[파이썬 python] 순열, 조합 코드로 구현하기

## 코딩테스트에서 자주 출제가 되는 순열과 조합문제를 기억하자!

 

# 순열 구현하기 (1) - itertools 모듈 사용하기

# 코딩테스트에서 가장 효율적인 방법이다 (간단하고 빠르다)

 

# <코드>

# 목적: 한 개의 리스트에서 모든 순열을 구하기

# 입력: 요소들로 채워진 리스트 하나

import itertools

l = ['a', 'b', 'c']

# 리스트를 반환하도록 하였슴
print(list(map(list, itertools.permutations(l))))

#결과값: [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]

 

 

# 순열 구현하기 (2) - DFS 사용하기

# itertools를 사용하지 못할 때 구현할 수 있다

 

# <코드>

# 목적: 한 개의 리스트에서 모든 순열을 구하기

# 입력: 요소들로 채워진 리스트 하나

# DFS로 모든 경우의 수를 하나씩 구하되, 각 경우의 수에 같은 요소가 없도록 함으로써 순열을 구현한다

l = ['a', 'b', 'c']
visited = [0 for _ in range(len(l))]
answer = []

def dfs(cnt, list):
    if cnt == len(l):
        answer.append(list[:])
        return

    for i, val in enumerate(l):
        # 만약 방문했다면 건너 뛰기(순열을 위함)
        if visited[i] == 1:
            continue
        # 현재까지의 list에 값을 추가하고, 방문 표시하기
        list.append(val)
        visited[i] = 1

        dfs(cnt+1, list)
        # 방금 전 list에 추가한 값과 방문 한 것을 되돌려주기
        list.pop()
        visited[i] = 0


dfs(0, [])
print(answer)

#결과값 : [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]

 

 

# 조합 구현하기 (1) - itertools 사용하기

#역시나 가장 빠르고 효율적이다

 

#<코드>

# 목적: 한 개의 리스트에서 r개의 조합 구하기

# 입력: nCr 에서 n과 r

import itertools

l = ['a', 'b', 'c', 'd']

print( list(map(list, itertools.combinations(l,2))))

#결과값 : [['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']]

 

 

# 조합 구현하기 (2) - DFS 사용하기

# itertools를 사용 못 할 때

 

#<코드>

# 목적: 한 개의 리스트에서 r개의 조합 구하기

# 입력: nCr 에서 n과 r

# DFS로 자기 자신을 포함 시킬 경우, 포함시키지 않을 경우 2가지를 고려하여 나아간다 (abcd, bcd, ad, d 등등 나옴)

# 전체를 DFS로 돈 후에 r개의 요소를 가졌을 경우가 답(ab, ac, ad, bc 등으로)

l = ['a', 'b', 'c', 'd']
n = len(l)
r = 2
answer = []

def dfs(idx, list):
    # 전체를 돌았을 때
    if idx == n:
        # 해당 경우의 수의 요소 개수가 r개와 같다면
        if len(list) == r:
            # 답이다
            answer.append(list[:])
        #모두 돌았으니 정답이든 아니든 리턴해줌
        return
    # 자기 자신을 포함시킬 경우
    list.append(l[idx])
    dfs(idx+1, list)
    # 자기 자신을 포함시키지 않을 경우
    list.pop()
    dfs(idx+1, list)

dfs(0, [])
print(answer)

#결과값 : [['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']]

 

 

# 조합 구현하기 (2) - DFS 사용하기

# itertools를 사용 못 할 때, 효율화 시켰습니다

 

#<코드>

# 목적: 한 개의 리스트에서 r개의 조합 구하기

# 입력: nCr 에서 n과 r

# DFS를 사용하여 r개를 초과하는 가지는 구하지 않도록 하였다

 

(발그림...)

l = ['a', 'b', 'c', 'd']
n = len(l)
r = 2
answer = []

def dfs(idx, list):
    if len(list) == r:
        answer.append(list[:])
        return

    for i in range(idx, n):
        dfs(i+1,list+[l[i]])

dfs(0, [])
print(answer)