컴공 일기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를 선물하세요.
-
이미지 메타 탑승 34
ㄱㄱ혓.
-
내 이미지좀 3
궁금해
-
나죽어
-
많이 늦나요??
-
덕코는 주고..
-
어케되려나
-
탈릅 전 무물보 4
한 번은 해보고 싶었어요 질문 없음 서러운거고 뭐...
-
저한테 많이들 쓰시던데 귀엽다는 뜻인가
-
1. 부산대 밀캠 인식이 어떤가요 2. 부산 내 대학이랑 비교해선 어느정도인가요...
-
25수능이 끝나고 당시 반응은 "물리학1 매우어렵다"이거였음 메가에서 등급컷...
-
뭔 뜻임뇨
-
고2 국어 학평 백분위는 3번 다 백분위 100 원점수 (89 100 98)이였고...
-
소신발언 0
솔직히 심찬우T 김상훈T 윤성훈T ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ ㆍ...
-
질질 5
흘리기
-
등록금으로 다 나갑니다( -4,400,000 ) 거지가 됩니다 다시 돈을 모읍니다 반복 하...
-
고2올라가고 인강들어본적이 없어서 그런데 수1 거의 노베입니다 내신으로 갈거고요...
-
시대 라이브반 3
동내 수학 학원 끊고 시대 라이브 들어보려고 하는데 들을만 한가요? 16만원 정도...
-
나의 이미지는? 11
써주세요
-
네.
-
내일 하루종일노는데 할게없음
-
나는 무엇을 하고 잇는 것인가... 책값과 패스값으로 얼마를 쓰고 잇는가...
-
미미미누 영상 보는데 입에서 침이 나와
-
어차피 대충 결과가 보이지만 어쨌든 입학처에서 보고싶다!!
-
ㅈㄴ 안 오름 나 댓글머신인데
-
[칼럼] 연세대학교 조기발표 일정에 대한 심층 분석 58
오르비 계정은 만에 하나 무언가 입시에 문제가 생길 것을 대비해 공론화 목적으로...
-
김준 풀이 3
김준 풀이 체화하려면 크포 문제 계속 반복해서 풀고 듣고 풀고 듣고 하는게 좋나요?...
-
그의여자친구는 먹던밥을뱉었다
-
반려는 또 뭐임
-
(서울대 합격 / 합격자인증)(스누라이프) 서울대 25학번 단톡방을 소개합니다. 0
안녕하세요. 서울대 커뮤니티 SNULife 오픈챗 준비팀입니다. 서울대 25학번...
-
뭔가 나의 거대한 주식같은 느낌임
-
현역이고 3등급이라 기출도 어렵게 읽힘 어디서 수특이 쉬운 편이라는 말 들은 것...
-
고냥 고렇던데
-
들어가볼까 흐흐
-
이게 다 노박사 때문이다
-
올해 다군 추합 0
외대 경영 추합 얼마나 돌까요?
-
ㅈ반고 0
ㅈ반여고에서 미적 계속 전교1등이었는데 작수 미적 4개 틀림 히히 ….
-
비행기랑 빙고ㅆㅅㅌㅊ
-
덕코 달달하네 4
-
윤측 "공수처, 탈취한 도장으로 문서 위조…초유 사태" 1
[이데일리 백주아 기자] 윤석열 대통령 변호인단이 고위공직자범죄수사처(공수처)와...
-
재종이라면 어딜 가야하고 기숙이면 어딜 가야하나요 추천 좀 해주세요 ㅜㅜ 정보가 하나도 없습니다
-
5인 1방 2
ㅋㅋㅋㅋ
-
보관은 어디다 해요? 냉장고? 실온?
-
저는 4월에 있는 세무사 1차를 치래요 한달에 한 과목씩 끝내야 할 판인데 ㅅㅂ
-
현역정시삼룡의 0
부럽다
-
일월 언어연구소입니다. 법학 지문을 어려워하는 학생들에게 도움이 되길 바랍니다.
-
인간 vs ,사람 14
뭘 더 좋아하시나여
-
???☠️☠️??????????????? 간절 간절 간절 제발 제발 제ㅂ발
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.