[플레이데이터][알고리즘] 완전탐색 / 이분탐색
완전탐색 / 이분탐색
🔊 2021.04.01 (목) 엔코아 플레이데이터 알고리즘 특강 2주차 내용을 정리한 노트 게시물입니다.
탐색(검색)이란?
많은 데이터 속에서 원하는 데이터를 찾는 것으로 웹에서 특정한 문자를 가진 웹 문서를 찾거나 신용카드나 버스카드 역시 검색 알고리즘을 사용한다.
탐색의 종류
- 완전탐색, 이분탐색, 깊이우선탐색, 너비우선탐색, 문자열탐색, KMP, BM
- 우리 강의에서는 가장 중요하다고 볼 수 있는 완전탐색, 이분탐색, 깊이우선탐색, 너비우선탐색 네 가지에 관한 탐색의 종류를 다룰 것이며
- 오늘 강의에서는 완전탐색과 이분탐색에 관한 내용을 다룬다.
PART 1. 완전탐색 (Brute Force)
완전탐색이란?
브루트 포스(Brute Force)라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 효율성 관점에서 최악의 방법
모든 경우의 수를 탐색하는 특성때문에, 효율성 측면에서는 최악
하지만, 완전탐색으로는 풀리지 않는 문제가 없다는 장점이 있다!
완전탐색 구현방법
- 반복문
- 재귀함수
- 동적 계획법
- 백트래킹
- 탐욕법
이 외에도 다양한 알고리즘에서 자주 사용되지만 어려운 알고리즘이기 때문에, 오늘은 간략하게 어떤 것인지만 보고 넘어가도록 한다.
반복문을 활용한 완전탐색
여기 뒤집혀있는 트럼프 카드 8장이 있다. 우리는 각 카드가 어떤 숫자를 가지고 있는지 알지 못한다. 이 카드 배열을 trump라고 해보자.
여기서 우리는 ‘♥ 8’이 어디에 있는지 알고 싶다. ♥ 8이 나올 때까지 아무 카드나 뒤집어 보면 될까?
이런식으로 무작위로 뒤집는다면 몇개 없을 땐 괜찮지만 카드가 몇 백만장이 있다면 어떤 것을 뒤집었는지 안뒤집었는지 기억하기가 쉽지 않을 것이다.그래서, 하나의 방향을 따라서 순서대로 하나씩 뒤집어보도록 할 것이다. (왼쪽에서 오른쪽으로 갈 것이다. 반복문의 순리를 따라가는 것이 되겠다.)
왼쪽에서 오른쪽으로 하나씩 뒤집어보니 4번째에서 8이 나왔다. 8은 우리가 원하는 정답이므로 여기서 종료한다.
반복문으로 어떻게 구현될까?
코드
def solution(trump): # 먼저 solution이라고 하는 함수를 정의
for i in range(len(trump)):# trump를 탐색할 index값을 range를 활용해서 반복문에서 사용하도록 한다
if trump[i] == 8: # trump의 i번째 인덱스가 8인지 아닌지 검사
# 만약 8이면,
return i # 8의 위치를 반환
return -1 # 하지만 trump 내에 8이 없다면, -1을 반환하도록 하고 작업을 종료한다.
재귀함수를 활용한 완전탐색
재귀함수로는 어떻게 구현될까?
코드
def solution(trump, loc): # solution이라는 이름을 가지면서 trump와 loc라고 하는 위치 인덱스 값을 갖는 함수를 정의하도록 한다
if trump[loc] == 8: # 현재 위치의 트럼프 값이 8이면,
return loc # 바로 현재 위치 loc를 반환한다.
else: # 그렇지 않으면,
return solution(trump, loc+1) # 트럼프의 다음 위치를 검사하는 solution 함수를 반환한다.
'''
지금 보는 것처럼 solution함수가 solution함수를 호출하고 있고,
이것을 우리는 재귀함수라고 부른다.
재귀함수는 다양한 방면에서 활용 가능하지만,
쉽게 무한루프에 빠지는 경향이 있기 때문에 사용하는데 반드시 유의해야한다!
'''
PART 2. 이분탐색
이분탐색에 대한 설명을 하기 전에 간단한 UPDOWN 게임을 한다고 가정해보자.
1부터 1000 사이의 숫자를 맞추면 된다. 기회는 8번이다.
어떤 숫자를 가장 처음으로 답할 것인가?
아마 대부분은 500이라는 숫자를 먼저 말할 것이다.
그 이유는 가장 안전하게 숫자의 범위를 반으로 줄일 수 있기 때문이다.우리는 500이라는 질문에 답으로 UP을 얻었다.
그럼, 그 다음엔 어떤 숫자를 물어볼 것인가?
아마 501과 1000사이의 숫자인 750을 물어볼 것이다.
우리는 범위를 점차 반씩 줄여나갈 것이다.이분탐색은 이와 같은 원리로 범위를 점차 줄여나가는 것이다.
이분탐색은 무엇인지 인터넷에 있는 흔한 정의부터 보도록 하자.
이분탐색이란?
- 이진검색이라고도 표현하며 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘
- 중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교하는 방법
여기서 우리가 주의깊게 봐야할 것은 ‘정렬된 리스트’라는 것이다.
앞에서 본 완전탐색은 정렬이 필요 없었지만, 이분탐색은 정렬된 리스트를 필요로 한다!
이분탐색의 구조를 한번 살펴보도록 하자.
이분탐색의 구조
여기 아까와 같이 카드가 있다.
이번에는 어떤 카드가 어디에 있는지 모르지만 순서대로 정렬된 카드 리스트이다.
우리는 여기서 8이 어디에 있는지 찾아보도록 한다.
이분탐색에서 먼저 가장 앞 즉, 인덱스 0의 위치를 left라고 지정하도록 한다.
그 다음, 가장 큰 인덱스 값을 갖는 곳을 right라고 지정하도록 한다.
그리고, left와 right의 중간 값을 갖는 mid를 지정하도록 한다.mid에서 얻은 값을 우리가 구하고자 하는 값과 비교를 해본다.
아직 mid의 값이 우리가 원하는 값보다 작으므로 left를 새로 지정해주도록 한다.
새롭게 지정된 left의 값은 기존의 mid보다 1이 더 큰 값이다.
그리고, 우리는 다시 새롭게 mid값을 지정해주도록 한다.
이번에 새롭게 지정된 mid에서의 카드 값은 7이다.
7은 역시나 우리가 원하는 정답이 아니지만 정답보다 작기 때문에 다시 left를 mid보다 한 칸 더 큰 곳으로 위치시켜준다.
그리고, 다시 mid를 새롭게 지정해주도록 한다.
이번 mid에서의 값은 우리가 원하는 정답이므로 우리는 여기서 알고리즘을 종료하면 되겠다.
이분탐색은 흔히 left, right 그리고 그 사이의 mid값의 조정으로 알고리즘이 구성되어있다는 것을 생각하면서 활용하면 어렵지 않게 문제를 풀어나갈 수 있을 것이다.
이분탐색 예시코드
def solution(trump):
left = 0
right = len(trump)-1
# ⓐ 함수의 도입 부분에서 left, right의 index 값을 지정해준다.
while(left <= right): # ⓑ left가 right보다 작거나 같다면
mid = (left+right) // 2 # ⓒ mid값 계산
if trump[mid] == 8:
return mid # 지정된 mid값을 활용하여 계산식이 정답이라면 정답을 반환
elif trump[mid] < 8:
left = mid + 1 # 만약 정답보다 작은 경우, left값을 기존의 mid보다 1을 더 크게 해준다.
elif trump[mid] > 8:
right = mid - 1 # 반대로 정답보다 클 경우, right값을 기존의 mid보다 1을 더 작은 값으로 해주고,
return mid # (정답을 찾을 때까지 반복 실행하도록... while문)
'''
### ⓑ 부분에 대해서 ###
right는 left보다 항상 클 것이다.
하지만, 이 두 개가 뒤집어지는 순간이 온다면 그것은 범위를 줄일 만큼 최대한 줄인 것이기 때문에,
while문 안에서 right가 left보다 크다면 항상 실행될 수 있도록 구성해준다.
### ⓒ 부분에 대해서 ###
while문의 시작과 동시에 계속해서 계산되어야 할 mid값을 계산해주도록 한다.
'''
Leave a comment