[알고리즘] Permutation 부수기 : 백준 문제 세트로 연습하자

이번 포스팅에서는 파이썬의 itertools 모듈을 활용하여 순열과 조합 문제를 해결하는 방법을 다룹니다. 특히, 백준의 다양한 문제를 예시로 들어 설명하겠습니다. 대부분 위 모듈을 이용해서 풀 수 있지만 특정 문제는 순열 자체에 대한 문제로 itertools를 이용하지 않는 문제도 포함되어 있습니다. Ex) 10972번

1. 순열의 이해와 활용

순열(Permutation)은 순서를 고려하여 배열하는 방법입니다. 예를 들어, [1, 2, 3]의 순열은 다음과 같습니다:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

백준 문제 10972번 "다음 순열"을 통해 순열의 기본 개념을 살펴보겠습니다. 이 문제는 주어진 순열의 다음 순열을 찾는 것입니다. 다만 이 문제는 수학적으로 이해는 아직 못해서 일단은 그냥 외웠습니다... 그러면 안되는데... 일단은 잘 이해가 안가니 넘어가도록 하겠습니다. 

눈치...

 

문제 해결 코드:

def next_permutation(arr):
    n = len(arr)
    i = n - 1
    
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    
    if i <= 0:
        return False
    
    j = n - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
        
    arr[i - 1], arr[j] = arr[j], arr[i - 1]
    arr[i:] = arr[i:][::-1]
    return True

n = int(input())
arr = list(map(int, input().split()))

if next_permutation(arr):
    print(' '.join(map(str, arr)))
else:
    print(-1)

 

2. 조합의 이해와 활용

조합(Combination)은 순서를 고려하지 않고 배열하는 방법입니다. 예를 들어, [1, 2, 3]에서 2개를 선택하는 조합은 다음과 같습니다:

• [1, 2]
• [1, 3]
• [2, 3]

백준 문제 6603번 "로또"는 주어진 숫자 중 6개를 선택하는 조합을 출력하는 문제입니다.

문제 해결 코드:

 

import sys
from itertools import combinations

input = sys.stdin.read

def solve():
    input_data = input().strip().split("\n")
    results = []
    
    for line in input_data:
        if line == "0":
            break
        nums = list(map(int, line.split()))
        k = nums[0]
        s = nums[1:]
        
        comb = combinations(s, 6)
        for c in comb:
            results.append(" ".join(map(str, c)))
        results.append("")  # 줄 간격을 위해 빈 줄 추가
    
    print("\n".join(results).strip())

solve()

3. 외판원 문제: 순열의 응용

외판원 문제는 순열을 활용하여 모든 경로를 탐색하는 문제입니다. 백준 문제 10971번 "외판원 순회 2"는 최소 비용으로 모든 도시를 방문하는 문제입니다. 너무 유명한 문제죠. 알고 있었던 문제이지만 이렇게 쉽게 풀리는 줄은 몰랐습니다. 막상 해결하고 보니 정말 쉬운 코드였어요.

 

문제 해결 코드:

 

import sys
from itertools import permutations

input = sys.stdin.read

def get_cost(per, board):
    total_cost = 0
    n = len(per)
    
    for i in range(n - 1):
        cost = board[per[i]][per[i + 1]]
        if cost == 0:
            return float('inf')
        total_cost += cost
    
    cost = board[per[-1]][per[0]]
    if cost == 0:
        return float('inf')
    total_cost += cost
    
    return total_cost

def solve(n, board):
    arr = range(n)
    possible_per = permutations(arr)
    min_value = float("inf")
    
    for per in possible_per:
        cost = get_cost(per, board)
        if cost < min_value:
            min_value = cost
    
    print(min_value)
    
input_data = input().strip().split()
n = int(input_data[0])
index = 1
board = []

for _ in range(n):
    board.append(list(map(int, input_data[index:index + n])))
    index += n

solve(n, board)

결론

순열과 조합은 생각보다 많은 문제를 해결하는 데 중요한 도구입니다. itertools 모듈을 사용하면 이를 쉽게 구현할 수 있고 저는 codeplus의 백준 문제를 통해 순열에 관한 내용을 연속적으로 학습할 수 있었습니다.

 

참고 : https://www.acmicpc.net/workbook/view/9374