재귀 - 순열, 조합

재귀를 활용한 순열.. 조합.. 매번 헷갈리고 어렵다.

 

먼저 수학적 개념에 대해서 알아보고 프로그래밍을 도입하자.

 

순열

n개 중 r개를 순서대로 나열하는 방법이다.

ex) 3개의 숫자 중 2개를 뽑아 순서대로 나열하면?  [1, 2, 3]에서 2개를 뽑아서 나열하라

=> [1, 2] [1, 3], [2, 1], [2,3], [3,1] [3, 2]

 

수학적 정의

nPr = n!/(n-r)! = n*n-1*...*(n-r+1)

quiz) 아침 점심 저녁의 식단을 정하려고 한다. 후보지로는 한식, 중식, 양식, 일식, 분식이 있다. 이 후보지로 만들 수 있는 식단의 경우의 수는? (한식-양식-중식,   중식-양식-한식 순서는 엄연히 다른 식단이다) sol)  5개 중 3개를 순서 있이 뽑으면 5P3 이므로 5*4*3 = 60가지의 경우의 수가 나온다. 60가지의 식단을 즐길 수 있다!

 

 

조합

n개 중 r개를 순서를 고려하지 않고 뽑는 경우의 수 1,2 = 2,1 은 같다

ex) 3개의 숫자중 2개를 순서 상관없이 뽑아라.  [1, 2, 3]에서 2개를 순서 상관없이 뽑아라.

=> [1, 2] [1, 3], [2, 3]

 

수학적 정의

nCr = n!/(n-r)!*r! = nPr/r!

+) nCr = nCn-r   ,  nCr = n-1Cr-1 + n-1Cr

 

quiz) 나는 새로 커피가게를 오픈했다. 메뉴를 만드는 도중 세트메뉴를 만들면 사람들이 많이 찾을 것 같았다. 제공하는 커피 종류는 아메리카노, 카페라테, 쑥 라테 총 3가지다. 샌드위치는 미니 사이즈로 과테말라 샌드위치, 에그 마요, 트리플 햄 샌드위치, 양상추 범벅 샌드위치 총 4가지다. 각 세트 당 커피 하나, 샌드위치는 2개씩 해서 세트메뉴를 만든다면 총 몇 가지의 세트 메뉴를 만들 수 있을까? sol)  3 * 4C2 = 18가지의 세트를 만들 수 있다. 샌드위치는 [에그마요, 트리플 햄]이나 [트리플 햄, 에그 마요]나 순서는 상관없으므로 조합을 사용하면 된다.

 

중복순열, 중복조합

자기 자신을 뽑는지 여부다.

 

재귀

재귀는 자기 자신을 호출한다는 것이다. 자기 자신을 호출할 때 변화 없이 계속 자기 자신을 호출한다면 무한적으로 자기 자신을 호출하게 될 것이다.

 

아래 코드는 변화 없이 자기 자신을 계속 호출하므로 결국엔 hello를 출력하다가 스택오버플로우가 발생할 것이다.

 

class Recursion {
	public static void main() {
		func();
	}

	private static void func() {
		System.out.println("hello");
        
		func();
	}
}

그렇기에 변화를 주면서 재귀 호출을 하고 종료 조건을 주어야 한다. 여기서 변화는 매개 변수에 변화를 주거나 재귀 함수가 참조하는 값을 변화시키는 것이다.

 

class Recursion {
	public static void main() {
		int n = 4;
		func(n);
	}

	private static void func(int k) {
		// 종료 조건
		if (k <= 0) return;
        
		System.out.println("hello");

		// 매개 변수가 변함
		func(k-1);
	}
}

위 소스를 보면 재귀 호출을 매개 변수 값에 변화를 주면서 호출하며 종료 조건이 존재한다.

 

재귀를 사용하는 방식과 스택에 할 일을 보관하면서 분기를 직접 처리하는 방식은 사실 동일하다.

시스템 호출 스택을 사용할 것인가 별도의 명시적인 스택을 사용할 것이냐의 차이이다. 이렇게 for문의 사용 없이 재귀 호출을 통해 구현할 수 있다.

재귀는 보통 문제를 어떻게 풀어야 할지의 느낌보다 문제 정의 자체를 코드로 표시한다.
즉, 재귀는 정의를 이해하려고 하면 된다.

위 코드의 func(int k)는

k <= 0 일 때 return

k > 0 일 때 hello world를 출력하며 func(k-1) 호출

 

재귀는 크게 보면 반복과 단계로 이루어져 있다. 반복은 후보를 선택한다고 보면 되고 단계는 후보를 선택하고 다음 단계를 재귀 호출한다고 보면 된다.

 

[1, 2, 3]의 배열이 있고 2가지의 수를 뽑아 순서 있게 나열을 해본다고 하자.

1단계에서는 첫 번째 오는 수를 결정한다. 결정할 때 1,2,3을 선택하는 것을 반복으로 돌리며, 그리고 그 단계 안에서 다음 단계를 재귀 호출을 통해 넘어간다.

 

2가지 수를 뽑기 때문에 2단계가 있으며, 각 단계는 3번씩 반복한다.

 

1단계: [1]                     [2]                   [3]     

2단계 [1, 2] [1,3]          [2,1] [2,3]        [3,1] [3, 2]

 

정의로 보자면

단계 == 2 ) 일 때 문자열 출력

단계 < 2  ) 이번 단계 문자를 정하고 다음 단계를 호출

 

자 그러면 이제 프로그래밍적으로 접근하여 보자... 계속

 

 

 

 

 

참고

https://www.youtube.com/watch?v=MjW10t9ppok