컴공 일기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를 선물하세요.
-
.
-
아인슈타인 천재인듯 13
특수 상대성이론 듣는데 ㄹㅇ 감탄만 나오네 뮤온 입자 얘기 나올 땐 소름 돋음 캬..
-
마지막 까지도 하지 못한 말
-
대학 실수로 재수할 뻔한 수험생, 결국…DGIST "합격 처리" 27
대학의 실수로 다른 대학에도 입학하지 못한 피해 수험생이 임태희 경기도교육감의...
-
진짜 뭐 안 했는데 이상하네
-
아니 다 사라져서 노는 애들이 몇 없는디… 고3때랑 스토리 빈도가 큰 차이가 없어..
-
해야되나요?
-
약속 끝나고 집 올때 쯤에 가장 머리가 마음에 드는 현상..
-
1티어 : 경영/경제 - 자타공인 문제의 황제들 1.5티어 : 정외 - 상경이들에게...
-
무언가를 만족시켜야된다는 생각한 내가 부끄럽네
-
그냥 갤러리에 있는 사진...
-
이번엔 강사가 얼마나 개뭐라할지 후
-
올해 오르비 좀 0
줄여야지 하루에 10분
-
은근 남자들 소개팅이나 연애 시 여자가 칼같이 더치페이하면 자존심 상해서 별로라는 분들 많네요.
-
살거 8
23,24드릴 제본(젤먼저?) 강기분 문,독 사야할듯 작년 사규시2(젤먼저) 샤인미...
-
계속하면 민폐이려나
-
오늘 한일 롤체 1등 2번 와퍼2개 시발점 공통완강 헬스 오르비 오르비 오르비
-
농심 : 킹겐, 기드온, 피셔, 지우, 리헨즈 / 감독: 첼리, 코치: 크레이지,...
-
성인되면 배그에서 만난 어떤 누나랑 술마시기로함 낭만쩔지
-
정시에서도 내신 개많이 볼거란 말이 있어서 무섭네요
-
지금이 조기발표철인걸 이제야 알았네요 우주최강 정시파이터분들 원하는 학교 가시길 기원합니다!
-
김동욱 쌤 풀커리에 김상훈 쌤 문학론&유네스코 얹고 싶은데 어떻게 하면 될까요 0
일취월장 들으면서 문학론을 같이 들으면 될까요? 아니면 일취월장 할 때 잠시 문학은...
-
덕코좀 주세요 6
가난한 이에게 자비를!
-
화작 84 미적 96 영어 2 과탐 97 82 내년에 받을거임. 꼭,,,,
-
화작 확통 생윤 사문 순으로 88 96 80 99 인데 확통을 진짜 하는게 아니더라...
-
통합사회 통합과학은 문항 수도 안 나온걸로 아는데 이런 전반적인 시행 계획 언제 나오나요?
-
소신발언 3
천지인 <<<< 틀딱… 이라고 생각한다면 7ㅐ추 ㅋㅋㅋ
-
일억덕 가쥬아
-
수학 과외 3
경희 이화 시립 정도의 라인대면 잘 구해지나요.?.?.? 여러분들은 어디서...
-
몇월? 입대 몇점인가요?
-
오우야 크리퍼 눈나....
-
학교랑 본가랑 지하철 타고 2시간 거린데 기숙사 사는 게 나을까 대신 기숙사 살면...
-
나중엔 리트 지문을 읽어낼 수 있는 수준이 되면 좋겟어요 너무 설렌다
-
피로 누적 2
하암
-
역시 불금
-
마카로니랑 치킨무만 있어도 뚝딱이야
-
현재 공군에서 군복무중인 군인입니다. 군생활 하다보니 시간도 남고, 공군 온 김에...
-
음쓰>재활용 ~재활용>음쓰 …?
-
작수 14 15 20 21 22 27 28 29 30 틀렸어요 풀지도 못하겠어서...
-
진주교대 면접 2
교대 생각이 없다가 준비를 하게 되어서 면접을 어떻게 준비해야할지 모르겠습니다....
-
저는 경고 했습니다
-
외가 친가 다합쳐서 건대보다 잘 간 사람 없는걸로 아는데 본인 능지 딸려서 오수함...
-
마카롱 6
-
어땠는지 알 수 있을까요?
-
할맥에서 9천원인데 세개먹어서 2만7천원나옴
-
궁금함
-
사실 살짝 예측은 한게 생명과학부가 너무 펑크 분포인데다가 최종 컷은 생과부가 살짝...
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.