컴공 일기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를 선물하세요.
-
안먹으면 잠엄청와서 참고먹는데 속 진짜 먹을때마다 ㅈㄴ쓰림
-
진로, 취업, 학교생활, 결혼등 다 괜찮습니다~
-
ㅇㅅㅇ
-
입결 가지고 차별하는 경우가 없지 않나요 그런 경우가 있어서도 안 되고 말도 안 되고
-
옯모닝 3
-
노잼일듯 나,엄마 엄친,엄친딸 이렇게 넷이 감
-
매우 궁금합니다
-
개패고싶음
-
가기 ㅈㄴ 싫네 가서 또 뭔 소리를 들을지..하 막내여서 할것도 없는데 걍 잇올이나 가고싶다 ㅠㅠ
-
군수했는데 처참하게 말아먹고 1-1복학인데 그냥 학교 프라이드도 없는데 다니기도...
-
중앙대 합격생을 위한 노크선배 꿀팁 [중앙대25][최애맛집 공유] 0
대학커뮤니티 노크에서 선발한 중앙대 선배가 오르비에 있는 예비 중앙대학생, 중앙대...
-
아님 동테? 머에여?
-
그 이름은 대 서 연 그냥 보기만 해도 웃음이 절로 나옴 ㅋㅋ
-
설치 면접 끝 8
진짜 잡담스러운것만 물어보긴 하는군 근데 하나 대답못함 ㅋ
-
리트에 관한 게시글을 두 번 연속으로 올리고 나서, 이번에는 논술 계획에 대한 글을...
-
소설은 당연히 다 정독하고 푸는데 고전시가나 현대시는 어떻게 풀어야할지 모르겠음..
-
ㅠㅡㅠ
-
ㄹㅇ이 합창파트 ㅈ됨
-
속물적인 년 24
친동생임
-
마플시너지 다음으로 너기출vs고쟁이중에 하나 풀려고 하는데 어떤게 좋을까요?
-
자만하기. 10
고정 드립치기. 이것은 입시판을 떠난 자만이 할 수 있는 특권
-
체육대회같은거 할때 단톡에 "자1위하자 애들아!!" 보내보고싶음
-
형수 칼 4
??
-
영어.전공어가 점수매우 낮구요......(4,5,) 차라리 수학이랑 과학 선택과목...
-
거임?
-
대체 소대장이 뭐라 말해놓은거지...
-
물리시치 빼고는 그런 거 같은데
-
진짜 맛있다. 매실맛 나는데 최고임. 제발 고정..
-
사수생만 좋아요 누르셈 24
대학좀가자
-
너무부끄러우신걸까
-
생윤 사문 3
수특 수완 빡세게 봐야하나요?
-
대학간판만 중요시할까? 솔직히 방송같은거보면 그러자늠
-
(서울대 합격 / 합격자인증)(스누라이프) 서울대 25학번 단톡방을 소개합니다. 0
안녕하세요. 서울대 커뮤니티 SNULife 오픈챗 준비팀입니다. 서울대 25학번...
-
이제 진짜 골라야하는데
-
난엄슴
-
수학 2등급 - 3등급 왔다갔다 하는 학생인데, 국어나 탐구가 잘 되어있는 편이라...
-
박혀보면됨
-
의대 가고싶다 3
의사는 별로
-
공리는 참이라는 증명이 없다 따라서 귀류법 증명도 없다 따라서 공리를 부정하면...
-
고구마라떼 맛있다 14
훈육관님이 줬음
-
지금 고대 663.11점인데 될까요ㅠㅠ 2,3지망은 무조건 붙는거 써서 웬만하면...
-
일 할 시간은 없는데 쉴 시간은 있네 그냥 홈페이지에 발표창 하나 띄우고 퇴근해라
-
ㅜㅜㅜㅜㅜㅜ
-
얼버기 19
-
나는 왜 공감안해줌? 12
1=2 라고 공감해달라고
-
궁극의 가설 0
공허참에 의하면 전건이 거짓이면 명제가 참이다 p->q 에서 p가 거짓이면...
-
향긋
-
강민철T만 듣는데, 12수능 비트겐슈타인지문 이원준 t 해설 한 번 듣고싶거든요? 1
죄송한데 혹시 강의가 있을까요?? 경험, 경험 가능한, 경험적. 이 세가지가...
-
이거 먹어봤음 3
맛 궁금하면 100xdk보내셈 댓글로 알려드리겠음
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.