컴공 일기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
-
나도 ㅇㅈ함 13
진짜 진지하게 효림이한테 고백하면 받아줄까
-
점공률 55퍼인데 45퍼나 점공이있는걸모른다고? 걍 몰라서안하는건지 귀찮아서안하는건지
-
모든 오르비언들을 믿을수없음 ㅇㅇ
-
개어지럽다
-
고민중임 낼 병원가야하는데
-
서울 기준 급하게 따야할 일이 생겼는데 며칠안에 가능한가요
-
롤체 레전드 1
예전에 탐켄치 선택할수 있었을때 일반에서 9렙 달려서 찍음
-
진짜 할말이 없네..
-
그럼 맘놓고 한 번 더 하기ㅋㅋ
-
좆도 쓸모없는 쓰레기지만 막상 달라하면 못주겟음 ㅇㅇ;;
-
아주대 903.33이면 첨단신소재 막차로 가능할까요?? 0
여기 붙으면 참 좋을텐데
-
메디컬 점공률 6
39%면 안들어온 사람들 중에 실수분들 어느정도 될까요?? 상지대 한의예...
-
일반 후드티가 뽀짝 후드티가 됨 ㄱㅇㅇ
-
여르비 찐인증!! 12
그런건없다ㅋㅋㅋㅋ
-
갑자기 무섭네
-
수학 2등급 정도 나오는 예비고3인데 개념은 다 끝냈고 기출 분석을 혼자 힘으로...
-
흠
-
예비고2인데 지금 수1 수2 시발점 듣고있는데 시발점이랑 마플시너지만 푸는게(1번)...
-
인증 너무 하지마요.. 오르비가 친근해도 인터넷이 얼마나 무서운데.. 누군가는 그걸...
-
밥집 가기도 힘들어 여기는..
-
ㅇㅈ 17
-
오천덕
-
"노"의 의지를 원하는가 피아제 시계를 원하는가 모든건 그곳에 두고왔다 찾아봐라 신세대여
-
여르비 ㅇㅈ 2
안녕하세요 오구라 유나입니다
-
수린이형~
-
그사람이 처한 상황과 능지와 모든게 다르기에 진짜 참고만하고 복붙하지는 말것
-
생각좀하고 글써야겟다 하
-
여르비 ㅇㅈ 7
조회수 테스트
-
옛날엔 활동을 해가도 기재안해주는 ㅈ반고 쌤들이 문제다같은 소리가 많이...
-
우리학교 후배 몇명나와서 깜짝놀랬네
-
여르비 ㅇㅈ 3
(수정됨) 23초
-
지하철 한번 환승하고 편도 한시간 정도면 통학 할 만한 거리인가요? 지방 살아서...
-
고2 모고 3~4등급 나왔고 학원을 고1때까지 다녀 문법체계는 어느 정도 잡혀...
-
공포주의))) 12
-
아 씨빠 5
강사쌤한테 고벡 갈기고싶다
-
인르비 여증 1
아님
-
방 ㅇㅈ 2
다 우리 형이 꾸밈
-
친절하고 좋은말을 해주면 나한테 돌아옴. 이걸 모르고사는 사람들이 많은거같아서 아쉽다.
-
남르비ㅇㅈ 19
-
왜냐면 나부터 여중생이거든
-
귓 하실 여르비들 귓 주세요
-
연대 빵꾸!!! 1
연대 생명공 빵꾸인가요?
-
감사합니다
-
학고할려고하는데 만약 복학하는 상황이 오게되면 어케되나요
-
자중해야지..
-
아이유랑 활동명도 비슷하고 같은 싱어송라이터고 노래도 좋고 감성도 좋고 그냥 좋음
-
ㅇㅈ 11
레무링이랑 사귀고싶다
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.