컴공 일기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를 선물하세요.
-
중앙대 합격인증 9
-
중앙의 최초합!!! 57
1지망 최초합하는 바보입니다
-
감사합니다.
-
중앙대 이거 붙나요? 17
제가 살아야 중대기계님이 살아요..
-
세무사 붙은 시립대생이 제일 잘 산다.
-
19등/27에 예비 8번 예상했었는데 진짜 8번 뜨노
-
당연히 추합이고 추합 2000번쯤까지 도는데 왜 전화로 돌린거지 걔넨 중앙대 합격증...
-
중경 최초합 3
ㅅㅅㅅ
-
수능 끝났을 때는 "드디어 해방이다!" 싶었는데, 정서 원서까지 내고 나니, 진짜...
-
내년에 중약에서 뵙겠습니다
-
무등비 0
쎈이랑 시발점에 무등비가 좀 많은데 일단 시발점 문제는 풀었습니다 워크북이랑 쎈에...
-
합격 ㅇㅈ 16
고3때부터 총 11번의 불합격. 그리고 인생 처음으로 받아본 합격증이네요. 한발짝...
-
생각해보니까 친구들이랑 어머니가 …오르비를…..아
-
흑 ㅠㅠ
-
중대 경영 3
추합 213번이면 무조건 돌까요?? 이거 꼭 돌아야되는데..
-
완전 재밌었는데 혹시 저를 하루이틀만 고용해주실 사장님 없으신가요??
-
중대경영 0
644붙을수잇나
-
방 빼고싶어요방 빼고싶어요방 빼고싶어요방 빼고싶어요방 빼고싶어요방 빼고싶어요방...
-
넹 예상보다 등수가 더 높네요 (한 예비 40번 받을줄 알았슴) 중대 전전은 약빵이 맞는듯요
-
중앙의 떴냐? 5
1차추합때 바로 되겠지,,
-
48명 뽑는데 14번 나옴.. 될까여?
-
나머지 두 놈. 7
머가리 썰러 간다 기다려라
-
중앙대 합격/예비 받으신 분들 점공에 입력 부탁드립니다 ㅜㅜ 0
합격하신분들 축하드립니다~~~
-
중대 경영 0
606번 붙을까요 ㅋㅋ
-
오늘....ㅠㅠ
-
조아쓰 3
중대 깔끔히 합격! 이제 서강대만 제발 추합되라
-
대 중 앙 11
감사합니다
-
중대도 붙었는데요 아니 이게 왜 최초합
-
엄 3
엄
-
보면서 많은 걸 느낌 암살범은 영웅으로 대우받고 있음 조커 보면서 개연성 없다고 생각했었는데
-
중대 경영 1
예비 278 무조건 붙음?
-
수능보기? 맞아 정답
-
아마 10등권일거고 장학생이네요 나머지도 잘 돼서 뒷분들에게 자리 드릴 수 있길!
-
2시땡하자마자 들어가서ㅉㅉ 내가 먼저 볼거라고!!ㅠㅠ
-
野 계엄 폭로전에… 합참의장 “김정은이 돈 들여 확인할걸 왜 해주나” 6
김명수 합참의장, 국회 내란 국조특위 출석 “계엄 준비 없어… 외환·북풍 주장은 軍...
-
짜잔? 22
중앙대 소프트웨어 합격이닷 장학금도..?
-
아 ㅈㅂ
-
오오
-
하.. 터졌냐? 3
에바야
-
잇뿐!!! 1
가자
-
놋코리 니훈 0
..
-
중앙대 발표 0
중대 2분전
-
사실 헬조선 취업시장이 박살나면서 공대 전체의 문제이기는 한데 공대생이 취직을...
-
?_?..
-
5분이라도 조기발표 해주지....ㅡ3ㅡ
-
해주냐
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.