순열, 조합 만들기

순열 만드는 방법

1. 방문 배열을 안에

N = 5

def dfs(S, N, V, chosen):
    if S == N:
        print(chosen)
        return
    for i in range(N):
        if i not in V:
            dfs(S+1, N, V+[i], chosen + [i])

 

2. 방문 배열을 밖에

N = 5

V = [0 for _ in range(N)]
def dfs2(S, chosen):
    if S == N:
        print(chosen)
        return
    for i in range(N):
        if V[i]:
            continue
        V[i] = 1
        dfs2(S+1, chosen+[i])
        V[i] = 0
dfs2(0, [])

조합 만드는 방법

L = 5

def dfs(S, wishL, nowL, chosen):
    if S >= L:
        if nowL == wishL:
            print(chosen)
        return
    dfs(S+1, wishL, nowL+1, chosen+[S])
    dfs(S+1, wishL, nowL, chosen)

dfs(0, 2, 0, [])
dfs(0, 3, 0, [])
dfs(0, 4, 0, [])

느낀점

• 작년 8월에 쉽게 풀었던 순열, 조합 문제를 지금은 기억이 잘 안나는 걸 보고 블로그에 정리해야겠다고 생각했다.
• itertools 사용하는 방법도 나중에 정리해서 올릴 예정이지만 중요한건 itertools없이도 만들 수 있다는 것.
• 이거랑 비슷하게 정렬도 퀵정렬을 구현할 수 있는 것이 중요하다고 느꼈다. 다음에는 정렬도 블로그에 올릴 예정.