[알고리즘 이론] 순열과 조합, 그리고 중복순열과 중복조합

순열과 조합, 그리고 중복순열과 중복조합은 알고리즘 문제풀이에서 매우 자주 이용되고, 또 백트래킹이니 DFS니 어쩌구 저쩌구로 이어지는 것들이다. 그래서 코드로 구현하는 것까지는 다음에 하고, 오늘은 이론적인 내용을 예시와 함께 살짝 정리해두려고 한다.

---

우선 순열과 조합부터 이야기해보자.

이 둘은 중복을 허용하지 않으므로 모두 다른 숫자가 나온다는 공통점이 있다.

 

순열: 중복을 허용하지 않음. 순서가 의미 있음.

조합: 중복을 허용하지 않음. 순서가 의미 없음.

 

그리고 순서가 유의미한지의 여부가 둘의 가장 큰 차이다.

 

 

가령 주사위를 3번 던진다고 할 때

순열은

1 2 3

1 3 2

이 두 가지가 모두 나올 수 있다.

중복을 허용하지 않으므로 모두 다른 숫자가 나왔고, 순열은 순서가 유의미하므로 [1, 2, 3]과 [1, 3, 2]은 엄연히 다른 것이므로 둘 다 결과값이 될 수 있는 것이다. *순서가 유의미 하다는 말의 의미: 숫자의 구성이 같아도 숫자 위치가 다르면 다른 값으로 본다.

 

반면,

조합은

1 2 3과 1 3 2가

공존할 수 없다.

일단 중복을 허용하지 않으므로 모두 다른 숫자가 나온 것까지는 괜찮아보이지만, 조합은 순서가 무의미하므로 [1, 2, 3]이나 [1, 3, 2]를 같은 것으로 본다. *순서가 무의미 하다는 말의 의미: 숫자의 위치가 달라도 숫자 구성이 같으면 같은 값으로 본다.

 

 

예시를 살펴보자~

출처: [JUNGOL] 1169 : 주사위 던지기1

여기 주사위 던지기 문제가 있다. (문제 링크는 여기를 클릭)

 

출력 예시를 보면 결과값들 중 중복되는 숫자가 없이 모두 다른 숫자이므로 중복을 허용하지 않는 순열이나 조합 중 하나일 것이다. 그리고 좀 더 자세히 살펴보면 [1, 2, 3]과 [1, 3, 2]가 모두 결과에 포함되어 있는 것을 볼 수 있는데, 이 부분에서 순서가 유의미하다는 것을 알 수 있으므로 위 문제에서는 순열에 대한 알고리즘을 구현하라는 뜻이 되겠다.

 

---

 

다음은 중복을 허용하는 순열과 조합에 대해서 알아보자.

 

용어로는 중복순열과 중복조합이라고 한다.

위에서 공부한 순열과 조합의 개념에 중복을 허용한다는 개념만 끼얹으면 끝이다.

 

중복순열: 중복을 허용함. 순서가 의미 있음.

중복조합: 중복을 허용함. 순서가 의미 없음.

 

순열과 조합이 모두 다른 숫자로 구성되어야 했다면,

중복순열과 중복조합은 말 그대로 중복을 허용하기 때문에 같은 숫자로 구성되어도 된다.

 

 

이번에도 앞에서 든 예시와 똑같이 주사위를 3번 던진다고 하자.

중복순열의 경우에는

1 1 1

1 1 2

...

1 2 1

이런 식의 구성이 가능하다.

중복을 허용하면서도 순서가 유의미하기 때문에 1 1 2 와 1 2 1 가 다른 것으로 취급된다.

앞에서 이야기한 순열과 어떤 점이 다른지 차근차근 살펴보면 이해하기 쉽다.

 

한편,

중복조합의 경우에는

1 1 1

1 1 2

...

1 2 2

이런 식으로 구성된다.

중복순열과의 차이점은 1 1 2 과 1 2 1 을 같은 것으로 취급해서 1 2 1 는 건너뛰고 바로 1 2 2 로 간다.

이 또한 앞에서 이야기한 조합과 어떤 점이 다른지, 그리고 중복순열과는 또 어떤 점이 다른지 차근차근 살펴보면 이해가 쉬울 것이다.

 

---

 

개념을 얼추 정리했다면, 여기서 문제!👩‍🏫

출처: [JUNGOL] 1169 : 주사위 던지기1

 

여기 아까 봤던 주사위 던지기 문제가 있다. 위에서 본 것과 같은 문제다. (문제 링크는 여기를 클릭)

 

출력 예시를 보면 맨 처음은 1 1 1, 맨 끝은 6 6 6이니 중복을 허용하는 중복순열이나 중복조합 중 하나일 것이다. 중간을 살펴보자. 1 1 2와 1 2 1가 둘 다 존재한다. 그렇다면 순서에 의미를 부여하는 순열임을 알 수 있다. 따라서 이 문제는 중복순열을 구현하라는 의미가 될 것이다.

 

 

이번엔 또 다른 상황을 보자.

출처: [JUNGOL] 1169 : 주사위 던지기1

이번에도 같은 문제에서 살펴보자. (문제 링크는 여기를 클릭)

 

출력 예시를 보면 이번에도 맨 처음은 1 1 1, 맨 끝은 6 6 6이니 중복을 허용하는 중복순열이나 중복조합 중 하나일 것이다. 그럼 이제 중간을 살펴보자. 1 1 2가 있고, 1 1 6 다음에 1 2 1을 건너뛰고 1 2 2가 나왔다. 즉, 1 1 2와 1 2 1를 같은 것으로 본다는 뜻이다. 그렇다면 순서에는 아무런 의미를 부여하지 않고 숫자 구성만 본다는 뜻이므로 중복조합이 되겠다.

 

---

 

여기까지 순열과 조합, 그리고 중복순열과 중복조합까지 총정리를 마쳤다!

다음에는 이러한 개념을 코드로 옮겨보도록 하자. 그럼 20000👋