컴공 일기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를 선물하세요.
-
미적 28에서 이미 한 번 털리고 돌아온거라 현장에서 하나하나 대입하며 귀납 추론할...
-
뭐 선택할까 ㅠ 24
1. 언매 미적 생명 생윤 2. 화작 미적 생명 생윤 3. 언매 확통 생명 생윤...
-
성인기념? 입학기념? 으로 지갑 팔찌 신발 가디건 목걸이 해서 740만원정도썼어욤...
-
241122<<이거 왜이렇게 고평가되는거임? 이거 난 현역때 걍 삼차함수 몇개...
-
나같은 케이스는 오르비 역사상 아무도 없을 듯 사귄 애는 오르비에서 첨 본 게...
-
문과분들께 여쭤봐요 11
1. 혹시 고2때 사탐 몇과목 하셨나요 2. 과탐 진로선택과목도 하셨나요 3....
-
특히 서고연 분들은 올탭 꼭 하셈 노동강도 0임 그냥
-
공수2-2 4
틀린거 있으면 말해주세용
-
사설에서 이정도 퀄리티인 문제 한개도못봄
-
1년동안 8명가르쳤습니다,, 시급이 일반 알바에 비해 많이높아서 좋긴한데 가르치는게...
-
공수2-1 8
매일마다는 아니어도 조금씩이라도 올리겠음
-
https://orbi.kr/00026573385 낼부터 전단지 바로 만들어볼려고요
-
위험한 발언 10
발이 얼면 위험합니다 는 장난이고 개인적인 사견으로는 23 25수능처럼 남은 26...
-
대가리에 들어오지도 않는 영어 꾸역꾸역 외우기 개같은 제2외 수능특강 벅벅 암기하기...
-
책상에 엎드려 자면서 짝녀랑 섹스하는 상상하는 꿈을 꿨음 문제는 잠꼬대를 ㅈㄴ 크게...
-
볼 때마다 이사람이 어디 썼더라 하고 헷갈림
-
얘전에 봉사할때 정말 많아야 30정도? 눈으로 봤을땐 25정도 이지 않을까 하는...
-
내인생계획 7
군대에서행정고시준비하기 일초에피셋합격 상초에2차합격 병장때최종합격 법률저널 인터뷰:...
-
사실상 공대잖아
-
탈릅. 4
형 간다.
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.