[C/C++] 코드업 1920 : (재귀함수) 2진수 변환

문제풀이

10진수를 2진수로 바꾸는 내용임.

재귀 함수로 푸는 데, 쉽게 얘기해서 2로 나누는 작업을 계속해서 하는 것임.

그리고 쪼갤 수 있을 때까지 쪼갠 후, 그 후부터 하나씩 내려오면서 2로 나눈 나머지를 출력함.

이때 왜 마지막까지 쪼갠 후의 나머지 값부터 출력할까? 이는 가장 높은 수부터 작은수까지 출력하기 때문임.

 

예를 들어 33라고 해 보겠음. 이진수로 10 0001이 됨. 비트 5번과 0번.

33은 2로 5번 나눠짐. 6번째 나눌 땐 0이고.

2로 5번 나눴으면 이미 2^5라는 의미이고 그 값부터 출력해야 하는 것임.

이미 32라는 값을 10 0000으로 올려줬으니, 남은 숫자는 1만 남았음.

각각 2^4일 때 나머지 0 일 것이고, 2^3일 때 나머지 0일 것이고..... 마지막으로 2^0일 때 나머지 1이 됨.

 

따라서 DFS 함수 아래에 출력이 나오는 것은 최대한 DFS함수가 실행된 이후 마지막에서 출력하고자 함임. 이렇게 해야 가장 큰 수부터 출력되기 때문임.

 

아래 소스코드 이후에 좀 더 추가하겠음.

소스코드

#include <iostream>
#include <vector>
using namespace std;

int n;

void DFS(int x)
{
	if (x==0)
	{
		return;
	}
	else
	{
		DFS(x/2);
		cout<<x%2;
	}
}

int main()
{	
	cin>>n;
	if (n==0)
		cout<<0;
	else{
		DFS(n);
	}
	return 0;	
}

좀 더 부연하면 아래와 같이 동작함.

왜  cout 출력을 DFS함수 아래에 했는지가 중요함. 출력을 가장 마지막에 숨겨둔 것!

DFS함수는 아래와 같이 스택으로 저장되고, 계속 DFS 함수 내에서 DFS가 불리기 때문에 쌓이기만 함.

쭉 ~ 돌고 2로 최대한 나누어지고 DFS(0)은 아무 값 없이 리턴되고, 그 이후 DFS(1) Line 15번 이후가 실행됨. 이제부터 제대로 출력 시작되는 것임.

 

최대한 나누어질 때까지 cout 출력을 최대한 미룬 것.

 

n이 0일 때는 예외 처리 해 줌.

재귀함수 스택