컴공 일기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를 선물하세요.
-
난몰랏음;
-
대한민국 제 18대 대통령 박 근 혜 (70, 전자공학과)
-
물1 생1 5
물리 올해 고딩때 하다버린 노베에서 4개월하고 40점 과탐무조건해야하면 뭐가낫나요...
-
지듣노 3
-
갤러리 탐방하고 있었는데 나옴 카페임
-
공주,,, 0
님을 석방하라
-
새벽라면 ㅊㅊ받음 23
어제 공복..
-
ㄷㄷ
-
? ??
-
김승리 레전드 0
https://youtu.be/1CcVy_j5FzY?si=OJexSD4y62lkB0N...
-
ㅌㅈㅇㄹ될수 있음?
-
좀 많은 편인죠..? 진짜 여러모로 불만족스럽네
-
오스트랄로피테쿠스를 소트르랄포티케수 이렇게 씀 손가락 개꼬임
-
과랑 학교중에 8
냥대 유기나노 서강 생명 냥대 안될거같긴 한데 만약에 된다면.. 학교는 냥댄데 과는...
-
??수능수학1등급 쉽던데 이런게 걍 어이가옶네 아오 ㅋㅋ
-
또 잘못되면 진짜 돌이킬 수 없을 것 같아서 무섭네… 이것이 하이리스크 하이리턴인가
-
보현이 누구심 17
ㅇㅁㅇ
-
보현 내 누나임 16
내 이름은 자현 엌ㅋㅋ
-
우훙하고 우나요?
-
헤으응 서울대 안간거라구는 외안헤..
-
정답이랑 해설 아래에
-
국민대 -> 연세대인데 재수하면서 깨달은 게 공부를 하든 뭐를 하든 뭔가를 이루기...
-
수능 물리학1 공부하는게 좋을까요 아니면 일반물리학 공부하는게 좋을까요.. 물리...
-
내일 치팅데이 5
본진이 출시한 전통주와 수육을 즐겨볼테야
-
그런 여자는 엄마밖에 없음
-
짧은 ㄱㅁ 10
인생업적
-
지금은 그럭저럭 친한데 학교 달라지면 멀어질 거 같은 친구가 있거든요 근데 멀어지긴...
-
모르겠다노
-
링크좀
-
교육위, 野주도로 '의대 증원 추진과정' 감사원 감사요구안 의결 2
(서울=연합뉴스) 안정훈 기자 = 국회 교육위원회는 17일 전체회의에서 정부의 의대...
-
목표는 ky지만 성한만 가도 만족하며 그만할 자신이 있는데 무휴반이 낫다는 생각도...
-
각 나왔다 2
도시락각 이제 진짜 나감
-
닮은꼴메타 0
-
잘 나가는 배우에다가 아가씨 영화도 히트쳐서 논란만 없으면 배우로 승승장구 했을건데...
-
애초에 교수가 젊은게 가능한가?
-
이상한 댓 달면 스나 다 떨어짐
-
빡구
-
원본 재구성 폰트는 Sandoll 설야(제목) / Sandoll 런던(과목 이름)...
-
냥대망함? 0
사시로 안보이면 망한건데
-
ㅇㅈ 14
키킥
-
아가 자야지 6
모두 굿밤
-
그리고 학번제임?? 바지 주머니에 손 넣고 다니면 혼남? ㄷㄷ
-
설윤 카리나 장원영 유나
-
나 왔엉 17
안뇽
-
정부기관 프린트는 안된다는데 서울대 면접용 수험표는 그럼 프린트 가능한거에요?
-
ㅇㅈ 10
-
메모장 어딘가에 숨어있던 2년 전 새벽감성 시를 꺼낼 시간이 왔구나... 대부분 시...
-
포장지에 묻은 소스 오겜 달고나마냥 핥아먹는게 ㄹㅇ 섹스인데 이게 보기에 좀 추함
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.