컴공 일기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를 선물하세요.
-
뉴런vs아이디어 5
둘중 하나 한후에 n제 할건데 뭐가 나을까요??
-
윈터 다니면서 수학 단과 두개(둘다 공통,하나는 개념이고 하나는 기출) 듣고있는데요...
-
오르비언 mbti 조사 18
댓글로 적어주셈뇨 ㄱㄱ혓.
-
심심한 2
나
-
도시락때매 기분좋아져서... 도시락이 이렇게 위험합니다 괜히 독립 운동가분들이...
-
반갑습니다
-
진짜 이제 1주일 내내 수학만 한다... 뉴런 수분감 딱대ㅐ..
-
좀 자라 20
나야
-
5랜만 6
ㅎㅇ
-
오르비 레전드였던 사건 12
야 너 전화받아! 이거 이제 나만 아는건가..
-
가천대는 금융 빅데이터 학과 이고 가톨릭은 자유전공 인데 뭐가 나을까요??
-
응애 0
나 졸려
-
자러갈게요 다들ㅂㅂ
-
2배속으로 안들으면 답답한데 ADHD인가? 물론 수학같은건 2배속으로들으면서...
-
난 여자 보면 눈이 그냥 가슴부터 보게 됨 특별히 큰 것도 아니고 그냥 진짜 아무...
-
이거 어떰? 5
가격 ㅈㄴ싸고 리뷰가 ㅈㄴ많아서 괜찮은거 같은데 난 신발 285신는데 280사이즈 맞으려나
-
다들잘자요 8
않영
-
화학수업 오면 나 잇다. 점심같이 먹을 사람 구한다.
-
빼뺘로 먹는 중
-
내신으로 입학한 부류들은 나 000에게 말을 걸지 말길 바란다. 논술과 정시만이...
-
셈퍼 점공계산기 4
예상실제등수가 뭔지 아시는 분? 2700은 너무 말이 안 되는 숫자 같은데...
-
님들 언제 주무세요 13
전 3시전엔 무조건 잘 거 같아요 !!! ㅎㅎ
-
저왜프사못바꿔요 4
어서바꿈
-
나 반수한다니까 작년 컨텐츠 나눔해주셨던 고마웠던 교양 같은 조 분들 꼭 올해는...
-
다리 vs 가슴 2
어느 부위가 좋으신가요?
-
174.5정도인가 78(밥먹으면 79,80 왔다거림) 몸무게 어디까지 빼야 비만이 아니게돼?
-
컴활 2급 0
따보신분 있너요?
-
맛좋은스팀겜추천 6
해주세요
-
나처럼 순수한 사람은 메타 이럴때마다 손 벌벌 떨면서 눈물을 흘려야 한다구요 ㅜㅜ
-
사랑과평화우정 2
초5부터 쓰던 닉
-
윤석열 대통령 탄핵소추안 vs 윤석열 대통령 소추탄핵안 5
뭐가 더 나아보임?
-
흐우우움
-
원서 쓸 때는 쫄아서 이거 11상향 11광탈각이 아닌가 싶었는데, 돌아보니 1 상향...
-
개학해야 고3이지
-
퍼리가 안꼴리면 비뇨기과에 가봐야함
-
프로세카하는사람 8
-
**감상 전 좋아요와 팔로우는 작성자에게 큰 힘이 됩니다!! 안녕하세요!! 오늘은...
-
슬더스하는사람 19
친구하잣
-
무물보 23
선넘 ㄱㄴ 솔짓히 아무것도 없으면 쫌 슬플 것 같아요
-
진짜 한심한 생각 11
오야스미 << 이거 oh 야스 me 라고밖에 생각이 안남
-
다 자러가시는듯
-
반말할게 그냥 12
난 고등학교 최고참이잖아 ㅇㅇ
-
인생이 걍 4
개 큰 똥덩어리다 씨발
-
보는데 재수생 성적표 하나씩 공개하는 내용이였는데 언매 미적분 98 99 이래서 와...
-
무물보 8
선넘질ㄱㄴ
-
야!! 12
잘자!!!!!
-
강대쿼터 vs 의대관 근데 의대관 성적순전형은 어느정도까지 붙나여? 거기기준으로...
-
나랑 저나할사람 7
심심한데 전화할사람구함....
-
173/58/17이고요 바텀을 선호해요
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.