Python | 완전탐색

완전탐색(Exhaustive Search)은 가능한 모든 경우의 수를 탐색하여 해답을 찾는 방법

• 모든 가능성 탐색(브루트 포스)
• 백트래킹: 재귀적으로 탐색하여 정답을 찾는 방법
• 순열/조합/부분집합
• 격자 탐색(DFS, BFS)

python docs 공식 문서

itertools — Functions creating iterators for efficient looping

> product(), permutations() 함수의 차이점, 정의 등

 

# 프로그래머스 | 피로도

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    answers = []
    kk = k
    per = permutations([i for i in range(len(dungeons))], len(dungeons))
    per = [p for p in per] 
    for i in range(len(per)):
        for j in per[i]:
            if dungeons[j][0] <= kk:
                kk -= dungeons[j][1]
                answer += 1
            else:
                break
        answers.append(answer)
        answer = 0
        kk = k
    return max(answers)

 

1.  순서 고려한 조합을 먼저 구하기 위해 permutations를 import 하였습니다.

2. k(피로도)를 그대로 사용할 경우, 반복문 안에서 계속 -(마이너스)가 되기 때문에 k를 계속 새로 잡아줘야 합니다.

3. 리스트에 모든 경우의 수에 따른 결과 값을 넣어서 그 중 최대값을 return 합니다.

 

# 프로그래머스 | 모음사전

from itertools import product

def solution(word):
    dictionary = []
    for i in range(1,6):
        dictionary.extend(list(map( ''.join, product(['A', 'E', 'I', 'O', 'U'], repeat = i))))
        dictionary.sort()
    return dictionary.index(word)+1

 

1. product() 함수 사용 > 공식 문서에서 볼 수 있듯이 반복횟수를 정해서 만들 수 있습니다.

2. 함수를 사용해서 직접 모든 조합의 딕셔너리를 만듭니다.

3. 그리고 sort()를 통해 정렬하고, index()를 통해 index 확인 후에 인덱스가 0부터 시작하기 때문에 1을 더해서 return 하면 답을 구할 수 있습니다.