컴공 일기264
게시글 주소: https://d.orbi.kr/00071280638
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를 선물하세요.
-
학벌좋고 외모좋고 성격좋은 사람들 꽤 있음 ㅇㅇ..
-
얘 내년에 입을 과잠을 내가 선택한다고 생각하니까 소홀히 할 수가 없음 ㅋㅋ
-
68 95 99.7 10
보통 신뢰구간 구할 때는 a=0.05를 쓰죠 점공에서는 예측 구간이라고도 합니다
-
제목 그대로 입니다. 문닫고라도 들어갈 수 있을까요?
-
대학을 더 잘가던데 ㄹㅇ루
-
기차에서 잠안올것같은데 유튜브영상보면 멀미나나여?? 기차별로안타봐서몰라여..
-
벌레 ㅈㄴ 싫음 5
그냥 순간 몸이 굳고 패닉 옴 극복불가능 극복한 사람 있음?
-
이거 꼭 해야해요? 책값 왤케 비쌈 그냥 개념 확인용같은데
-
그냥 국숭세단까지면 ok 너무 학벌을 많이 보고 싶지도 않기도하고....
-
연애하고 싶다 0
ㅏ
-
Z
-
삽 졸린데 8
애들 사이에서 못 자겟어
-
고2 모의고사때 쭉 1이었고 10월때 2등급(구차한 변명이지만 이때 1등급 비율이...
-
그냥 동문이랑 사귀는 게 깔끔할듯요 cc는 좀 아닌 것 같고 같은 사과대라면...?...
-
지금 노는거 조금씩 줄여서 대학 잘 가고 줄인거 수능 끝나고 순도 100퍼센트로 놀...
-
이거 떨어지면 1
하늘이 절 버렸다고 생각할게요..
-
매직키보드 실까 고민되는데…
-
더러운거 질색이에요;; 편의점 바퀴벌레때문에 관둠 쿠팡은 육체적으로 힘들어서 ..
-
마음에 들어요
-
궁금하네요
-
윤석열은 9수까지해서 사시패스를 했는데 조국은 사시패스도 안하고 설법 교수된거 ㅇㅇ
-
말안된다……
-
작년에 학원끝나고 걸어가고 있는데 길에서 사람보고 하수구에 뛰어드는 쥐봐서 충격먹었음
-
잠은 안 오네요
-
점공 업뎃완료 3
오늘 두명이나 들어왔네용 제발 최초합기원!!!
-
군필 03년생이고 이번에 휴학하고 공부하는데 수학개념을 많이 까먹어서 시발점부터...
-
롤케이크 맛있어 2
-
내일도 안좋으면 병원가야지..., 다들 굿밤되세요ㅜ
-
ㅅㅂ 팔만전자 되는 순간 다 팔아버린다
-
제2외국어 보는반이 분위기 좋다는 말도 있던데요
-
기차지나간당 6
부지런행
-
진심 트라우마 ㅜㅜ
-
개념강의가 가장 좋았고 판서좋아인간이라 더 잘 맞았나봐요 풀커리 탔고 수능날 아침에...
-
시ㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣ발 ㅠㅠㅠㅠㅠㅠ
-
되찾아 오자꾸나 가보자 가보자~
-
근데 성적도 재밌어질거같아서 못하겠음
-
초딩인가 중딩때 인형뽑기 오락실 잠깐 유행하고 그뒤로 싹 사라졌는데 디시 우후죽순생김
-
군대 가면 생각보다 내 학벌이 나쁜 게 아니어서 놀랐네요. 1
지방 국립대 문과 출신이라 속된 말로 하위 10%일 줄 알았는데 군대에서는 이것도...
-
슬슬 합격발표일을 위한 마음의 준비나 해둬야겠군요 설날이 코앞인데 부디 어깨 펴고...
-
어우 기하가 재밌는데
-
고등수학 개념서 2
기본정석이랑 숨마쿰라우데 중에 어떤게 더 낫나요? 완전 노베고 처음 시작하는 거예요
-
잇올 대체공휴일 4
잇올 대체공휴일이나 임시공휴일에 자율등원인가요?
-
이대남들 다 그런거 아나요? 배운다면 어케 배우죠..?
-
이번에 듣보잡 샀는데 step3 뉴테이션 부분은 건너뛰고 1,2만 해도 상관없죠?...
-
국어 대학전공서적공부법으로1등급쟁취 영어 영강공부법으로1등급쟁취 수탐만 판다 ㅇㅇ
-
만화책도 책임? 2
그럼 나도 어릴때 책 많이 읽었지 그리스 로마 신화 칭기즈칸 삼국지 역사 와이책...
와 이런 거 너무 좋은 거 같아요
:)
아 저도 코딩 공부하고 싶네요..나중에 원하는 학과 입학하면 이런 거 연재해보겠습니다
화이팅이에용!
님 코딩 문제 풀때 보면 바로 알고리즘짤때 뭐써야하는지 떠오르나요?
사실 난이도가 올라가면 올라갈수록, 시간이 걸리긴 합니다.
코딩테스트 한정해서 말씀드리면, 빈출 알고리즘(dp, greedy, knapsack, graph …)이라는 게 존재해서
유형을 반복적으로 접하다 보면 알 수 있죠.
생전 처음 보는 문제는 저도 버겁습니다.
답보면 맥락은 이해가 가는데 문제만 보고 이걸 떠올리는게 많이 빡세더라고요
경험 부족인 거죠. 그래서 가급적이면 유형 별 문제풀이가 도움이 될 때가 많아요.
오늘은 배낭문제, 내일은 dp, 모레는 greedy… 이런 식으로 유형 별로 반복을 하면서 연차가 쌓이면
“자기 주관”이 생기게 마련일 거예요.
자고로, 저도 그런 경험을 지금까지도 너무 많이 겪고 있는 중입니다.