컴공 일기264
10진수(decimal)를 2진수로 변환하는 알고리즘입니다.
주로, stack을 이용해서 구현하지요.
20을 2진수로 구현하는 방식은 다음과 같습니다.
20 / 2 = 10 …0
10 / 2 = 5 … 0
5 / 2 = 2 … 1
2 / 2 = 1 … 0
1 / 2 = 0 … 1
몫이 0이 될 때 까지 나누고, 나머지를 밑에서부터 출력하면
10100이 되지요.
이 과정을 표현하기에 적합한 자료구조가 stack입니다.
제일 먼저 2로 나눈 수는 20이지만, 20을 2로 나눈 나머지가 제일 마지막에 출력 되어야 하죠.
말하자면, 나눈 순서와 나머지를 출력하는 순서가 거꾸로 뒤집힌 상황입니다.
그러니까, 1이 제일 마지막으로 2로 나누어졌지만, 이 결과로 얻어진 나머지가 우선적으로 출력이 되죠.
다시 말해, First in - Last out을 만족하는 stack구조가 적합하다는 판단을 내릴 수 있죠.
제일 첫번째로 입력된 데이터가 마지막에 출력된다.
도출 과정을 글로 요약해보면 이렇습니다.
1. “해당 수를 나눈 몫이 0이 될 때까지 2로 나눈다”
2. “나눌 때 마다 얻게 된 나머지를 스택에 집어 넣는다”
3. “스택의 데이터가 모두 없어질 때까지 출력한다”
조금 다른 감이 없지 않아 있습니다만, 실제 알고리즘을 구현할 때
이런 식으로 간단히 의사를 정리해두는 코드를 Pseudo code(의사 코드)라고도 합니다.
개인적인 견해로, 이런 예시로 보면 알 수 있듯이 코딩은 절차적인 글쓰기입니다.
시제를 넘나드는 OOP로 넘어가면 얘기가 조금 달라지지만, 근본이 이렇죠.
#include <iostream>
#include <string>
#include <stack>
using namespace std;
stack<char> st;
int main()
{
int num;
cin >> num;
//해당 수를 나눈 몫이 0이 될 때까지 2로 나눈다
while(num > 0)
{
int ret = num % 2;
char res = '0' + ret;
//나눌 때마다 얻게 된 나머지를 스택에 집어 넣는다
st.push(res);
num /= 2;
}
//스택의 데이터가 모두 없어질 때까지 출력한다
string result = "";
while(!st.empty())
{
result += st.top();
st.pop();
}
cout << result << endl;
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
나 정말 저능한데 고능한 친구들이랑 같이 수업 따라갈 수 있을지 고민.. 학점...
-
떵떵거리고 싶어
-
등록금 인상된거 너무 비싼데;;
-
수강신청이쉽다
-
점심추천해주세요 22
。◕‿◕。
-
운동가기싫다 3
하지만가야만해
-
정시모집요강에서 못본거같은데 보통 거기에 써있나요..?
-
뀨뀨 13
뀨우
-
여자력 상승 12
성형외과 상담예약있다
-
금융 증권 쪽 일을 하는 게 가장 좋은 길 같다 물론 국어와 수학을 잘해서 대학을 잘 간 다음에..
-
과탐 2등급도 4
걍 사탐런이 이득인가요? 국수는 2,1 인서울높공,지방약수 목표로 하고 있는데 뭐가...
-
모든게 애매하군 10
기말시험은 안애매하게 만들어주지
-
그 인증을 받으려고 6년간 유급,제적빔 때리면서 학생수 줄여나가면 인증평가 통과할수 있긴함
-
13명 모집인데…ㅋ . ㅋ ㅠㅠ
-
기념일이라는건 7
공전을 기준으로 하는거잖ㅇ음 자전을 기준으로 한 기념은 없는걸까 둘다 지구가 한바퀴...
-
단국대~광운대 라인이고요… 작년 재작년에는 뽑는 사람도 30명대로 많았고 충원율...
-
제가 이번에 대전한, 원광한 썼는데 둘다 붙을수도 있을거같아요. 둘중에 어디가 좀더 낫나요??
-
의평원 불인증 알빠노 아닌가요..?(선동아님 질문글) 30
졸업하기 6개월전에 인증받기만 하면 국가고시 칠수있다고하는데.. 로스쿨 다시니는분들...
-
는 아니고 홈페이지 가면 있어요
-
추천해줄 책이나 강의 있을까요?
-
하 코어관리 열심히 해야겠뇨
-
통째로 번역한다고 (책 한 권/논문 한 편) 통+번역인 줄 알았는데 통역 +...
-
서울역에서 먹을지 대치동에서 먹을지 고민이네용
-
공스타맞팔구함 0
구함요
-
중대에서 같이 다닐 오르비언 구해요
-
오티 갔다 와서 3월에 해야지
-
서강대 조발 1
언제 하냐 아아으의아으의이아에
-
면허따야대는데 1
ㅠㅠㅜㅜ
-
한 3~4일 빡공하면 담날부터는 머리 깨지면서 어렵고 깊은 사고를 요구하는...
-
국토대장정이나 챌린지 형식의 여행 유튜브 너무 재미있음...
-
만날 기회가 있긴 할까..
-
간쓸개 0
나옴?
-
꾸준글
-
얼?버기? 6
-
현우진 시발점 0
시발점 강의 꼭 들어야하나요? 3,4등급 정도 나오는데 시발점 문제들(본책)은 거의...
-
내가 번역을 크게 잘못해서... 나 때문에... 말이 심하게 나왔대... 나는...
-
안녕하세요 :) 디올러 S (디올 Science, 디올 소통 계정) 입니다....
-
이번에 재종에서 재수함 공부는 진짜 선생님들이나 애들 누가 봐도 열심히 했음 근데...
-
Day 1씩 외우는 중인데 *표시 있는 작은 검정단어 빼고 예문 보면서 뜻 다...
-
운전면허 감독관 계속 옆에서 핸들에 힘주지마라 차선 한참 남았는데 브레이크 밟으라고...
-
칼럼 또 씀뇨 0
ㅇㅇ
-
제 첫닉 아시는분? 11
설마 있겠어
-
2탄에선 우리 옯붕이들이 실제로 할 수 있는 것들로 준비 해봤다 1. 기본중의...
-
안녕하세요 인간쓰레기에서 인을 담당하고 있습니다
-
상지한 a형 2
37/149 점공 합격기원.. 진짜 점공 안들어오네요 ㅋㅋㅋㅋ 빵이면 좋겠다
-
3년전 사귀엇던 남자고 내가 번호바꾸고 카톡 전번으로 추가랑 추천친구 다...
-
차라리 연대나 서강대 성적이 되면 괜찮은 거 같은데 중앙대랑 경희대는 사탐 감점이...
-
영어 고1은 무난히 1등급 떴는데 고2 올라오니까 단어가 한 지문에 한 6-7개씩...
-
맞팔구 6
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.