카테고리 없음
[이코테 # 탐색1] 이진 탐색/이진 탐색 트리 알고리즘, 부품찾기(이진탐색), 떡볶이 떡 만들기(이진탐색)
코딩상륙작전
2023. 6. 12. 17:28
* 이진 탐색
- 이미 정렬되어 있는 경우에 사용할 수 있는 알고리즘.
- 한 번 확일할 때마다 확인하는 원소의 개수가 절반씩 줄어들기에 시간 복잡도가 O(logN)이다.
- 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)을 적용하자.
- 코딩테스트 단골 문제이니 소스코드 외울 것.
# 이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
return binary_search(array, target, mid + 1, end)
# 이진 탐색 소스코드 구현 (반복문)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
end = mid - 1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid + 1
return None
# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result + 1)
*이진 탐색 트리
- '왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드'을 만족하는 트리.
- 데이터를 넣고 빼는 방법은 자료구조에 가깝고, 구현을 요구하는 문제는 출제 빈도가 낮다.
- 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다. 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 고려할 것.
- 입력 데이터가 많은 문제는 sys라이브러리의 readline() 함수를 이용하면 좋다.
import sys
# 하나의 문자열 데이터 입력 받기
input_data = sys.stdin.readline().rstrip()
# 입력 받은 문자열 그대로 출력하기
print(input_data)
rstrip() : readline()으로 입력하면 입력 후 줄 바꿈 기호가 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용한다.
* 부품 찾기(p.197 이진탐색)
N개의 부품 종류에서 M개의 부품 찾기.
# 오답 풀이 -> 비슷한 구현 구조인 집합 자료형을 이용하면 시간복잡도가 해결됨.
N = int(input())
n = list(map(int, input().split()))
M = int(input())
m = list(map(int, input().split()))
# 순차탐색, 시간복잡도 O(n^2)
# M*N = 최악의 경우 100,000,000,000으로 시간초과할 가능성이 크다.
for i in range(M):
if m[i] in n:
print("yes", end = ' ')
else:
print("no", end = ' ')
재귀함수를 이용한 풀이
# 제공 답변 (약간 변형)
N = int(input())
n = list(map(int, input().split()))
n.sort()
M = int(input())
m = list(map(int, input().split()))
# 이진탐색(재귀함수)
# 전체 시간복잡도 : 정렬함수 + 이진탐색 함수
# 전체 시간복잡도 = NlogN+MlogN = O((N+M)logN)
def bi_search(n, target, start, end):
if start > end:
return False
middle = (start + end) // 2
if n[middle] == target:
return True
elif n[middle] < target:
return bi_search(n, target, middle + 1, end)
elif n[middle] > target:
return bi_search(n, target, start, middle - 1)
for i in M:
if bi_search(n, i, 0, N - 1):
print("yes")
else:
print("no")
계수행렬을 이용한 풀이
# 계수행렬을 이용한 제공답변
# N(가게의 부품 개수) 입력
n = int(input())
array = [0] * 1000001
# 가게에 있는 전체 부품 번호를 입력 받아서 기록
for i in input().split():
array[int(i)] = 1
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if array[i] == 1:
print('yes', end=' ')
else:
print('no', end=' ')
집합 자료형을 이용한 풀이
# 집합 자료형을 이용한 제공 답변
# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 입력 받아서 집합(Set) 자료형에 기록
array = set(map(int, input().split())) # set()함수는 집합 자료형을 초기화할 때 사용
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if i in array:
print('yes', end=' ')
else:
print('no', end=' ')
30분 시간초과
오답노트
시간복잡도 생각할 것.
* 떡볶이 떡 만들기(이진탐색)
# 제공답
# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))
# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)
# 이진 탐색 수행 (반복적)
result = 0
while(start <= end):
total = 0
mid = (start + end) // 2
for x in array:
# 잘랐을 때의 떡볶이 양 계산
if x > mid:
total += x - mid
# 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부분 탐색)
if total < m:
end = mid - 1
# 떡볶이 양이 충분한 경우 덜 자르기 (왼쪽 부분 탐색)
else:
result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1
# 정답 출력
print(result)
오답노트 :
이진 탐색 적용 어렵.
* 참고
https://github.com/ndb796/python-for-coding-test