[완전탐색] 순열과 조합 - 복습필요

순열(Permutation)

서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 혹은 나열하는 것

_nP_r로 표현되며 공식으로는 아래와 같이 나타낼 수 있다.

n! / (n-r)!

 

• DFS 트리와 체크리스트를 사용하는 방법이 가장 쉽다.
• 체크리스트는 말 그대로 내가 어디로 갔었는지를 기억해야 하기 때문에 임시로 사용하는 체크용 리스트
• 순열 알고리즘 코드는 그냥 외우는걸 추천

구현

코드

n = [1, 2, 3]
r = 2

result = [0] * r
checklist = [0] * len(n)

def DFS(L):
  if L == r:
    print(result)
  else:
    for i in range(len(n)):
      if checklist[i] == 0:
        result[L] = n[i]
        checklist[i] = 1
        DFS(L + 1)
        checklist[i] = 0

DFS(0)

 

조합(Combination)

서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관없게 선택하는 혹은 나열하는 것

nCr로 표현되며 공식으로는 순열 공식을 사용해 아래와 같이 표현할 수 있다.

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

• DFS 트리를 이용한다.
• 트리를 트래버스할 때 다음 시작점을 가지고 간다.
• 조합도 그냥 외우는걸 추천

구현

코드

n = [1, 2, 3]
r = 2

result = [0] * r

def DFS(L, BeginWith):
  if L == r:
    print(result)
  else:
    for i in range(BeginWith, len(n)):
      result[L] = n[i]
      DFS(L + 1, i + 1)

DFS(0, 0)

 

응용 문제

문제 1. 순열

숫자 0~9로 이루어진 4칸짜리 자물쇠의 비밀번호를 까먹었을 때

1. 서로 다른 숫자
2. 곱하거나 더해서 220이되는 숫자

위 조건을 만족하는 비밀번호 후보를 모두 고르시오

• 순서가 달라도 
  1 + 3 * 4  + 5 = 18
  5 * 3 + 4 + 1 = 20
  과 같이 결과가 달라지기 때문에 순열을 사용한다.
• 0 ~ 9로 이루어졌으니
  n = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
• 그 중 4개니까
  r = 4

코드

n = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
r = 4
sum = 220

result = [0] * r
checklist = [0] * len(n)

def calc(result):
  if result[0] + result[1] + result[2] + result[3] == sum:
    print(result[0], '+', result[1], '+', result[2], '+', result[3])

  if result[0] + result[1] + result[2] * result[3] == sum:
    print(result[0], '+', result[1], '+', result[2], '*', result[3])

  if result[0] + result[1] * result[2] + result[3] == sum:
    print(result[0], '+', result[1], '*', result[2], '+', result[3])

  if result[0] * result[1] + result[2] + result[3] == sum:
    print(result[0], '*', result[1], '+', result[2], '+', result[3])

  if result[0] * result[1] * result[2] + result[3] == sum:
    print(result[0], '*', result[1], '*', result[2], '+', result[3])

  if result[0] * result[1] + result[2] * result[3] == sum:
    print(result[0], '*', result[1], '+', result[2], '*', result[3])

  if result[0] + result[1] * result[2] * result[3] == sum:
    print(result[0], '+', result[1], '*', result[2], '*', result[3])

  if result[0] * result[1] * result[2] * result[3] == sum:
    print(result[0], '*', result[1], '*', result[2], '*', result[3])

def DFS(L):
  if L == r:
    # print(result)
    calc(result)
  else:
    for i in range(len(n)):
      if checklist[i] == 0:
        result[L] = n[i]
        checklist[i] = 1
        DFS(L + 1)
        checklist[i] = 0

DFS(0)

calc 함수가 상당히 더러운데 이것도 DFS를 통해 220이 되는 값을 찾게끔 만들 수 있겠지만

그 과정이 더 더럽고 복잡하기 때문에 때론 이렇게 단순 무식한 방법을 사용하는 것도 방법이 될 수 있다.

 

문제 2. 조합

백설공주와 일곱 난쟁이가 있었는데 어느 날 난쟁이가 9명이 되어 있었다.

각 난쟁이들의 키가 적힌 리스트 n = [20, 7, 23, 19, 10, 15, 25, 8, 13]이 주어질 때

원래 있던 7명의 키를 모두 더하면 100이 나온다고 한다면, 원래 있던 난쟁이들을 구해라

• n = [20, 7, 23, 19, 10, 15, 25, 8, 13]
• r = 7
• 순서 상관없이 뽑아서 조건을 맞추면 되기 때문에 조합을 사용한다.

구현

DFS로 끝에 도달했을 때 (1, 2, 3, 4, 5, 6, 7)에 대해 키를 모두 합친 값을 구한 뒤

비교 후 다시 다음 노드로 넘어갈 때 

(1, 2, 3, 4, 5, 6, 8)로 7 -> 8이 되니까 7의 키를 빼고 8의 키를 더해주는 과정을 생각해야한다.

코드

n = [20, 7, 23, 19, 10, 15, 25, 8, 13]
r = 7

result = [0] * r
sum = 0
total = 100

import sys

def DFS(L, BeginWith):
  global sum  # global로 선언하지 않으면 local 변수로 따로 계산
  if L == r:
    if sum == total:
      print(result)
      sys.exit(1)  # 찾는 순간 종료시켜버려 필요 이상의 연산을 제어할 수 있다.
  else:
    for i in range(BeginWith, len(n)):
      result[L] = n[i]
      sum = sum + n[i]
      DFS(L + 1, i + 1)
      sum = sum - n[i]

DFS(0, 0)

 

참고한 곳

https://youtu.be/78MHQ9s7kAc

https://youtu.be/HYKpunR1Nto

https://youtu.be/7L8OzmSUXWo