순조부 1 - 순열, 조합, 부분 집합

이 글에서는 알고리즘의 기초 중 하나인 순열, 조합, 부분 집합을 다루겠습니다.

순열, 조합, 부분 집합은 나중에가면 비슷하기 때문에 같은 문제를 서로 다른 방법으로도 풀 수 있는데

시간의 차이가 있기 때문에 문제를 파악해서 적절한 알고리즘을 사용할 수 있도록 개념을 정리해봅니다.

이 글에서는 각각의 기본 개념에 대해 다루며 자세한 내용은 다음 글에서 다루도록 하겠습니다.

 

1. 순열

• 정의 - 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열(순서있게)하는 것 

순열은 간단하게 말해 순서가 있는 집합이라 표현할 수 있습니다.

예를 들어 {1, 2, 3} 과 {2, 1, 3}은 내용물은 같지만 순서가 다르죠

이 경우 순열에서는 두 집합은 다른 집합입니다.

• 표현
  • nPr
    • nPr = n * (n-1) * (n-2) * … * (n-r+1)
    • nPn = n!
  • 중복순열은 nΠr로 표시
    • n^r

• 순열 사용 방식
  • 일반 재귀
  • 비트마스킹
  • Next Permutation(NP, 넥퍼)
    • 현 순열에서 사전 순으로 다음 순열 생성
    • 배열을 오름차순으로 정렬한 후 시작

2. 조합

• 정의 - 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

중복 조합은 순열과 비슷하지만 다르게 순서가 없는 집합입니다.

예를 들어 {1, 2, 3} 과 {2, 1, 3}은 같은 집합으로 취급합니다.

• 표현
  • nCr
    • nCr = n! / (n-r)!r!
    • nCr = n-1Cr-1 + n-1Cr
    • nC0 = 1
  • 중복조합은 nHr로 표시
    • n+r-1Cr

• 조합 사용 방식
  • 일반 재귀
  • Next Permutation(NP, 넥퍼)
    • n크기의 배열에 r개를 뒤쪽부터 1로 채우고 넥퍼를 진행하여 나온 결과를 기존 배열의 위치와 비교하면 조합

3. 부분 집합

• 정의 - 집합에 포함된 원소들을 선택하는 것

부분 집합은 공집합을 포함하여 해당 집합에서 선택할 수 있는 모든 경우의 수를 나타냅니다.

예를 들어 {1, 2, 3}의 부분 집합은 {∅}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 입니다.

• 부분 집합의 수
  • 공집합 포함하여 2^n

• 부분 집합 표현 방식
  • 일반 재귀
  • 바이너리 카운팅

고려 사항

• 순열은 n의 수가 10보다 클 경우 순열 문제가 아닐 가능성이 높음
  • 순열의 시간복잡도 n!
• 조합은 n=30, r=15일 경우 약 1억 5천
• 부분 집합은 n이 30일 경우
  • 2^20은 약 100만, 2^30은 약 10억

Java 기준 시간복잡도는 1억에 1초로 생각하시면 됩니다.