컴공 일기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를 선물하세요.
-
오빠 나한테 한 300만 줘봐
-
진짜모름
-
Big해서 ㅇㅈ 1
자신감도 대물이다
-
옯찐따 서럽다 에휴뇨이
-
세다 0
확실히 세다
-
한완수는 실전개념정리한걸오 알고있는데 한완기는 그냥 일반 기출문제집이랑 같은가요?
-
진짜 ㅇㅈ했음?? 18
엄..........
-
수식풀이 한정 평가원기출 중 난이도 압도적 원탑 같아요 오래전에 210921을...
-
여실히 느낀다
-
ㅋㅋㅋㅋㅋㅋ 0
ㅋㅋㅋㅋㅋㅋㅋ
-
레전드노 ㅋㅋ
-
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
-
개추 ㅋㅋ
-
수학의 정석 괜찮을까요?
-
넌ㅇㅈ이다
-
이미 엄청 밀려났네
-
키킼
-
다들 잘자요 0
굿 나잇
-
야추 인증함? 5
몇센치임?
-
여자분 키가 나랑 비슷한데 본인은 키 상관없다고 해도 자꾸 내가 주눅 듦 이거 어캄?
-
그치만 바로 벌점 먹고 산화당해준다면 해도 됨
-
흠
-
차단은 미리미리 5
후후
-
저격 아닙니다
-
수2 개념 5
예비고 2여서 수2 하려하는데 시발점으로 할까요? 시발점 보니까 80강이 넘어서...
-
여친 사귀면 바로 드러낼 계획인데 변태라고 까이려나 퓨ㅠ
-
wrc 재밌음? 1
함 입문해 볼까
-
대가리에소주꽂았니??
-
아니 이걸 떨쳐내라고는 하는데 그때 선택잘했으면 인생이 더 잘 풀렸을거라고 확신이...
-
어떤가요
-
님들 서브웨이 키오스크로 주문함 직접가서 주문함?
-
.
-
보고 싶어 대행 goat
-
대학생 팔로워수 ㅇㅈ 10
심지어 전적대도 다녔고 이제 2학년임…
-
닉추천 3
남고에 빡빡이인데 어울릴만한거 추천좀 ㄱㄱ
-
옯스타 깐다 1
다들 드루와 dm으로 옯닉이나 아이민 말해줘요 @p01nt0
-
바로 벌점100임?
-
틀딱 특 2
수능 본적있음
-
리트 가르친다는데 ㄹㅇ ㄹㅈㄷ
-
경영 붙을수 있을까요?? 749등임요
-
눈웃음 ㅇㅈ 16
키킼
-
보인다 보여 3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣶⣦⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⡿⡛⠝⡛...
-
지금 먹으면 아싸상태일때 먹을수잇음
-
배때지의 부피가 늘어났어
-
질문받습니다 6
궁금한 거 물어보면 웬만하면 답해드려요
-
한명빼고 두명은 구경만하고 하이라이트에대한 감상평을 남기고사라짐
-
알파 메일은 아니고 센타우루스자리 알파임
-
옯쀳삐들 굿나잇
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.