컴공 일기264
게시글 주소: https://ebsi.orbi.kr/00071280638
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를 선물하세요.
-
[관심좀] 4
p->q에서 p가 거짓이면 p->q가 참 이는 q의 원인이 p다. p가 없다 "q의...
-
꽤 있는데 몇 번 디엠만 하다가 지금은 딱히 연락 안 함
-
억울하면 진짜로 만들면 되지 않음?
-
진지하게 경한과 현금 10억을 바꿀의향이있다
-
ㅈㄴ 귀찮음
-
진짜 인생시발 2
생생우동 물거르다가 음쓰통에 면 다쏟았네ㅋㅋㅋ
-
대학도 못가고 돈도 없다 치킨 먹을 자유를 달라
-
오르새 선생님 개센스 들어보신 분? 들으시면서 유형서 하나 픗셧나요?
-
본인 좆된점 1
오르비에 내이름이랑 신상아는 같은 학년 고닉있는데 그사람이 이제 내 재정상태를 알아버림
-
대학공부할거야 실습도 하고
-
시드자체가 크신건가
-
울엄마 아빠 어렸을때 많이 남 그래서 나도 나는건가 아니 누구는 뭘 쳐먹어도 피부...
-
차피 휴학이니 상관없으려나
-
원서잘못쓴사람하고싶네
-
심지어 23살 군필... 안 그래도 우울한 마음에 기름 들이붓네
-
하 하향만 붙게 생겼네 ㅅㅂ
-
ㄹㅇ.
-
ㅈㄱㄴ
-
대학가니까 미움받을 용기 없이는 시작이 잘 안되네
-
프로포즈 ㅇㅈ 1
-
얻는 기쁨보다 잃는 두려움이 큰 쫄보니까 예금적금 이자 몇백원따리인 거 보면 아깝다
-
대전에 비상계엄령 선포
-
뀨뀨 16
뀨우
-
남들 다 하는데 왜 너만 안 해
-
펑
-
벗쉬크라크라크라 인더 헐 론니 헡 띵킹
-
과탐 뭐뭐하죠.. 11
화2생2 생2지1.. 아 설의냐 빅5냐인데 너무 고민되네요ㅠㅠ
-
결국 마음이 맞아야 함 11
근데 그런 사람이 없음
-
십알 1
나도 성불하고 말거야
-
생1지1할까 2
-
나만입는브랜드
-
내가 여자였어도 안함
-
삼킨 음식을 블랙홀이 다 먹어줄거 아니야..
-
모든수의 시작은 자연수 자연수의 시작은 1 따라서 모든수의 시작은 1 따라서 1은 제1원인의 위치
-
결혼하면 안되는 사람이라고 생각해서 비혼주의임 결혼함으로써 얻는 안정감<자유인 것 같아서
-
아무도 상처받지않는 세상을 만들자
-
100세까지 산다 치고 70년을 한사람이랑 살아야하는데.. 너무 질릴듯
-
스나 성공한듯 14
진학사 2칸 걍 스나했는데 예비2번뜸 도는 예비같은데 아직 붙은건이니지만 ㅈㄴ 햄복하네
-
이건 1월인데 4
여행다녀와서 매매한동안 못해서 꼬였음 펑
-
내 생각임
-
비문학 황이라고 자만해서 걍 문학만 마더텅으로 풀어보고 작수쳐봤는데 비문학 4틀...
-
강대 의대관 독서실비나 컨텐츠비까지 포함하면 달에 얼마정도 쓰셨나요 그리고 수능...
-
독해력이 얼마나 구리면;;
-
주변사람들이 대학 물어보는데 답을 어떻게해야할지 모르겠음 5
OO대학교 쓰긴했는데,, 아직 발표가 안나서 잘 모르겠어요 이렇게 해야하나여? 아마...
-
펑 투자 10년차 안건든 상품 없음 실친들, 가족들은 아무도모름 월평균은 그냥...
-
결혼까지 바라보는중이고 한 명은 이미 날짜까지 잡아놓음 나만 도태한남임
-
난 많이 안돌거같다고 보긴 함
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.