프로그래머스 고득점kit 완전탐색 (Exhaustive search) - 모음사전(level2)

j_wisdom_h·2022년 10월 8일
0

CodingTest

목록 보기
6/58
post-thumbnail

완전탐색(Exhaustive search) - 모음사전(level2)


1. 문제 설명

입출력 예시


2. 완전탐색 in python

출처 : https://rebro.kr/59

1) 완전탐색 ?

문제에서 주어질 수 있는 모든 경우의 수를 탐색하는 알고리즘

▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.

▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.

2) 완전 탐색 기법

  • 단순 Brute-Force
    : 단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법

  • 비트마스크(Bitmask)
    : 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다.
    완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용이 가능하다.

  • 재귀 함수

  • 순열 (Permutation)
    : 완전 탐색의 대표적인 유형이다. 순열에 원소를 하나씩 채워가는 방식

  • BFS / DFS
    : 완전 탐색 + BFS/DFS 문제가 많이 나온다. 대표적인 유형으로 길 찾기 문제가 있다.


3. 문제해결

문제를 보고나서 든 생각은 '재귀함수 를 쓰면 되겠는데!'였다.
그렇지만 결국 풀지 못했다. 내게는 아직 level2는 고난도 문제다 😂😂

검색한 코드1
출처 : https://foameraserblue.tistory.com/187

def solution(word):
    answer = 0
    word_list = []
    words = "AEIOU"
    def all_word(cnt, w):
        if cnt == 5:
            return 
        for i in range(len(words)):
            word_list.append(w + words[i])
            all_word(cnt + 1, w + words[i])
    all_word(0, "")
    #print(word_list)
    return word_list.index(word) + 1

검색한 코드 2
itertools에 product함수를 이용
출처 : https://velog.io/@juwonlee920/Python-프로그래머스-완전탐색-모음-사전

from itertools import product
def solution(word):
    dictionary = []
    for i in range(5) : 
        for c in product("AEIOU", repeat=i+1) : 
            dictionary.append("".join(c))
    dictionary.sort()
    return dictionary.index(word)+1

i=0
'A', 'E', 'I', 'O', 'U'

i=1
'AA', 'AE', 'AI', 'AO', 'AU', 'EA', 'EE', 'EI', 'EO', 'EU', 'IA', 'IE', 'II', 'IO', 'IU', 'OA', 'OE', 'OI', 'OO', 'OU', 'UA', 'UE', 'UI', 'UO', 'UU'
...


4. itertools

출처 : https://docs.python.org/ko/3/library/itertools.html
자체적으로 혹은 조합하여 유용한 빠르고 메모리 효율적인 도구의 핵심 집합을 표준화한 모듈

itertools.product(*iterables, repeat=1)
: 입력 이터러블들(iterables)의 데카르트 곱.
repeat 키워드 인자를 사용하여 반복 횟수를 지정

product(A, B) == ((x,y) for x in A for y in B)
product(A, repeat=4) == product(A, A, A, A)

a = ['a','b','c','d']
b = ['e','f','g','h']
result = []
for c in product(a,b, repeat=2) : 
  result.append("".join(c))
print(result)
#['aeae', 'aeaf', 'aeag', 'aeah', ... ,  'dhdf', 'dhdg', 'dhdh']
profile
뚜잇뚜잇 FE개발자

0개의 댓글