오늘의 학습 키워드
완전 탐색
공부한 내용 본인의 언어로 정리하기
완전 탐색
- 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법
완전탐색 기법을 활용하는 방법
우선 완전탐색 기법으로 문제를 풀기 위해서는 다음과 같이 고려해서 수행한다.
1) 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2) 가능한 모든 방법을 다 고려한다.
3) 실제 답을 구할 수 있는지 적용한다.
여기서 2)의 모든 방법에는 다음과 같은 방법 등이 있다.
① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법
repeat 함수
- object를 반복해서 반환하는 이터레이터를 만드는데, times 인자가 지정되지 않으면 무기한 실행
- repeat의 일반적인 용도는 map이나 zip에 상숫값 스트림을 제공하는 것
In [4]: list(repeat(numbers, n))
Out[4]: [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
- repeat함수를 for 문에 넣어 사용한 경우
for idx, word in enumerate(itertools.repeat({1:2},3)):
print(word)
#결과
{1: 2}
{1: 2}
{1: 2}참고
https://rfriend.tistory.com/459
오늘의 문제
from itertools import product
def solution(word):
#길이를 1씩 늘려가며 해당 자릿수에 가능한 모든 경우를 찾는 방법
words = []
for i in range(1, 6):
for c in product(['A', 'E', 'I', 'O', 'U'], repeat=i):
words.append(''.join(list(c)))
words.sort()
return words.index(word) + 1
-
위에 나와있는 방법 중 어떤 방법으로 풀까 고민하다가, 이 배열 요소가 5가지 밖에 되지 않기 때문에 Brute Force 기법을 사용해 풀게 되었다
-
사실은 따로 for 문으로 repeat 을 구현하려다가, 제공하는 repeat 함수가 있는 것을 확인하고 활용하게 풀게 되었다
오늘의 회고
어떤 문제가 있었고, 나는 어떤 시도를 했는지
- for 문을 사용해 repeat 함수를 구한하려고함 -> 더무 복잡
어떻게 해결했는지
- itertools 모듈의 repeat 함수를 사용
무엇을 새롭게 알았는지
- repeat 함수
- 완전 탐색의 종류와 적용 사례
내일 학습할 것은 무엇인지
- 완전 탐색 문제 더 풀어보기
