컴공 일기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를 선물하세요.
-
본인 0
작년 수능날 생일이었음… 수험장 나오고 친구한테 케이크 받은게 가장 행복한 기억임
-
2월 말에 재종 들어가기 전에 뭘 할지 고민인데요. 작년에 제대로 체화 못한...
-
올해 문과만점으로 냥의가시는 분이 문과 메디컬 최고 아웃풋아님?
-
너무 심한 소리만 빼고,,,
-
다른건 이해되는데 공산주의가 21%나 나온건 이해가 안되네 6
나도 사회주의 성향이 있는 건가
-
진학사 3칸이였고 점공률 46퍼입니다 발표날이 24일인데 발뻗잠 해도 될까요 ㅠㅜㅜ...
-
영향을 주는 비율이 더 높다고 생각하는 쪽에 투표 ㄱㄱ
-
어떻게 과 이름이 농 ㅋㅋㅋ
-
ㅋㅋㅋㅋ
-
정외 심리같은거 배워서 어디다써먹지 아 어렵다
-
근들갑 2
근들근들
-
24학년도 교육청 학평 킬러 중 제일 GOAT라고 생각하는 문제 13
24학년도 10월 학력평가 22번 구간별로 정의된 함수인데, 함수 의 부호에 따라...
-
보통 설경을 안쓰면 농경제를 쓰려나 정외를 쓰려나 16
아무래도 농 때문에 정외려나..?
-
사탐 언제 시작할거임
-
머리 6
가슴배
-
과외에 특강에…. 내 2배 이상을 쓰네… 근데 영어 모고 4?등급이면 인강...
-
작수 미적 백분위81이구요. 작년에 한걸 적어보자면, 현우진T 뉴런 다 듣긴했는데...
-
ㅇㅗ빠 7
차 있어?
-
자취방에서 뭐하는 거람..
-
비둘기게이가 ㄸ치다가 갑자기 알닮은 애가 ㄸ치는 거 알고 이불 뺐어가서 후다닥...
-
영어랑 안 맞나 1
가끔 Birthday 이런 단어를 보면, 뭔가 이상해
-
소액이라도 덕코 받으면 기분 좋잖아요? 모두가 막쓰면 순환하면서 기분도 좋으니 막씁시다!
-
사실 아까 옯스타 글 올릴 때 우정이 영어로 먼지 기억 안 나서 인터넷에 쳐봣어
-
팔취할거면 하셈여...가시는 길 고이 보내드리오리다
-
서로 아무 말도 안하다가 20분? 걷고 집 옴 왜 삐져있는거야 본인이 잘못해서 싸운건데 참어렵다
-
후배 잘못둬도 한참잘못뒀다
-
도전을 안 외쳣어 깜빡하고
-
원하시면 쪽지주세여 。◕‿◕。
-
왜 팔로우하시는거에요.. 잡담태그도 안다는 불량이용잔데
-
"해줘"
-
저도 옯스타 홍보할께요 10
Love, Peace and Friendship
-
내일 하겟습니다
-
그렇다네요
-
결국 그게 최고더라고요
-
파인애플펜슬이 될때까지 대기
-
살면서 가장 많은 사람들이 자신의 정치성향을 세게 드러내는 걸 보게 되는 시기같다. 0
아니면 나이가 들어 보이게 되는건가
-
입대일 4
따라라
-
삶은 계란 뭐랑 먹지 24
소금이 국룰이긴 한데 다른 조합 없을까
-
기하를 벅벅 17
얘도 안 하니까 감이 떨어지는구나...ㄷㄷ
-
오랜 생각이다
-
구라예요. 분석부탁드려요 찡긋
-
맞팔해주세염.. 4
네임드가 되기 위한 첫번째..맞팔해줘잉
-
다 오른쪽인데 진보하나만 높은 게 말이되나
-
라면을 하고 사이다를 넣으면면을 올릴 때 면에 기포가 묻어잇는데진짜 ㄱ ㅐ 빡침뇨
-
뭔가오랄잘할것같음 이빨도없자너
-
이거 불법으로 공약미는 정치인 나오면 내 인생을 걸고 빨아줄 자신있다 일본처럼 차고...
-
당장 전닉도 기억하시는분이 없을것같아서 포기함 혹시 계시려나
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.