컴공 일기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를 선물하세요.
-
나만입는브랜드
-
내가 여자였어도 안함
-
삼킨 음식을 블랙홀이 다 먹어줄거 아니야..
-
모든수의 시작은 자연수 자연수의 시작은 1 따라서 모든수의 시작은 1 따라서 1은 제1원인의 위치
-
결혼하면 안되는 사람이라고 생각해서 비혼주의임 결혼함으로써 얻는 안정감<자유인 것 같아서
-
아무도 상처받지않는 세상을 만들자
-
100세까지 산다 치고 70년을 한사람이랑 살아야하는데.. 너무 질릴듯
-
스나 성공한듯 14
진학사 2칸 걍 스나했는데 예비2번뜸 도는 예비같은데 아직 붙은건이니지만 ㅈㄴ 햄복하네
-
이건 1월인데 4
여행다녀와서 매매한동안 못해서 꼬였음 펑
-
내 생각임
-
비문학 황이라고 자만해서 걍 문학만 마더텅으로 풀어보고 작수쳐봤는데 비문학 4틀...
-
강대 의대관 독서실비나 컨텐츠비까지 포함하면 달에 얼마정도 쓰셨나요 그리고 수능...
-
독해력이 얼마나 구리면;;
-
주변사람들이 대학 물어보는데 답을 어떻게해야할지 모르겠음 5
OO대학교 쓰긴했는데,, 아직 발표가 안나서 잘 모르겠어요 이렇게 해야하나여? 아마...
-
펑 투자 10년차 안건든 상품 없음 실친들, 가족들은 아무도모름 월평균은 그냥...
-
결혼까지 바라보는중이고 한 명은 이미 날짜까지 잡아놓음 나만 도태한남임
-
난 많이 안돌거같다고 보긴 함
-
아 일본여자랑 5
결혼하고싶다ㅏㅏㅏㅏㅏㅏㅏ
-
아오 물리야!!!! 11
-
나 커뮤충이라 요새 비혼이 대세인줄 알았단 말이야...
-
ㅈㄱㄴ
-
전국서바,엄영대,나진환등등 25학년도 지1 모의고사 41회분 8만원이면 ㄱㅊ나요??
-
ㅈㄱㄴ
-
찌아찌아족 4
골라도 하필 8%
-
대학커뮤니티 노크에서 선발한 경희대 선배가 오르비에 있는 예비 경희대학생, 경희대...
-
얼버기 2
ㅎㅎ
-
농담이고 국어 아무거나 질문 받음 퀄리티있는 답변 기대 ㄴㄴ
-
우진이형 수분감 step1,2 총 6강씩 진도나가는 중인데 4
수1,수2,미적 각각 스텝 1,2 1강씩 해서 하루 6강씩. 스텝2는 괜찮은데...
-
몇살때 결혼하고 싶으심?
-
나보다 공부못해도 괜찮음
-
점메추좀
-
맞선 들어왓는데.. 15
상대는 7급 공무원이엇는데 아버지보고 내가 나 대학교 졸업도 아니고 이제 시작인데...
-
안나올수가없음ㅇㅇ
-
영국 노섬브리아 대학교 복수학위와 커리큘럼 영향으로 최근에도 해외 진출 사례가...
-
대깨컴이라서 망정이지 메디컬 지망하고 있었으면 공부하다가 죽어 나갔을 거 같음 ㅋㅋ...
-
속 ㅈㄴ쓰리다... 콜라먹고 카페인 플라시보효과 안되려나
-
설경제 2
내신bb전제하에 390까지는 죽어도 안오나요? 걍포기하고 편하게살까여?
-
후기를 남기겠음 2
지금 너무 기대가 됨
-
a>0인 거를 놓쳐버려가지고 10분 낑낑거림 ㅅㅂ
-
우리 엄빠는 그런거 안 물어본다 어차피 안 생길거 아나 봐..
-
왜 아냐면 내가 작년에 알바 지원했다가 빠꾸먹음
-
대학은 붙었니? 수능 잘봤니? 앞으로 뭐해먹고 살 예정이니? 군대는? 여자친구는?
-
주관식 내면 안되나 바로 해결 아닌가
-
큐브는 일 안하는듯?? 10
저렇게 물어봐서 내가 진짜 엄청 고민해서, 질문자가 생각한 전제가 틀렸다고...
-
어젯밤엔 머했냐 이 인싸들아.
-
끄투 천덕 내기할사람 13
끄투 1000덕 내기하실분 있음? 상시 대기중
-
ㄹㅇ..
-
순천향대 임상병리, 경기대 관광경영 둘 다 안정~적정이라 아마 붙을 것 같은데...
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.