https://www.acmicpc.net/problem/10829
10829번: 이진수 변환
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000)
www.acmicpc.net
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
long long recursion(long long N) {
long long temp;
if (N == 0)
return 0;
else {
temp = N % 2;
N /= 2;
recursion(N);
printf("%lld", temp);
}
}
int main() {
long long N;
scanf("%lld", &N);
recursion(N);
}
우선 문제에서 제시된 자연수 N의 범위가 대략 21억의 값의 범위를 가지는 int나 42억의 값의 범위를 가지는 unsigned int를 초과한 100조였기 때문에, long long 자료형을 선택해야 합니다.
10진수를 2진수로 변환하는 과정을 알아봅시다.
예제에 주어진 53을 예시로 들어보겠습니다.
53은 실수이며 '정수'이기 때문에 몫이 0이 될 때 까지 변환하려는 기수로 나누면서 각 단계마다 나오는 나머지를 나열하는 방식으로 구할 수 있습니다.
이때 가장 먼저 얻은 나머지는 변환된 진수의 가장 오른쪽 자리에 가장 마지막에 얻은 나머지는 변환된 진수의 가장 왼쪽 자리에 위치하게 됩니다.
즉 나머지가 구해지는 순서의 역순으로 배치됩니다. 위의 53의 경우에는 101011이 아닌 110101이 됩니다.
'2로 나눈다'라는 동작이 반복되므로, 재귀 호출을 통해 풀고자 하였습니다.
재귀를 풀 때 항상 명심해야하는 것은 크게 2가지 입니다.
1. 재귀의 종료시점 (조건문을 이용)
2. 큰 문제를 세부 문제로 분리하여 생각하기
위 문제에서 재귀의 종료 시점은 몫이 0이 되는 순간입니다.
2로 나누어 나머지를 출력하는 것은 좋으나, 어떻게 역순으로 출력 할 수 있는가에 대해서
반환값을 이용하는 것이 아닌, 재귀의 특성 즉, 함수 호출이 스택 프레임에 쌓이는 성질을 이용하여
함수 호출을 먼저 수행한 후 나머지를 나중에 출력하는 방식으로 구성하였습니다.
'Baekjoon' 카테고리의 다른 글
[C++]백준 10093번: 숫자 (0) | 2024.02.06 |
---|---|
[C++]백준 2309번: 일곱 난쟁이 (1) | 2024.02.05 |
[C] 백준 2750번 : 수 정렬하기 (1) | 2023.02.02 |
[C] 백준 2563번 : 색종이 (0) | 2023.02.01 |
[C] 백준 2090번 : 골드바흐의 추측 (2) | 2023.01.31 |