컴공 일기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를 선물하세요.
-
이건 어때요?
-
오르비 가입할 때 친구 이름으로 가입했는데 센츄리온 받으려면 계정 이름하고 실명하고...
-
ㅇㅈ어제 두번은한것같은데 그이후에 맞팔한분들인지 그전에 맞팔한분들인지 궁금
-
보통 국어 준비할때 릿밋핏 푸는거에 부정적임? 난 이원준 커리가 릿밋핏 많이다뤄줘서...
-
ㅇ
-
김승리+과외병행 5
현 고3 모고 5정도 뜹니다 과외 다니는중이고, 주 1회 자이스토리 2회분 풀고...
-
적셔! 6
-
뭐뜯을까여 8
-
내 한계는 여기까지인가...
-
맞팔구함뇨 6
맞89
-
캬 은테달성 9
형은 먼저 똥테탈출한다ㅋㅋ
-
오야스미 11
네루!
-
저랑 뽀뽀하실분 5
????????????????
-
맞89 1
-
이게 이미 찐따면 벗어나기가 힘든거같음 성격문제를 스스로 알고있음에도 고치기가힘듦...
-
다들 하더라
-
제발제발제발 은테 가즈아!!!!
-
노래 추천 9
얼마나 좋아하냐면 폰 배경이 이거임
-
김현우 미적분반 5주차부터 합류하는데 지금 진도 ㅇㄷ나감???? ㅈㅂㅈㅂㅈㅂ
-
맞팔하실분
-
ㄹㅇ 문법 쌩노베라 못해먹겠음 찐 탐구 한 과목 더하는 느낌
-
난 씹덕글을 썼는데 태그가 안지워짐
-
취르비등장 2
두병반마시고 등장
-
이거 예비번호 20번 정도 뜨는데
-
너무 과하게 어려운가요? 미적 첫 엔제로 무리일까요
-
유리 2
-
점심을 토하기 직전까지 쳐먹긴 함
-
어려운4점만 다틀리면 몇점정도 나오나요?
-
이거 그만보고 싶어요, ....
-
하사십 개어렵네 0
생각할게많네요 ㅋㅋ
-
예비 140번대는 걍 안된다고 봐야겠죠…
-
그니까 요약하면 낼 아침에 일어나면 지젤이 내 여자친구가되는 그런 가능세계도...
-
다시 못 일어나겠네요.. FM은 다음에...
-
강평과 욱평 3
강평: 1년 내내 강기분을 못끝냄 욱평: 1년 내내 일클래스를 못끝냄
-
ㅈㄱㄴ
-
1시간지낫는데도 조아요 3명이누름,,, 스공도햇는데,,,,
-
일단 난 깔끔한게 조아서 시대파
-
캬캬
-
단어장을 하나 늘리려고하는데 이거 외우는분 계신가요???어떤가요!??
-
널사랑하는거지...
-
적응잘한것같음 커뮤체질인가
-
캐슬 정주행 끝 2
생각보다 진도 ㅈㄴ적네
-
힘들어 2
회로에 연립미분방정식이 웬 말인가 나를 죽이려고 작정했느냐
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.