PostsSeriesLabsAlgo

백트래킹·구현

순열과 조합 만들기

가능한 경우를 빠짐없이

친구 셋이 한 줄로 섭니다. 서는 순서가 몇 가지일지 먼저 고르고, 앞자리부터 친구를 세워 서로 다른 순서를 빠짐없이 찾아 보세요.

친구 A·B·C가 한 줄로 서요. 서는 순서는 모두 몇 가지일까요?

  1. 1번째 자리
  2. 2번째 자리
  3. 3번째 자리

찾은 순서 0가지

  1. 아직 없어요
친구를 세운 횟수 0번

내 예상 가지 · 실제 6가지 → 달랐어요

3 × 2 × 1 = 6가지첫 자리 3가지 → 둘째 자리 2가지 → 셋째 자리 1가지. 친구를 세운 횟수는 번이었습니다. 헛걸음 없이 찾으면 15번입니다.

  • 자리마다 고른다 — 첫 자리는 3가지, 둘째 자리는 남은 2가지, 셋째 자리는 1가지였다
  • 다 서면 되돌아온다 — 한 칸 되돌려 다른 친구를 고르고, 막히면 또 한 칸 되돌렸다

자리마다 하나씩 고르다 끝에 닿으면 되돌아와 다른 것을 고르는 방법 = 백트래킹(backtracking). 앞에서 본 재귀가 이 일을 합니다.

  • 순서가 있는 줄 세우기 = 순열(permutation) — AB 와 BA 는 다른 순서다. 셋 중 둘을 세우면 6가지다
  • 순서 없이 뽑기만 하기 = 조합(combination) — AB 와 BA 는 같은 하나다. 셋 중 둘을 뽑으면 3가지다
친구 3명6가지
친구 10명3,628,800가지
친구 12명479,001,600가지
친구가 늘면 순서가 확 늘어납니다. 12명이면 1초에 1천만 번씩 세도 약 48초 걸립니다. 완전탐색 장에서 본 N!입니다.

이미 선 친구는 다시 세우지 않는다

  • 서 있는 친구는 못 누른다 — 방금 겪은 규칙이다. 코드에서는 used 가 이 표시다
  • 한 번씩, 빠짐없이 — 첫 자리가 A 인 순서를 다 찾은 뒤에야 B 로 넘어간다. 그래서 겹치지도 빠지지도 않는다
  • 되돌리면 표시도 지운다 — 뺀 친구는 다시 고를 수 있어야 한다. 표시를 지우지 않으면 한 가지만 찾고 끝난다

코드는 세우기, 들어가기, 되돌리기가 전부다

처음에는 permute(["A", "B", "C"], [], [False] * 3, result) 처럼 빈 줄, 빈 표시, 빈 결과를 넣어 부릅니다. 위에서 해 본 것과 같은 친구 셋입니다.

다음을 눌러 한 줄씩 넘겨 보세요. 모든 줄을 보여 주면 150스텝이 넘습니다. 그래서 친구를 세우고 부르는 10번 줄, 결과를 담은 뒤 돌아가는 4번 줄, 마지막 친구를 빼고 표시를 지우는 12번 줄만 켜집니다.

다음을 눌러 한 줄씩 넘겨 보세요

len(path) = 0 len(result) = 0

permute.py
  1. 1def permute(items, path, used, result):
  2. 2 if len(path) == len(items):
  3. 3 result.append(path[:])
  4. 4 return
  5. 5 for i in range(len(items)):
  6. 6 if used[i]:
  7. 7 continue
  8. 8 used[i] = True
  9. 9 path.append(items[i])
  10. 10 permute(items, path, used, result)
  11. 11 path.pop()
  12. 12 used[i] = False
0 / 37
  • used[i] = True · path.append(...) — 친구를 세운다. 8·9번 줄
  • permute(...) — 다음 자리로 들어간다. 자기 안에서 같은 일을 다시 부른다
  • path.pop() · used[i] = False — 마지막 친구를 빼고 표시를 지운다. 11·12번 줄

친구가 넷(A·B·C·D)이면 한 줄로 서는 순서는 모두 몇 가지일까요?

순열 만들기에서 틀리는 자리

  • result.append(path) 로 쓰면 — 결과가 전부 같은 줄 하나를 가리킨다. 끝나면 그 줄이 비어서 [[], [], [], [], [], []] 가 나온다. 복사해서 담는다 — path[:]
  • path.pop() 과 used[i] = False 를 빼면 — 되돌리지 못해서 첫 한 가지 ['A', 'B', 'C'] 만 나오고 끝난다
  • 같은 값이 섞이면 — [1, 1, 2] 는 6가지가 나오는데 서로 다른 건 3가지다. 같은 값끼리 자리를 바꾼 것도 따로 센다. set 에 담거나, 정렬한 뒤 같은 값을 건너뛴다
  • 실전에서는 한 줄 — itertools.permutations(items) 와 itertools.combinations(items, 2) 가 튜플을 하나씩 돌려준다. list() 로 감싸면 개수를 볼 수 있다. 10명의 360만 가지를 훑는 데 약 0.1초 걸렸다(Python 3.14, 컴퓨터마다 다르다)
  • n 이 크면 못 한다 — 12명은 4억 7,900만 가지라 1초에 1천만 번씩 세도 약 48초 걸린다. 순열로 모든 경우를 다 만드는 건 10명 이하일 때 쓴다

문제에서 이 말이 보이면

모든 순서(순열)·모든 뽑기(조합)n 이 작다(10 이하)경우를 빠짐없이 나열

다음 장에서는 서로 못 보게 퀸을 놓는 N-퀸을 봅니다. 놓다가 막히면 돌아오는 백트래킹을 그대로 씁니다.