[Python] 이것이 코딩테스트다 7장 이진탐색

이진탐색의 핵심

 

• 순차 탐색 : 앞에서부터 차례차례 탐색
• 이진 탐색 : 반으로 쪼개면서 중간점을 기준으로 탐색  O(logn) 

 이진 탐색은 우선 정렬이 되어있다는 가정하에 할 수 있는 탐색이다

따라서, 정렬이 안되어 있다면 정렬을 하고 이진탐색을 해야하므로 O(logn)의 성능이 안나올 수 있다.

 

 

이진 탐색 트리 :  왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

이진 탐색 트리를 구현하면은 부모노드 부터 검사를 해서 왼쪽으로 갈지 오른쪽으로 갈지 정할 수 있기 때문에 이진 탐색을 쉽게 적용 가능하다

 

 

이진 탐색의 핵심은 문제를 보고 이진탐색이냐 아니냐를 구별해 내는 능력을 키우는 것 

보통 몇십억~ 기하급수적인 숫자가 나오면 아무리 순차탐색의 O(n)성능이라도 시간초과가 나기 때문에 

이진 탐색을 떠올려야한다

 

 

번외

파이썬에서 문자열 빠르게 입력 받기 문법

import sys

input_data = sys.stdin.readline().rstrip()

print(input_data)

 

 

 

---

이진 탐색 예제

 

 

 

📝 체감난이도 : ★☆☆☆☆

 

🎨 이진 탐색 : 재귀 이용

 

 

 

 

 

🎨 이진 탐색 : 반복문 이용

 

 

 

 

🔑 Key Point 

 

두 방법 모두 구현할 줄 알게되었다

 

 

 

 

 

---

부품 찾기 

 

 

 

📝 체감 난이도 : ★☆☆☆☆

 

 

🎨 내가 짠 코드 (이진 탐색)

 

 

 

 

 

 

 

🎨 계수 정렬로 푸는법

 

 

 

 

 

 

🎨 집합 자료형 이용하여 푸는 법

 

 

 

 

 

🔑 Key Point 

 

• 이진 탐색 방법

이 문제는 최대 1000000 까지 입력 받을 수 있기 때문에 O(nlogn) 이상의 성능을 가지는 알고리즘으로 구현하여야 한다.

전형적인  Yes , No 문제로 이진탐색을 이용하여 풀 수 있다 

 

정렬이 되어있지 않기 때문에 정렬을 한 뒤, 이진 탐색을 이용하여 풀면 O(nlogn)의 성능으로 무리 없이 풀 수 있다📑

 

 

• 계수 정렬 방법

계수 정렬을 이용하여도 풀 수있다 데이터가 딱 마지노선인 1000000이하 이기 때문에 가능하다 📐

 

 

• 집합 자료형을 이용하여 푸는 방법

파이썬의 set 함수를 이용(집합자료형)하면 문자열안에 문자가 있는지 없는지 판별하는 것처럼 in 이라는 문법하나로 검사를 할 수 있다. 

in set을 써서 풀 수 있다는건 O(nlog)이하의 성능을 보일만큼 효율적이라는건데 처음알았다

 

 

 

---

떡볶이 떡 만들기

 

 

 

체감 난이도 : ★★☆☆☆

 

🎨 내가 짠 코드

 

 

 

 

 

🎨 다른 방식의 코드

 

 

 

🔑 Key Point (매우 중요!)

 

 

이 문제는 위의 문제와 다르게 반드시 이진탐색을 써서 구현하여야 하는 문제이다. 아니면 시간초과에 걸림

전형적인  Yes , No 문제로 이진탐색을 의심해보아야한다. (파라메트릭 서치)

 

 

이 문제가 순차 탐색이 될 수 없는 이유는 절단기의 최대 높이가 10억 까지다

즉 순차 탐색의 최악의 경우 발생되는 연산 횟수는 10억 x 1000만번 이 된다. 

파이썬은 2000만번에 1초걸린다고 했으므로,

제한시간이 2초인 이 문제에서는 연산횟수가 4000만번 이하로 실행되어야 할 것이다

즉,순차 탐색 O(n)으로 풀 경우, 최선의 경우가 아닌이상 무조건~ 시간초과가 난다

 

 

하지만 이진탐색으로 풀 경우는 2^31 이 거의 10억 비슷하게 되므로

최악의 경우 절단기 옮기기는 끽해야 31번 x 1000만번 = 3100만번으로 2초이내에 실행 할 수가 있다. 

 

책에는 이진탐색 반복문을 이용하였고, 나는 따로 함수를 만들어 재귀함수를 이용하여 구현하였다

 

 

 

---

마무리

 

사람들이 이진탐색이 어렵다~ , 저자도 이진탐색이 굉장히 어려운 편에 속한다 ~라고 표현을 하였는데, 아직까지 이해가 잘안간다

 

 

문제푸는 방식은 쉽지만 처음에 조건을 보고 이 문제가 이진탐색을 써야하는 문제인지 구별하기가 어려운 것 같다

그러려면,

제한시간초 + 데이터최대갯수 등을 고려하여 연산 횟수가 최악의 경우 몇번인지 대략이라도 구해보아야한다

그렇지 않으면, 이진탐색을 이용하여야하는데 순차 탐색을 이용하는 경우 다시 코드를 구현해야하는 😅삽질을 하게 될 것이다 

 

 

암튼 BFS/DFS보다 쉽다고 느껴졌고,

마지막 떡볶이 문제도 꽤 어려운 문제에 속한다고 하였는데 체감상 쉬운 문제였다.

실제 코딩테스트에서 등장하는 이진 탐색 문제를 더 풀어보면서 뭐가 어려운지 살펴봐야 할 것 같다 😣