컴공 일기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를 선물하세요.
-
물1화1생1화2생2 제외
-
이거 상승곡선을 타야 20렙을 가는데 왜 이러지 이 다음 갑자기 14자리에서 의문사할 삘임
-
미적3틀+미적에 시간 박느라 공통 못 푼 거 감안해서 기하 88로만 바꿔도 지방의...
-
살기가 귀찮네 6
ㄹㅇ 뒤질수도 없고
-
보통 얼마나 걸릴까요???
-
Hi 강릉 0
-
08이 맞을까요 80이 맞을까요
-
밸런스게임 1
재미로만 봐주세영
-
과연 오평은 지역인구와 비례할까
-
-
컴공 일기269 0
알고리즘 큐로 넘어왔습니다. 알고리즘 문제를 풀기 전에는 늘 그것과 관련된...
-
수1을 존나 못함
-
수능날 과탐 컷 일케 뜨면 5시 오르비 반응 어떨까 7
물리 41 36 32 화학 45 41 36 생명 43 39 35 지구 42 37 33
-
저 등장 2
-
학교선생님 11
좋아하는데 어케할까요 고2요
-
이남자 협곡도 지켜 원신도 지켜 붕괴도 시즌별로 지키고 있어 젠레스존제로 세계도...
-
VERBAL MEMORY는 국어실력하고 연관있나?
-
질문받습니다 45
제발요
-
+8% 0
달달하노
-
맞팔구함 1
30분마다 올림
-
사실 1트가 고점이었다 같은 끔찍한 결과는 아니겠지 20렙 찍을거야
-
솔직히 엄청 맛있다 이건아닌데 의외로 먹을만하네.. 걍 집에서 닭가슴살에 잡곡밥...
-
메인글 가는방법 2
한번 쯤은 가보고 싶은데 방법이 있을까
-
. 2
.
-
실시간 왕불쌍맨 0
지난 일주일간 순공 1시간 25분 찍은 본인
-
질문받음뇨 9
스펙 오후 5시에 인나서 인나자마자 고기 먹으러 감 그래서 거지됨 현역임 잘하는거 딱히 없음
-
질받 34
질문받습니다.
-
1개월만에 미적 27번까지 무난하게 풀 정도 돼야하는데 3
아예 노베 기준 무슨 수업을 들어야할까요 이게 수험생활을 하려고 하는게 아니라 되게...
-
수2가 나를 구원해주리
-
뭐가 높을래나
-
나도 질문해주 1
https://orbi.kr/00071605515/%EC%A7%88%EB%B0%9B%...
-
5월달에 재종 들어가려고 하는데 강대의대관은 50프로 장학이 되고, 시대는...
-
근데 저런 뇌피셜글을 쓰는 이유가 뭘까요(진짜모름) 8
본인피셜 여자친구도 있고 좋은 직장에 다니시는 분께서 2018년쯤에는 올2컷으로...
-
질문받는 이유는 장염 걸려서
-
딥시크에게 시켜봄ㅋㅋㅋ 요즘 이런거 너무 잘됨ㅋㅋㅋ
-
질문받습니다 4
저도한번해보고싶었어요
-
특성화고전형 4
적페가 맞긴 한거임? 난 하고싶은과가 달라서 일반전형으로 햇는데 다들 왜...
-
설 연휴 동안은 3
여캐일러투척 없을 예정 추석이라 썼네 암기하느라 뇌 용량 터져버린듯 ㅋㅋㅋㅋ
-
으음 요즘 한달사이에 싹다 물갈이됫다 해야하나 탈릅하는 사람도 많은데 누군질 모르니 인사도 못하겟네
-
뇨
-
근데 또 참여하면 진짜 정치병자란 소리 들어도 할말 없기 때문에 (이미 그런가?) 한타임 쉬고가야지
-
메모장에 적어놓으면 되기때문
-
질받메타임? 11
ㄱㄱ
-
저거 숫자암기 평균이 7임 새삼 오르비가 최상위권 커뮤니티인게 느껴지네
-
질문 받겟습니다 29
예.
-
서강대 합격생을 위한 꿀팁 4 [서강대 25][Tip.4] 0
대학커뮤니티 노크에서 선발한 서강대 선배가 오르비에 있는 예비 서강대생, 서대...
-
근데 어카냐.. 킅런트가 일을 안하는걸.. 2월 초중반안에는 진짜 올라오겠지..?
-
아 557인지 577인지 헷갈려서 틀리고 뒤에 2641 2461로 잘못 적은거랑...
-
단어암기 2
https://humanbenchmark.com/tests/verbal-memory
-
4등급 스블 2
쎈B랑 스블 병행하고 있는데 스블 지수로그함수 문제들이 거의 안풀리네요 최대한...
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.