[SWEA][완전탐색] 순열, 조합, 부분집합

완전탐색(완전검색)

• 완전탐색이란? 문제의 해를 얻기 위해 가능한 모든 경우를 나열해보고 확인하는 기법.
• Brute_force 브루트포스라고 부르기도 한다.
• 모든 경우의 수가 적을 때 유용하다.(일반적으로 코테에서 100만 이하로 알고있다.)
• 이를 기반으로 그리디 기법이나 동적계획법을 이용해 효율적인 알고리즘을 찾을 수 있다.
• 문제 어떻게 풀지 모르겠으면 완탐으로 풀 것!

완전탐색과 조합적 문제

• 완전탐색은 곧 조합적 문제들(Combinatorial Problems) : 순열, 조합, 부분집합 에 대한 Brute-force 방법이다.

순열, 조합 그리고 부분집합

• 순열: 서로 다른 n개 중 r개를 택해 한 줄로 나열하는 것
  •  nPr
  • nPn = n!

• 조합: 서로 다른 n개 중 r개를 순서 없이 골라낸 것
  • nCr = nPr / r!
  • nC0 = 1, nCn = 1
  • nCr = nCn-r
  • nCr = n-1Cr + n-1Cr    ==> 조합의 재귀적 표현
    • 5C3 = 4C2 + 4C3 즉, 5C3은 5를 제외한 4C2의 경우의 수와 5를 제외한 4C3의 경우의 수를 합한 것이다.
    • 이를 활용한 알고리즘도 존재.

• 부분집합: 집합에 포함된 원소들을 선택하는 것
  • 자기자신과 공집합을 포함한 모든 집합의 수(Power set)의 개수는 2^n 개
  • 바이너리 카운팅 : 원소 수 N개의 비트열을 이용하여 모든 부분집합을 오름차순으로 생성
    • i 번째 비트값이 1이면 i 번째 원소가 포함되었음을 의미
    • (0 <= i <= N-1)

바이너리 카운팅을 통한 부분집합 생성코드

• 쉬프트 연산 활용
  • 1 << n : 비트를 1씩 왼쪽으로 n번 이동했다 = 2^n = 부분집합의 개수
  • i & (1 << j) : i의 j번째 비트가 1이다 = j번째 원소 출력

arr = [1, 2, 3, 4]
n = len(arr)                # n: 원소의 개수

for i in range(1 << n):     # 1 << n : 부분집합의 개수 (비트를 1씩 왼쪽으로 n번 이동, 즉 2^n)
    for j in range(n):      # 원소의 수만큼 비트를 비교
        if i & (1 << j):    # i의 j번째 비트가 1이면 j번째 원소 출력
            print(arr[j], end="")
    print()

	#공집합
1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234