순열(Permutation)과 조합(Combination)은 어떻게 구분할까?

순열(Permutation)과 조합(Combination)

순열(Permutation)

https://ichijeochi.tistory.com/9?category=1012068 

순열 (Permutation)

 

조합(Combination)

https://ichijeochi.tistory.com/389?category=1012068 

조합 (Combination)

 

❓ 순열과 조합은 어떻게 구분할까?

알고리즘을 풀다보면 "조합"으로 풀어야하는 문제인지, "순열"로 풀어야하는 문제인지 헷갈릴때가 종종 있는데

오늘은 이를 어떻게 구분하면 좋을지에 대해 간단하게 얘기해보고자 한다.

 

나는 둘의 문제를 구분할 때 어떠한 원소를 뽑을 때 해당 원소가 다음으로 뽑힐 원소에게 영향을 주는지를 생각해본다.

즉, 뽑는 순서에 따라 결과가 달라진다면 순열이고 뽑는 순서가 달라도 결과는 달라지지 않는다면 조합이다.

 

조금 더 쉽게 이해할 수 있도록 예시를 들어보자.

1️⃣ 반에서 임원선정을 위한 제비뽑기 시, 후보 5명(짱구, 철수, 유리, 맹구, 훈이)으로 만들 수 있는 임원단의 경우의 수

      (단, 임원은 반장과 부반장 각 1명씩이며 가장 먼정 뽑힌 사람은 반장, 그 다음으로 뽑힌 사람은 부반장임)

      👉 이 경우 짱구가 제비뽑기로 임원단 안에 들어도 뽑힌 순서에 따라 반장이 될수도, 부반장이 될 수도 있어 결과가

            달라지므로 순열 예시

2️⃣ 반에서 청소당번 선정을 위한 제비뽑기 시, 후보 5명(짱구, 철수, 유리, 맹구, 훈이)으로 만들 수 있는 청소당번의 경우의

      수 (단, 청소당번은 2명이며, 뽑혔을 때 하는 일은 같음)

      👉 이 경우 짱구가 제비뽑기로 먼저 뽑히든, 두번째로 뽑히든 청소당번이라는 결과는 변하지 않으며 다른 1명과 역할

            의 차이도 없으므로 조합 예시

 

이렇게 쉬운 예시를 들어서 생각을 해보면 순열과 조합의 차이를 조금은 알 수 있다.

물론, 순열과 조합을 이해한다고 알고리즘을 풀 때 무조건 쉽다는 것은 아니고 두 경우 모두 재귀를 이용하여 푸는 경우가 많기 때문에 최대한 많은 문제들을 풀어보며 연습을 해보는 것이 좋다.

(순열과 조합의 개념과 푸는 법은 위의 링크를 통해 확인🌱)