반응형
완전탐색 & 이분탐색
▶ 탐색이란
많은 데이터 속에서 원하는 데이터를 찾는것.
웹에서 특정 문자를 가진 웹 문서를 찾거나 신용카드나 버스카드 결제시 탐색 알고리즘을 사용한다.
▶ 탐색의 종류
완전탐색
Brute Force라고도 부르며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 술르 탐색하는 효율성 관점에서 최악의 방법.
▶ 완전탐색 구현방법
- 반복문
- 재귀함수
- 동저 계획법
- 백트래킹
- 탐욕법
▷ 완전탐색의 반복문 구현
def solution(trump) :
for i in range(len(trump)) :
if trump[i] == 8 :
return i
return -1
▷ 완전탐색의 재귀함수 구현
def solution(trump, loc):
if trump[loc] == 8 :
return loc
else :
return solution(trump, loc+1)
이분탐색
- 이진검색이라고도 표현.
- 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘 중간의 값을 선택하여 찾고자 하는 값과 크고 작음을 비교하는 방법.
- UPDOWN 게임의 원리와 비슷.
▷ 트럼프 카드를 찾는 이분탐색 코드.
def solution(trump) :
left = 0
right = len(trump)-1
while (left <= right) :
mid = (left+right)//2
if trump[mid] == 8 :
return mid
elif trump[mid] < 8 :
left = mid + 1
elif trump[mid] > 8 :
right = mid - 1
return mid반응형
'Python' 카테고리의 다른 글
| [Python] Coding Test (카드2) (0) | 2022.10.10 |
|---|---|
| [Python] Coding Test (괄호) (0) | 2022.10.10 |
| [Python] Coding Test (크레인 인형뽑기 게임) (1) | 2022.10.08 |
| [Python] Stack & Queue (0) | 2022.10.08 |
| [Python] Pivot Table (0) | 2022.10.06 |