이것이 코딩 테스트다 PART2 with python : 이진탐색
1. 순차탐색
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
def sequential_search(n, target, array):
for i in range(n):
if array[i] == target:
return i + 1
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = input(input_data[0])
target = input_data[1]
print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()
# 순차 탐색 수행 결과 출력
print(sequential_search(n,target,array))2. 이진탐색
- 3개의 변수 : 시작점, 끝점, 중간점
- 찾으려는 데이터와 중간점위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.( 탐색 범위를 절반씩 좁혀가며 데이터를 탐색)
- 시간복잡도 : 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)
n, target = list(map(int, input().split()))
array = list(map(int,input().split()))
result = binary_search(array, target, 0, n-1)
if rsult == None:
print("원소가 존재하지 않습니다")
else:
print(result + 1)- 반복문으로 구현한 이진 탐색
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
n, target = list(map(int, input().split()))
array = list(map(int,input().split()))
result = binary_search(array, target, 0, n-1)
if rsult == None:
print("원소가 존재하지 않습니다")
else:
print(result + 1)3. 이진 탐색 트리
이진탐색의 전제조건 : 데이터 정렬
트리
트리는 부모 노드와 자식 노드의 관계로 표현된다.
트리의 최상단 노드를 루트노드라고 한다.
트리의 최하단 노드를 단말노드라고 한다.
트리에서 일부를 떼어내도 트리구조이며 이를 서브 트리라 한다.
트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.이진 탐색 트리
부모 노드보다 왼쪽 자식 노드가 작다.
부모 노드보다 오른쪽 자식 노드가 크다.
(왼쪽 자식노드 < 부모 노드 < 오른쪽 자식 노드)실전문제
부품찾기 (난이도 1.5)
매장의 부품의 개수 : n ( 1<= n <= 1000000)
손님이 구매할 부품의 개수 : m ( 1<= m <= 10000)
이진탐색
다량의 데이터 검색을 효과적으로 처리할 수 있다.
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 = int(input())
array = list(map(int,input().split()))
array.sort()
m = int(input())
x = list(map(int,input().split()))
for i in x:
result = binary_search(array, i, 0, n-1)
if result != None:
print('yes',end = ' ')
else:
print('no', end = ' ')계수정렬
n = int(input())
array = [0] * 1000001
for i in input().split():
array[int(i)] = 1
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 = int(input())
array = set(map(int,input().split()))
m = int(input())
x = list(map(int,input().split()))
for i in x:
if i in array:
print('yes',end = ' ')
else:
print('no', end = ' ')
set()함수
- 중복을 허용하지 않는다.
-> 중복을 허용하지 않는 특징 때문에 데이터의 중복을 제거하기 위한 필터로 종종 사용된다.- 순서가 없다(Unordered).
-> 만약 set 자료형에 저장된 값을 인덱싱으로 접근하려면 다음과 같이 리스트나 튜플로 변환한 후에 해야 한다.
떡볶이 떡 만들기 (난이도 2)
n: 떡의 개수
m: 떡의 길이
떡의 길이가 M일때 적어도 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
start = mid +1
print(result)
뚜잇뚜잇 FE개발자