컴공 일기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를 선물하세요.
-
하 삼수는 못하겠고 후회만 남는다...
-
ㅇㅈ 17
싸우지말고 사이좋게지내요
-
둘다 굇수들 천진데 포ㅁㅎ은 뭐랄까 오르비보단 건전하고 엄격한 느낌 오르비는 아무리...
-
처넌이네 ㄷㄷ
-
안녕히주무십쇼 6
어렵사리 다시한번 잠을 청해보도록 하겠습니다
-
ㅎ
-
공개좀요 ,, 어떻게 해도 평가원이랑 미묘하게 다른데 뭐지
-
아침일찍 기차타야되는데 밤낮바껴서 자는건 못함…
-
ㅋㅋㅋ 8
장 폐색 직전...?
-
선착 두 분
-
아무리봐도 얼싸 같음...
-
하루 6시간 자는데 낮에 졸음이 와서 낮잠 자야하는 상황이 나오면 7~8시간 자는건...
-
수학 실모에 쓰이는 그래프나 도형은 어디서 제작하시나요? 개념글에 수학 그림 그리는...
-
한문은 안받아줍니다
-
야차룰임 키 165 아래만 받음
-
설대식으로
-
연대 떨어지면 0
연대떨어지면 어떻게 살아야하지ㅢㅣㅜㅜ 삼수는 진짜 하... 올해 국어시간에 지금...
-
스펙)25수능 98점
-
오늘 안 사실 4
빨치산이 한국어가 아니었음
-
예전부터 딱히 하고 싶은 것도 없고 생각하기 귀찮아서 미루고 미루다가 고3이 돼서...
-
5만원빵 건동홍 이하 라인만 가능
-
6모배틀 ㄱㄱ 2
님은 6평 전 고2 모의고사 풀게요 ㅎㅎ
-
국수탐 백분위합으로 결정 6모의 황 저능부엉이님과 좋은 경쟁될수있게 열심히 하겠습니다
-
개삘이네요 으슬으슬함... 올해 들어서 건강한 날이 없네
-
저랑 성적 내기하실 분 17
평백 80 이하만 받아요
-
저랑 대결해요 29
대결 종목은 보드게임카페에서 정해요
-
맞89 3
-
오르비를 반으로 갈라버려
-
평가원 말고는 대충 다되는데 …
-
한강 ㅇㅈ 9
사람없는 새벽에 슬리퍼신고 최성노래 들으면서 따릉이 타는 삶이라..
-
지금 생각해보니 너무 죄송한 게 있네요 신규 젊은 수학선생님이었는데 수학 질문할 거...
-
누가 국어잘가르칠까요
-
08이라서 못함 ㅠ
-
슬더스 할 사람 0
슬더스하자 나도 뉴빈데 뉴비친구가 필요해
-
기준은 설대식이고 공정성을 위해 건동홍 이하면 받음
-
아.... 12
응급실옴...
-
이거 뭐임? 2
오리새끼뭐하능거
-
뭔가 다들 그런거같아요 굿나잇
-
생각보다 일년동안 븃기가 마니 빠진
-
탈락자는 산화되는 걸로 하죠
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.