[알고리즘] 순환(Recursion) 08 - 중첩 반복문 대체하기

순환(Recursion) - 중첩 반복문 대체하기

알고리즘 문제해결 전략

Java코드

import java.util.ArrayList;

public class Test {

	public static void main(String[] args) {
		ArrayList<Integer> picked = new ArrayList<Integer>();
		pick(4, picked, 3);
	}

	// n : 전체 원소의 수
	// picked : 지금까지 고른 원소들의 번호
	// toPick : 더 고를 원소의 수
	// 일때 앞으로 toPik 개의 원소를 고르는 모든 방법을 출력

	public static void pick (int n, ArrayList<Integer> picked, int toPick) {
		// 베이스케이스 : 더 고를 원소가 없으면 고른 원소들을 출력
		if(toPick==0) {
			System.out.println("완료 : " +picked);
			return;
		}

		// 고를 수 있는 가장 작은 번호를 계산
		int smallest = picked.isEmpty() ? 0 : picked.get(picked.size()-1) +1;

		//이 단계에서 원소 하나를 고른다
		for (int i = smallest; i < n; i++) {
			picked.add(i);
			pick(n, picked, toPick-1);
			System.out.println(picked);
			picked.remove(picked.size()-1);
		}
	}
}

완료 : [0, 1, 2]
[0, 1, 2]
완료 : [0, 1, 3]
[0, 1, 3]
[0, 1]
완료 : [0, 2, 3]
[0, 2, 3]
[0, 2]
[0, 3]
[0]
완료 : [1, 2, 3]
[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]

생각

재귀는 아직도 복잡하고 어렵게 느껴진다
좀 더 연습이 필요

재귀에서 탈출하는 베이스 케이스를 생각!!
즉, ‘더이상 쪼개지지 않는 최소한의 작업’에 도달했을 때 답을 반환하는 조건문을 포함해야함

Logic

재귀는 완전탐색으로 구할 때 아주 좋은 방법
매 단계에서 하나의 원소를 추가, 그리고 만족하는 답을 출력
다시 이전으로 돌아가서 원소를 추가하는 식으로 진행
중첩 for문과 달리 n개의 원소 중 몇 개를 고르든지 사용할 수 있는 장점