[알고리즘 코딩캠프 6일차] 순열, 조합, 중복순열, 중복조합, 백트래킹

제가 재학 중인 대학교에서 열린 `파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14)` 수업을 듣고 정리한 글입니다.

목차 :

• 순열과 조합
  • 순열
  • 조합
  • 중복순열
  • 중복조합
• 백트래킹

---

순열과 조합

직접 구현할 경우, 재귀를 사용해 구현.

순열과 조합의 직접 구현 2단계

1. 뽑고 싶은 만큼 뽑았다면 종료한다.
2. 그렇지 않다면, 재귀를 돌면서 수를 더 뽑는다.

(참고로, bfs와 달리 재귀 및 재귀를 사용한 dfs는 종료 조건이 action 부분에 있어도 ㄱㅊ. 오히려 코드 깔끔해짐.)

 

코테에선 대부분의 경우 `itertools 모듈` 내 함수들을 import해서 쓰게 됨.

왜냐? 그게 당연히 더 빠르기도 하고, 순열조합은 보통 문제의 과정으로서 등장하기에 알고리즘 자체에 변형을 가할 일은 별로 없기 때문.

---

순열

# 순열(permutations)

# 1. 재귀를 사용해 구현한 순열
def permutations(current):
    # 1. 뽑고 싶은 만큼 뽑았다면 종료한다.
    if len(current) == length:
        print(current)
        return
    # 2. 그렇지 않다면, 재귀를 돌면서 수를 더 뽑는다.
    for i in range(len(numbers)):
        if not visited[i]:
            visited[i] = True
            current.append(numbers[i])

            permutations(current)

            # 뽑은 놈들 취소하기
            visited[i] = False
            current.pop()

numbers = [1, 2, 3, 4]
length = 3
visited = [False] * len(numbers)
permutations([])


# 2. itertools 모듈의 permutations 라이브러리를 사용한 순열

from itertools import permutations

numbers = [1, 2, 3, 4]
length = 3

# (iterable, 숫자) -> iterable에서 숫자만큼 순열을 뽑아 줄게.
print(permutations(numbers, length))
for current in permutations(numbers, length):
    print(current)
    # 이 때, 확인할 수 있듯이 permutations 함수의 반환은
    # 튜플을 요소로 가지는 permutations 객체이기 때문에,
    # 저거 요소 내부를 조작하고 싶으면 map으로 list로 바꿔줘야 함.


# 그럼 강사님, 저거 라이브러리 쓰면 되지 않나요? 왜 직접 재귀로 구현?
# -> 저거 라이브러리 쓰면 모든 순열을 다 뽑아버림.
# 우리가 조건에 맞는 순열을 뽑고 싶으면, 1번을 직접 구현해서 조건을 추가해야 함.
# 근데, 그런 조건이 없으면, 2번을 쓰긴 함. 저게 더 빠르고 좋으니까.

# 보통, 순열 자체를 구하는 문제는 잘 안나오고,
# 문제의 일부로서 순열을 구하는 게 많이 나오기 때문에,
# 2번을 빠르게 쓰고 넘어가는 경우가 많음.

---

조합

# 조합(combinations)

# 1. 재귀를 사용해 구현한 조합
def combinations(current, start):
    if len(current) == length:
        print(current)
        return


    for i in range(start, len(numbers)):
        current.append(numbers[i])
        # 나 제외 다음 거(i + 1)부터 뽑기 시작함
        combinations(current, i + 1)
        # visited 처리는 필요 없지만, pop은 해줘야 다른 것들도 뽑을 수 있지.
        current.pop()

numbers = [1, 2, 3, 4]
length = 3

combinations([], 0)
# 여기서, 조합은 visited라는 개념이 필요가 없어짐.
# 왜냐하면, 나 다음 놈부터 뽑으면 애초에 다 첫 방문이거든.
# 왜냐하면, 2 뽑았으면 1로 갈 필요가 없음. 걔는 1에서 시작하는 놈에서 뽑혔을 거임.
# 즉, 2 뽑았으면 다음엔 3부터 뽑아가면 됨.

# 여기서, 2 뽑았으면 -> 이 부분을 위해 지금 나 자신에 대한 걸 start에 넣어줌.

# 2. itertools의 combinatinos

from itertools import combinations
numbers = [1, 2, 3, 4]
length = 3
for current in combinations(numbers, length):
    print(current)

---

중복순열

# 중복 순열(product)

# 1. 재귀를 사용해 구현한 중복 순열
def product(current):
    # 1. 뽑고 싶은 만큼 뽑았다면 종료한다.
    if len(current) == length:
        print(current)
        return
    # 2. 그렇지 않다면, 재귀를 돌면서 수를 더 뽑는다.
    for i in range(len(numbers)):
        # visited[i] = True 중복순열에선 visited를 모두 없애야함! 1 다음 1이 올 수 있어야 함
        current.append(numbers[i])
        product(current)
        # 뽑은 놈들 취소하기
        current.pop()

numbers = [1, 2, 3, 4]
length = 3
product([])


# 2. itertools 모듈의 product 라이브러리를 사용한 순열

from itertools import product

numbers = [1, 2, 3, 4]
length = 3

# (iterable, repeat = 숫자) -> iterable에서 숫자만큼 순열을 뽑아 줄게.
print(product(numbers, repeat = length))
for current in product(numbers, repeat = length):
    print(current)
# 얘는 repeat 써야 한다는 거에 주의!!

---

중복조합

# 중복 조합(combinations with replacement)

# 1. 재귀를 사용한 중복 조합
def combinations_with_replacement(current, start):
    if len(current) == length:
        print(current)
        return


    for i in range(start, len(numbers)):
        current.append(numbers[i])
        # 나 포함(i)부터 뽑기 시작함
        combinations_with_replacement(current, i)
        # visited 처리는 필요 없지만, pop은 해줘야 다른 것들도 뽑을 수 있지.
        current.pop()

numbers = [1, 2, 3, 4]
length = 3

combinations_with_replacement([], 0)


# 2. itertools의 combinations_with_replacement

from itertools import combinations_with_replacement
numbers = [1, 2, 3, 4]
length = 3
for current in combinations_with_replacement(numbers, length):
    print(current)

---

백트래킹

`백트래킹(Backtracking)`이란, 모든 경우에 대해 해를 찾는 도중, 그 해가 유망하지 않다고 판단되면 다시 되돌아가서(Backtrack) 다른 해를 찾아가는 방법이다.

`유망하다(Promising)`는 것은 어떤 경우가 해가 될 가능성이 있다는 것을 의미한다. 반대로 해가 될 가능성이 없다면 유망하지 않다고 한다.

 

백트래킹은 DFS를 이용해 모든 경우의 수를 탐색할 때 효율성을 도모하기 위해 많이 사용한다.

기본적으로 DFS는 완전탐색으로써, 어떤 경우의 유망성에 상관없이 모든 경우의 수를 탐색한다. 따라서 답이 될 가능성이 전혀 없는 경우(유망하지 않은 경우)도 전부 탐색을 하게된다.

 

유망하지 않은 선택지를 더 이상 탐색하지 않고 정답 후보에서 지워버리는 것을 가지치기(Pruning)한다고 말한다.

정리하면 백트래킹은 DFS를 이용한 완전탐색에서 모든 경우를 탐색하지 않고, 유망하지 않은 경우를 미리 가지치기하여 시간적 효율을 도모하는 방법이다.

 

`외판원 순회2 문제` 보면, 이 백트래킹이 명확히 드러나있음.

사실 백트래킹은 일종의 방법론 내지 기술 같은거지, 알고리즘이라고 하기는 애매함.

그냥 답이 나오면 리턴해버리는 것도 어떻게 보면 백트래킹이라고 할 수 있음.

---

과제 및 풀이 정리

- 순열, 조합, 중복 순열, 중복 조합

- 외판원 순회 2

- 로또

- 로마 숫자 만들기

- N-Rook Problem

- N-Rook Problem2