컴공 일기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를 선물하세요.
-
ㅈㄱㄴ
-
손 큰 사람이랑 0
손 잡으면서 나란히 걷다가 골목 들어가서 … 강민철 강의 같이 듣고싶다 ㅎㅎ.
-
이번 입시는 그냥 실패 그자체네
-
수1,2는 여러번돌렸고 미적은 기초 약간 아는데 3모 대비 겸 기출 돌리는 시기...
-
퇴퇴퇴근 1
재수 끝내자마자 월 150버는 삶 ㅁㅌㅊ인가요
-
역시 수학은 밤에
-
얼굴 비추고 학생이 앞에 없는데 설명하려니까 은근 쉽지 않음. 인강쌤들 ㄹㅇ 대단....
-
예비고3이고 내신으로 지구과학 했어요. 겨울방학때 시간이 너무 없지만 지구과학을...
-
뜨거운 물로 몸 좀 불리니까 살 거 같네요 약효가 이제 도는 건가
-
윤 측, 헌재에 답변서 제출…계엄 배경으로 ‘부정선거’ 적시 2
윤석열 대통령 측이 헌법재판소에 제출한 답변서에서 이른바 ‘부정선거론’을 언급하며...
-
뭐든지 거품이생기는듯 서울자체에 가치를 둬서 거품이아니라면 할말없다만 뭔가 가격대비...
-
나도 잘까 7
피곤하네
-
수학 커리 병호햄이랑 석원햄중 고민인데 누구들을까요 2
본인 정석풀이를 선호해서 정석풀이로 유명한 두분 강의를 좀 들어봄 솔직히 한석원...
-
한양대 갈거임
-
주세요오...냐옹
-
3때는 감흥도 없었는데
-
이번에 원광대 불인증 뜬건 중간평가라고 하던데 증원 고려한 평가는 2월 초쯤에...
-
남자아나운서를 꿈꾸는 수험생들 참고 + 서울/ 카이 / 고려/ 성균관/ 한양/...
-
1년 교재비 0
재수하면 보통 1년에 교재비 알마씩 쓰시나요? 재수하는거 죄송해서 12월에...
-
695따리라 못썼음 실제론 가군 고미디 나군 설인문 다군 고학부 썼음
-
무섭다... 7
ㅠㅠ
-
수학에 몰빵하지말걸
-
나도 그랬지만 질문글이 너무 답하기가 어려움 굉장히 포괄적이여서 누가 와도 답변하기...
-
히히 취한다 4
하이볼 맛있어
-
충원율 300% 넘게 찍을 수 있을까요?
-
설날 대학 4
친척이 05인데 재수했어요. 어디 붙었는지 (어디 썼는지) 물어보면 실례인가요?...
-
물화 안껴있으니까?
-
서울대 경제학과 어떤 분 대학 다니먼서 2년 컷 내는디
-
이정환T 후기 0
이정환 선생님 현강 어떤가요? 꼭 알려주세요!!!!
-
커리 옆 괄호는 시작~종료월(月) 국어(원98 백100) 독서문학: 김민정...
-
뀨우 15
><
-
유리한 것: 연대식 충북식 건글식 한림식 불리한 것: 설대식 중대식 백분위대식
-
시발시발점 0
하루에 theme 하나씩 나가는게 정속이에요? 보통 강의 3~4개정도
-
연경 설윤교 7
이게 맞아요
-
눈맞아서 증식했나 아까 길가다가 비둘기 보고 닭인줄 알았움 징그러워 으
-
설경제간다 6
고경호소인 메가진화함.
-
Q.협의의 소의 이익에 대한 설명으로 옳은 것은? (다툼이 있는 경우 판례에 의함)...
-
연대 조발 하라…
-
숭어회 맛있네 9
대방어만큼은 아닌데 그에 비해 슴슴하면서도 여전히 기름지고 쫄깃한 맛이 아주 좋네요
-
그 학교 제일 끝자락인데 붙이려고 쓰는거 아녜요? 안정으로 박는건가 아님 합격증만...
-
지1사탐 할빠엔 3
세지사탐 한다 ㅋㅋ 세지 해줘요 ㅠ
-
1번 2번 3번 옛날에 만든 가장 악명높은 대표 물2 자작 문제 삼총사입니다. 네,...
-
자사고다니셨고 반수해서 고대전전다니시는데 일단 메가스터디 대성마이맥 등 인강수강x...
-
취직 얼마나 안되는지 확인해봄 ㅇㅇ
-
무물보... 7
... .... ....
-
사탐사탐이 더 쉽지않나 대학 가기 지1 3등급에서 1받기보다 사탐노베로 1받기가 더 쉽지않나요
-
어짜피 안돼서 걱정 안해도 됨 ㅋㅋ
-
언: 추정 어려움. 가채점 안 해서 표점 118인데 그럼 대략 78점이니까...
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.