컴공 일기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를 선물하세요.
-
영어는 2 사탐은 둘 다 만점 아니면 47이라고 가정했을 때
-
V올인원 10강정도들었고 실력확인..?차 3모한번 풀어봣는데 관계고 자시고 해석을 몬하는디
-
엉엉 울엇다 4
점점 감성적인 사람이 되고 잇다
-
취소선 8
Tests
-
??? 이게 맞아? 15
????????
-
현우진쌤 은퇴하기전에 1타 뺏길거 같나요?
-
며칠 전에 일본여행 갔다왔습니다. 패키지 여행이라 막날에 면세점에서 쇼핑하는 시간이...
-
영어 5 합격 9
현역 영어4 -> 재수 영어 5 이게 되네
-
진짜 그정도에요??
-
테스트 4
테스트
-
공군 수석합격 2
이랑 9급 공무원 붙는거랑 난이도 비슷한가
-
오르비언들 옯뉴비한테는 너무 착해서 ㄹㅈㄷㄱㅁ 달아줌
-
지듣노 2
-
탐나네..
-
전 집가는중이에요
-
하 수능과외 너무 안잡히는데 걍 중딩이라도 해야되나.. 또 중딩내용 따로공부해야되나 그럼.. ㅅㅂ
-
수만휘에도 썼는데...댓글이 없어서 좀더 보강해서 오르비에도 올려봅니다. 중대...
-
군수 할말 4
포병 아님
-
1.무플 2.김범준 닮았어요 3.누나는 의대가라…(부엉이피셜) 4.힘내욧 임티...
-
하지만 이게 내가 할수있는 마지막 메타굴리기...
-
경평ㅋㅋ
-
학생이 잘생겼대요 10
중2 남자애가 갑자기 와서 쌤 잘생겼어요 하고 감 뭐지
-
ㅇㅈ하면 달릴 댓글 13
의대 스나 합격을 진심으로 기원합니다
-
이거 어떻게 못하나요?
-
인증 예상글 2
왜 클릭?
-
본인 인증시 댓글 15
.....
-
가격 얼마할려나~
-
메쟈의가야할거같은데? 과탐하자 아.
-
이 생각 다들 한번쯤 해보지 않았나요.. 예를 들어 나는 사과를 보면 노란색이...
-
내가 번호를 따이다니 말이안됨 당연하지 거짓말이니까
-
26수능 또 엄청 고이겠네 하 25 물리 컷 보니까 수능은 표본이 말이 안되는 수준인데
-
약대라서 다행이다 넌 의대로 반수해라
-
컴활 2급 0
이거 다 외워야해여?
-
ㄹㅇ재밌을듯…
-
메가패스 하나 사기도 눈치 보이네 어짜피 결국 살거 빨리 사는게 이득인데 쉽지않음
-
그 자동차 회사 공식 정비소? 이런 곳 가셨는데 정비하시는 분들이 죄다 키 크고...
-
뜌땨땨 하면서 존나박음…
-
스스로 자잖아... 난 가만히 있었다고.............
-
지구가 천구적도와 나란한 방향으로 회전하기에 북반구 중위도에서는 천체가 동에서 떠서...
-
2025수능 미적분 68 4등급뜨고 재수합니다 제 수준에 개념강의 어떤 분 강의가...
-
시간 어느 정도 걸리시나요? 난이도는 평균이라고 잡았을 때 궁금합니다!
-
김범준 듣는애들 0
무슨 단원이 가장 도움됨?
-
ㅁㅌㅊ
-
예비 고3이고, 문학을 감으로 푸는 감이 있어서 확실히 하고자 김재훈 쌤 문학 특강...
-
여초회사에서 일하지 마라
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.