컴공 일기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
6수 나이인데 5수생이고 수능은 3번밖에 안 봤고 3수에서 4수 갈 때 성적...
-
야식 땡기네 0
음
-
음…………
-
저녁여캐투척 15
음역시귀엽군
-
스카이 졸업했는데 예술에 뜻이 생겨서 예대 진학하려고 공부함 6수 했는데 매번 불합 계속 하는 중…
-
이유는 없음 ㅋㅋ
-
원에서 문제나올때마다 안풀리는거2~3개씩있는데 정상임? 윽건이풀이는 이해됨
-
대가대의대(지역인재) 조기발표나왔는데 제가 예비10번이고 정원5명인데 추합 가능할까요?
-
갑자기 든 생각 4
우물 안 개구리로 사는게 꼭 나쁘기만 한걸까
-
공부해야지. 0
암.
-
1차 신도시 2차 신도시 3차 신도시 수특수완에 넣고 도시 특성+인구...
-
고민이되는9나
-
너무 피곤해지려나
-
궁금해요 아직 뉴비임
-
언어와 매체 : 온라인 소그룹 및 커뮤니티에서 사용되는 은어의 변화 양상과 제도권...
-
현실에서 직접 본건 ㄹㅇ 재수가 최대예요 삼수생부터는 만나본 적이 없음뇨
-
현질하고싶다 8
근데 돈이 없음
-
상위권 문과 하위권 이과 지원할 것 같은데 탐구가 성적이 잘 안나오네요 사문 한지...
-
피타고라스 학파는 학문을 사랑하는 종교에 가까운 집단이였다. 어느 날 피타고라스...
-
뭐 물어보면 4
방학때 ~~공부 해두는게 좋을까요? 물으면 지금은 놀거나 알바하라고 하는게 개...
-
왕자 잘게 7
오야스미
-
전 00년생 본 적 있음
-
풉 풉힙 풉 미소된장국 푸히히
-
대민주 6
-
흐음
-
옛날에 1
책과 관련된 어떤 유튜브를 보고잇엇다. 영상의 내용은 모든 책은 거의 말하는 바가...
-
9년전만 해도 응시자수가 7만~8만이였는데 지금은 3만5천명정도 사문보다 다섯배는...
-
ㅈㄱㄴ
-
무한서울대시도할듯
-
아까 부장님께 걍 앵카 박았다했는데 지금 함대에서 날 보내주겠다고 하고 2월 말이나...
-
나이도 개틀딱 부산에서 지인없이 혼자 자취 얼마나외로울것인가..
-
차라리 정시 백퍼를 하면 갈 데가 있겠지만 본고사는 진짜 자신이없음... 논술형...
-
문제를 푸는건 4
무지를 깨닫는 것 무지를 채우는건 그 다음의 단계
-
난 쓰레기야 16
미소녀를 대기시키고 유기해버렸어
-
전 군수로 27만 보려고 하는데
-
25수능 개화지문도 이해하면서 풀었나요? 문제 풀려면 이해했어도 다시 지문으로...
-
무슨 글을 써야함?
-
확실히 정시커뮤네 34
내신반영보다 본고사라니 본고사는 진짜 수능이랑 아예 결이 다른데 그거랑 병행해야...
-
은퇴 1
소해린이될때
-
아 돈벌고싶다 0
과외생조차도 정상이아닌 이인생 ㅜㅠ
-
카포나 뭐 3개 과기원 걔네는 정시로 많이안뽑아서 정시 입결로 라인따지기도 애메한데...
-
좀 해라 이것들아
-
48명 뽑는데 1바퀴 반정도 안돌겠지..? 1바퀴가 정배죠? 1칸스나인데..0
-
대가대 조발 떴네요! 가나 군도 붙을 것 같아서 등록은 안할 것 같지만, 그래도...
-
실력이 좋은 것은 아니다. 지식은 충분한 시간이 잇을 때에 누구나 채울 수 잇다....
-
자취 0
어케하심 다들
-
이제 슬슬 2
정시 최초합시즌인가봐여
-
예비중3 학습 상담을 해야하는데.. 무슨 얘기를 해줘야 하나... 9
ㄹㅇ 고민이네... 고등학생도 아니고..
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.