순열, 조합 문제 풀이 (with. Python)

목차

1. 문제 이해하기

2. 실전 팁

3. itertools 라이브러리 사용

4. 자주 나오는 예제

---

1. 문제 이해하기

모든 경우의 수를 구해야 한다면, 아래 조건들에 따라 분류합니다.

 

• "중복이 허용되는가?"
  • 허용된다면: 중복 순열, 중복 조합
  • 허용되지 않는다면: 순열, 조합
• "순서가 중요한가?"
  • 순서 중요: 순열, 중복 순열
  • 순서 중요하지 않음: 조합, 중복 조합
• "정렬 조건이 있는가?"
  • 오름차순 → 조합
  • 비내림차순 → 중복 조합
• "결과의 조건이 명시되어 있는가?"
  • 예를 들어, 총합 제한, 특정 숫자 포함 여부 등의 조건이 있을 수 있음.
  • 이 조건을 함수 호출 조건에 포함

---

2. 실전 팁

순열/조합 문제는 보통 백트래킹을 사용합니다.

백트래킹에서 중요한 것은 

1. 종료 조건

2. 반복문 (n가지 중 1가지를 pick)

 

⭐ 추가적으로 결과 조건이나 특정 조건 등이 있다면 => 함수 호출 조건으로 추가해줍니다.

 

예를 들어, N개의 수에서 M개를 선택하는 조합문제일 때

https://www.acmicpc.net/problem/15650

1. 종료 조건 : M개를 선택

2. 반복문 (n가지 중 1가지를 pick)

  - 조건 1) 오름차순으로 선택해야함! ex)  (2, 1) <= 이거 안됨

  - 조건 2) 같은 수가 선택안됨! ex)  (1, 1) <= 이거 안됨

# 조합

n, m = map(int, input().split())

def sol(cur, visited, cnt):
    # 종료 조건: 카운트가 m에 도달
    if cnt == m:
        print(*visited)
        return

    # n가지 중 1가지를 pick
    for i in range(cur+1, n+1): # 반드시 오름 차순
        if i not in visited: # 같은 수 선택 안됨
            visited.append(i)
            sol(i, visited, cnt + 1)
            visited.pop()

sol(0,list(), 0)

 

---

3. itertools 라이브러리 사용

- permutations, combinations 에 's' 붙이는 거 잊지 않기!

 

1) 순열 

from itertools import permutations

n, m = 4, 2
for perm in permutations(range(1, n + 1), m):
    print(perm)

 

 

2) 조합

from itertools import combinations

n, m = 4, 2
for comb in combinations(range(1, n + 1), m):
    print(comb)

 

3) 중복 순열

from itertools import product

n, m = 4, 2
for prod in product(range(1, n + 1), repeat=m):
    print(prod)

 

4) 중복 조합

from itertools import combinations_with_replacement

n, m = 4, 2
for comb_wr in combinations_with_replacement(range(1, n + 1), m):
    print(comb_wr)

 

*참고

Sampling with replacement: 통계학 용어로 복원 추출

---

4. 자주 나오는 예제

1) 순열 문제

- 작업 스케줄링, 암호 해독, 경로 탐색(TSP)

 

2) 조합 문제

- 팀 구성, 부분 집합

 

3) 중복 순열

 - 주사위 굴리기, 반복이 허용되는 비밀번호

 

4) 중복 조합

  - 동전 교환