[이것이 코딩테스트다] 17일차 - 이진탐색 예제 | 고정점 찾기 , 백준 - 공유기 설치

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 7 이진탐색

오늘 풀이한 문제 - 실전문제 풀이

 

[이코테 368p] 고정점 찾기

문제 

고정점(Fixed Point)이란 , 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다.

예를들어 수열 a = {-15, -4, 2, 8, 13}이 있을때 a[2] = 2이므로 고정점은 2가 됩니다. 

하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든원소가 오름차순으로 정렬되어 있습니다.

이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 

고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 -1을 출력합니다.

단, 이 문제는 시간복잡도 O(logN)으로 설계하지 않으면 '시간 초과' 판정을 받습니다. 

 

접근 방법

수열이 정렬되어 있고 시간복잡도 O(logN)을 요구하므로 이진탐색을 이용하여 푼다.

이진탐색에서

target = data[mid]로 두고 

mid < data[mid] -> 뒤를 버림 (왼쪽만 사용)

mid > data[mid] -> 앞을 버림 (오른쪽 사용)

 

소스 코드

def binary_search(start, end, data):
    mid = (start + end) // 2

    if start > end:
        return -1
    
    if mid == data[mid]:
        return mid
    
    elif mid > data[mid]:
        return binary_search(mid+1, end, data)
    else:
        return binary_search(start, mid-1, data)
        
data = [-15, -4, 2, 8, 13]
start = 0
print (binary_search(start, len(data)-1, data)) ## 2

이진탐색 조건문 부분이 아직 조금 헷갈린다 .. 😅

 

[백준 2110] 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

접근 방법

특정 범위내에서 개수를 정하는 문제 유형은 이진탐색으로 풀어야한다고 한다.. (사실 이진탐색 파트여서 이진탐색을 떠올렸지 코테에서 이문제를 만났다면 얼레벌레 풀고 시간초과의 늪에 빠져있었을 것같다 ,,^_^,,,,,!)

문제는 이진탐색으로 풀어야겠다고 생각은 했지만 로직이 도저히 생각나지 않았다 ,,

그래서 해답을 봤다,,,,,,,,,,,,,

 

1. 일단 주어진 집의 좌표(x좌표)를 정렬한다

2. 초기 설정값으로 일단 와이파이를 설치할 수 있는 최대, 최소 간격을 start, end로 설정한다 

     최대 거리 (처음집과 맨끝집에 설치하는 경우), 최소 거리 (각 집마다 설치하는 경우)

3. while문을 돌며 이진탐색 시작

3-1. mid(와이파이 설치 간격) 를 최대~최소 중간값으로 설정하고, 일단 맨 앞집에 와이파이를 설치한다.

3-2. 맨 앞집으로부터 mid(설치 간격)만큼 떨어진 집에 와이파이 설치, 개수 세기

4-1. 설치된 와이파이 개수가 c보다 많다면 -> 설치간격을 넓혀야한다 -> start를 mid+1로 옮겨 mid값이 커지게한다

     이때 조건문이 종료될 수 있으니 현재 mid를 저장해놓는다

4-2. 설치된 와이파이 개수가 c보다 적다면 -> 설치간격을 좁혀야한다 -> end를 mid-1로 옮겨 mid값이 작아지게 한다

 

소스 코드

n,c = 5,3
data = [1, 2, 8, 4, 9]
data.sort()

start = 1  ## 공유기 설치 최소거리 설정
end = data[-1] - data[0]  ## 공유기 설치 최대거리 설정

wifi = 0
answer = 0
while (start <= end):
    mid = (start+end) //2
    installed = data[0] ## 일단 제일 처음 집에 설치
    
    for h in data[1:]:
        if h >= installed + mid :## 이미 설치된 집 + 간격이 충족되는 집이 나오면
            installed = h
            wifi += 1
        
    if wifi < c : ## 간격을 좁혀야함
        end = mid -1
    else: ## 간격을 넓혀야함
        start = mid + 1
        answer = mid ## while문이 끝날수 있으므로 일단 저장
        
print (answer) ## 3

사실 해답을 이해하는데도 시간이 좀 걸렸다 ,, 바부^^