이분탐색 - 백준 1654, 2110,1300,12015 파이썬

이분탐색과 관련한 문제를 백준에서 풀어보았다.

근데 알고리즘 문제들이 꼭 하나의 풀이만 있는 것이 아니기 때문에

내가 어렴풋이 알고 있는 이분탐색은 오름차순으로 정렬하여 중간값보다 크면 

큰 쪽 배열에서 원하는 값을 찾고 아니면 작은 쪽 배열에서 원하는 값을 찾는 방식이였다.

 

내가 위에서 설정한 중간값이 인덱스의 최소와 최대의 합을 2로 나눈 과정이였는데 여기서 더 나아가 

최소와 최대값을 바꿔가면서 바뀌는 중간값을 이용하여 원하는 값을 얻어내는 parametric search라는 게 있다.

이와 관련된 내용은 https://ialy1595.github.io/post/parametric-search/ 여기에 잘 정리되어 있으니 확인해보시길...

 

이제 문제를 함께 풀어보자

 

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

랜선이 n개가 주어지고 필요로 하는 랜선의 갯수 k가 있다.

주어진 랜선 n개를 적절히 잘라서 원하는 랜선의 갯수 k를 만족하는 최대의 길이를 구하는 문제였다.

 

import sys
input = sys.stdin.readline
n, target = map(int,input().rstrip().split())
li = [int(input().rstrip()) for _ in range(n)]
l = 1
h = max(li)
while l < h :
    if h - l <=2 :
        break
    m = (l+h+1) // 2
    result = 0
    for i in li :
        result += (i//m)
    if result < target :
        h = m
    else :
        l = m - 1
print(l+1)

처음에 작성한 코드인데 정답을 만족하지 못했다.

위에 링크한 본문을 읽고 코드를 작성했을 때 무한루프에 빠졌는데 무한루프는 정답의 범위 설정조절하거나

low와 high값의 수정을 결정하는 조건문을 적절하게 수정해주면 되는데 나는 정답의 범위를 조절했다.

그래서 low값에서 1을 더한 값을 출력했지만 최적의 값이 아니였다.

 

import sys
input = sys.stdin.readline
n, target = map(int,input().rstrip().split())
li = [int(input().rstrip()) for _ in range(n)]
l = 1
h = max(li)
while l < h :
    if h - l <=2 :
        break
    m = (l+h+1) // 2
    result = 0
    for i in li :
        result += (i//m)
    if result < target :
        h = m
    else :
        l = m - 1
answer = 0
while True :
    result  = 0
    for i in li :
        result += (i//l)
    if result >= target :
        answer = l
        l += 1
    else :
        break
print(answer)

그래서 이렇게 수정해줬는데 다른 점은 answer변수와 그 아래 while문이다.

high와 low값의 차이가 2로 줄어든다면 while문을 끝내고

그 범위 내에서 최대값을 계산하여 정답으로 return해줬다.

 

이런 식의 문제풀이는 처음이였는데 좋은 개념을 배워서 기분이 좋았다.

이제 이를 이용한 다른 문제들도 풀어보자

 

이분탐색의 핵심은 조건설정과

어느 부분에서 최소값 혹은 최대값을 얻어야 하는지 문제를 정의하는데 달렸음을 깨달았다.

 

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

이번엔 공유기를 설치하는 문제였는데

공유기의 갯수와 설치가능한 집의 x좌표값이 주어졌다.

집집간의 거리가 최대로되게끔 공유기를 설치하는 문제였다.

 

처음 이 문제를 풀 때 공유기가 홀수? 짝수의 개념으로 놓고 반으로 나누거나 홀수대로 나누거나 하는 방법을 생각했는데

이는 집간의 거리가 균등할 때 적용할 수 있는 풀이일 뿐 문제에 주어진 집은 들쭉날쭉이다

혼자 열심히 고민하다가 힌트를 좀 찾아다녔는데 공유기 사이의 거리를 중간값으로 놓고 만족하는 집에 설치하여

설치 갯수를 조건으로 low와 high값을 조정해주면 풀 수 있었다.

공유기를 설치한 갯수가 조건보다 많으면 low값을 수정하고 적으면 high값을 수정해줬다.

import sys
input = sys.stdin.readline
n,count = map(int,input().rstrip().split())
li = [int(input().rstrip()) for _ in range(n)]
li.sort()
low = 1 #최소간격
high = li[n-1]-li[0] #최대간격 첫 집과 끝집
if count == 2 : #공유기가 2대이면 무조건 첫 집과 끝집이므로 예외처리
    print(li[n-1] - li[0])
else :
    while low < high :
        if high - low <= 1 :
            break
        mid = (low+high + 1)//2
        cnt = 0 #공유기 설치한 갯수
        cur = 0 #마지막으로 설치한 집의 좌표
        for i in range(n) :
            if i == 0 :
                cnt += 1    
                cur = li[i]
                continue
            if (li[i] - cur) >= mid :
                cnt += 1
                cur = li[i]
        if cnt < count :
            high = mid
        else :
            low = mid
    print(low)

이렇게 각 상황에 맞게 알고리즘을 어떻게 적용할지 고민하는 게 문제를 풀어나가는 핵심인 것 같다.

 

https://www.acmicpc.net/problem/1300

1300번: K번째 수

숫자 n으로 NXN배열을 만드는데 각원소는 ixj의 값을 가지는 배열이다.(인덱스는 1부터 시작)

그리고 이 배열을 일차원 배열로 만들어서 k번째 수의 값을 출력하는 문제였다.

 

import sys
input = sys.stdin.readline
n = int(input().rstrip())
t = int(input().rstrip())
low = 1
high = ((t//n)+1)*n
while low<high :
    result = 0
    cnt = 0
    mid = (low+high)// 2
    for i in range(1,n+1) :
        isBreak = False
        for j in range(1,n+1) :
            n = i*j
            if mid >=n :
                result += 1
                cnt += 1
            if cnt > t :
                isBreak = True
                break
        if isBreak :
            break
    
    if cnt > t :
        high = mid
    else :
        low = mid + 1
print(low-1)

처음에 내가 작성한 풀이인데 VSCode에서 잘 동작했지만 시간초과로 실패했다...

아마 while문 안에 for문 2개가 연속으로 있는 게 시간 초과의 원인이였을것이다

NxN배열의 특징은 1행에 n번째 숫자가 가장 큰 숫자인데 이를 활용해서 

이 n보다 크면 1행의 모든 값보다 크므로 다음 행으로 넘어가서 몇 번째일지만 구하면 되는데

이걸 풀 수 있는 방법이 도저히 생각이 안났다... 그래서 다른 분의 풀이를 참고했다..

 

import sys
input = sys.stdin.readline
def count_below(number):
    count = 0
    for row in range(1, N+1):
        count += min((number-1) // row, N)
    return count


N = int(input().rstrip())
k = int(input().rstrip())

left, right = 0, N * N
while left <= right:
    middle = (left + right) // 2
    if count_below(middle) >= k:
        right = middle - 1
    else:
        left = middle + 1
print(right)

count_below라는 함수를 참고했다. N배열의 최대값과 최소값을 left와 right로 사용하여 중간값을 middle로 사용했다.

그래서 count_below에서 몇 번째 인지 계산하여 left와 right의 값을 적절하게 조절해줬다.

 

함수를 잠깐 살펴보면 for문 안에 row는 행을 뜻한다. min에서 볼 수 있듯이 number에서 1을 뺀 값을 row로 나눈 값과 

길이 N중에서 작은 값을 count해줬다. number에 -1을 해준 이유는 NxN배열의 원소값과 number가 같더라도 우리는 n번째로 큰 수를 찾고 있기 때문에 -1을 해줘서 같은 값보다 작은 값을 포함하기 위함이다. 

그리고 이 값과 N을 비교하는 이유는 몫이 N보다 크다면 해당하는 행의 제일 큰 숫자보다 큰 값임을 의미하므로 갯수 n개를 더해주었다.

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

이게 제일 마지막 문제인데 진자 너무 어려워서 결국엔 정답을 참조했던...그럼에도 의문이 풀리지 않았던 문제이다...

 

수열의 크기와 수열이 주어지고 거기서 가장 긴 증가하는 부분수열의 길이를 구하는 문제였다.

내가 처음에 풀이한 코드이다

import sys
input = sys.stdin.readline
n = int(input().rstrip())
li = list(map(int,input().rstrip().split()))
l = 1
h = n

def findLongestArr(li) :
    d = [1]*(len(li)+1)
    cur = li[0]
    for i in range(1,len(li)) :
        if li[i] > cur :
            d[i] = d[i-1] + 1
            cur =li[i]
        elif li[i] > li[0] :
            d[i] = 2
            cur = li[i]
    return max(d)

while l < h :
    mid = (l+h)//2
    d = []
    for i in range(0,n-mid) :
        arr = li[i:i+mid]
        d.append(findLongestArr(arr))
    if max(d) >= mid :
        l = mid + 1
    else :
        h = mid

print(h)

부분수열의 길이를 중간값으로 하여 이를 만족하는 모든 수열의 증가하는 부분수열 길이의 최대값을 출력했다.

그러나 이건 효율적인 풀이가 아니였다. 조건에서 n의 길이가 최대 100만개인데 최악의경우 100만**2의 연산을 하는

풀이이기 때문이였다..이렇게 저렇게 한참을 고민하다 다른분의 풀이를 찾아보았다.

 

import sys
input = sys.stdin.readline
n = int(input().rstrip())
li = list(map(int,input().rstrip().split()))
arr = [0]
for case in li :
    if arr[-1] < case :
        arr.append(case)
    else :
        left = 0
        right = len(arr)

        while left < right :
            mid = (left+right) // 2
            if arr[mid] < case :
                left = mid + 1
            else :
                right = mid
        arr[right] = case
print(len(arr) - 1)

이게 정답 풀이인데 주어진 수열을 돌면서 새로운 배열 arr에 적절한 위치에 값을 넣어주는 방식이다

코드의 실행이 끝나면 증가하는 부분수열인 arr을 얻을 수 있다.

그리고 처음에 0을 포함했으므로 -1을 한 값을 출력하면 정답을 얻을 수 있다..

여기서 정답은 맞췄지만 의문인 부분이 있었다.

 

100 50 70 90 75 87 105 78 110 60을 예로들자면 LIS는  [50, 70, 75, 87, 105, 110]으로 길이가 6이다.

그리고 위 코드로 얻은 arr은 [0, 50, 60, 75, 78, 105, 110]으로 0을 제외하면 [ 50, 60, 75, 78, 105, 110]이다.

길이는 같아서 결과적으로 정답은 얻었지만 내가 풀이한 위 코드가 만약 증가하는 부분수열을 구하는 문제라면

당연히 틀린 풀이가 되는 것이다...그럼에도 정답처리가 되었지만 찝찝한 마음에 질문게시판에 글을 남겼고

내가 가진 의문처럼 실제로 증가하는 부분수열을 출력하는 문제가 14003번문제였다. 난이도는 플레티넘...ㅎ

아직 플레티넘 문제 한 번도 안풀어봤는데 나중에 풀어봐야겠다!!

 

이렇게 이분탐색에 대한 문제풀이를 마쳤다. 테마별로 풀어나가서 집중적으로 학습하는 게 도움이 많이 되는듯하다

나도 언젠가 내 이름을 딴 알고리즘을 만들 수 있지 않을까? 내심 기대해본다 ㅎㅎ