섹션 7 Recursive, Tree, Graph - 2. 재귀함수를 이용한 이진수 출력

📌 문제 설명

10진수 N이 주어졌을 때, 재귀함수를 이용해 이 수를 이진수로 출력하는 프로그램을 작성하시오.
단, Integer.toBinaryString() 같은 내장 함수는 사용하지 않는다.

---

📝 입력 & 출력

입력

• 첫 줄에 자연수 N이 주어진다.
• (1 ≤ N ≤ 1,000)

출력

• 재귀를 통해 N을 2진수로 변환하여 출력한다.

---

🔹 예제 입력 & 출력

예제 입력

 

11

 

예제 출력

1011

---

💡 해결 방법

10진수를 2진수로 변환하는 방식은 아래와 같다:

• N을 2로 나눈 몫을 재귀적으로 나누고,
• 나머지를 출력하면 가장 앞자리부터 2진수가 출력된다.

즉, N을 계속 2로 나누면서 DFS 깊이 들어가다가,
가장 작은 N까지 간 다음 재귀가 빠져나오면서 역순으로 나머지들이 출력됨.

---

💻 코드 구현 (Java)

package partRecursiveTreeGraph;

public class Problem2 {
	public void DFS(int n) {
		if (n == 0) return;
		else {
			DFS(n / 2); // 몫을 재귀적으로 나눔
			System.out.print(n % 2); // 나머지를 출력
		}
	}
	
	public static void main(String[] args) {
		Problem2 T = new Problem2();
		T.DFS(11); // 예제 테스트
	}
}

---

📖 코드 설명

1️⃣ 종료 조건

if (n == 0) return;

;

• N이 0이 되면 재귀 종료 (더 이상 나눌 수 없음)

---

2️⃣ 재귀 호출

DFS(n / 2);

• 몫을 재귀적으로 나누며 맨 앞 자리부터 먼저 도달

---

3️⃣ 출력

System.out.print(n % 2);

• 재귀 함수가 되돌아오면서 나머지를 출력
• 즉, 가장 앞자리부터 순서대로 출력됨

---

⏳ 시간 복잡도 분석

• 시간 복잡도: O(log N)
  → 2로 계속 나누기 때문에 최대 약 log₂(N) 번 호출됨

---

🧠 핵심 정리

• 재귀를 활용해 2진수 변환 시 → “먼저 몫 나눈 다음, 나머지 출력” 순서
• System.out.print(n % 2) 를 재귀 호출 이후에 실행해야 순서 맞게 출력됨
• 반복문 없이도, 재귀로 깔끔하게 2진수 변환 가능함

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런