스터디룸

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 12015. 가장 긴 증가하는 부분 수열 2

문제 풀이

LIS(Longest Increasing Subarray) 문제란다. 처음 들어본 개념인데 동적 프로그래밍, 이진 탐색으로들 해결한다고 한다. 아마 다른 풀이 유형이 등장하면 또 막혀서 정리하러 올 듯 싶다.

이 문제는 부분 수열 자체가 아니라 길이를 요구한다. 따라서 부분 수열의 원소 추가 혹은 갱신 조건을 명확히 해야 한다. 증가하는 부분 수열이므로 부분 수열의 마지막 원소보다 더 큰 언소가 등장할 경우에만 원소를 추가하고 그 외엔 단순 갱신만 하여 길이를 늘리면 안된다.

• 부분 수열이 비었다면 추가하고 continue
• 부분 수열의 마지막 수보다 크다면 append
• 부분 수열의 마지막 수보다 작거나 같다면 값에 대한 부분 수열의 이진 탐색 lower bound에 해당하는 위치에 갱신한다. (마지막 값일 수도 있기 때문에 단순 skip은 곤란하다.)

python 코드

import sys
import bisect
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
sol = []
for a in arr:
    if not sol:
        sol.append(a)
        continue
    if sol[-1] < a:
        sol.append(a)
    elif sol[-1] >= a:
        sol[bisect.bisect_left(sol, a)] = a
print(len(sol))

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 1655. 가운데를 말해요

문제 풀이

시간제한이 0.1초인 걸 봐선 입력과 동시에 중간값을 출력해야 함을 의미한다.

문제 자체는 우선순위 큐로 해결할 수 있는데 중간값이므로 가운데 수보다 작은 값들, 큰 값들을 저장할 우선순위 큐 1개가 아닌 2개로 풀어내야 한다.

전체 숫자가 짝수 개면 가운데 두 수 중 작은 수를 출력하고 그 외엔 중간값을 출력해야 하는데 중간을 기점으로 좌측은 최대 힙을, 우측은 최소 힙에 저장하면 되겠다. 그러나 입력이 미리 주어지지 않기 때문에 매번 중간값을 찾기 위해 적절히 삽입해야 한다. 우선 중간을 기점으로 최대 힙, 최소 힙으로 나누었으니 우선순위 큐의 루트들이 중간 지점을 향하도록 만들었다. 그렇다면 우측의 최소 힙은 좌측 최대힙의 모든 원소보다 값이 커야 한다. 그리고 좌우측 큐는 서로 균형이 맞아야 양쪽 루트가 중간 값임을 보증할 수 있다. 따라서 다음의 규칙을 준수해야 한다.

• 최대 힙, 최소 힙의 길이 차이는 1 이하여야 한다.
• 길이가 부족한 배열에 우선 삽입한다. 같은 경우 최대 힙에 삽입한다.
• 만약 좌측 최대 힙의 루트 노드가 우측 최소 힙의 루트 노드보다 크면 서로 바꾼다.
• 좌측 최대 힙의 루트 노드가 입력 받아온 값들의 중간 값이다. (중간 값이 2개라면 작은 값을 출력하기로 했으므로)

python 코드

import sys
import heapq
input = sys.stdin.readline

N = int(input())
left_q = []
right_q = []
for _ in range(N):
    x = int(input())
    if not left_q:
        heapq.heappush(left_q, (-x, x))
        continue
    if len(left_q) <= len(right_q):
        heapq.heappush(left_q, (-x, x))
    elif len(left_q) > len(right_q):
        heapq.heappush(left_q, (x, x))
    if left_q[0][1] > right_q[0][1]:
        l_out = heapq.heappop(left_q)
        r_out = heapq.heappop(right_q)
        heapq.heappush(left_q, (-r_out[1], r_out[1]))
        heapq.heappush(right_q, (l_out[1], l_out[1]))
    print(left_q[0][1])

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 1300. K번째 수

문제 풀이

이진 탐색을 적용해서 풀 수 있는 문제다. 이진 탐색으로 변형할 수 있는 문제들의 공통점을 유념할 필요가 있다.

• 탐색의 범위의 최솟값과 최댓값이 명확할 경우
• 전체 탐색 범위가 정렬된 형태이거나 $O(n)$ 이내에 문제에서 요구하는 수치를 계산할 수 있을 경우

결론적으로 문제 해결에 요구되는 함수의 형태가 단조함수인 경우를 의미한다.

명확하게 떨어지지 않겠지만 위 두 조건이 문제에 제시되었다면 브루트포스로 해결해야 하는 경우가 아니라면 문제의 해결에 요구되는 시간복잡도를 $O(nlog\ n)$으로 두고 탐색 횟수를 $O(log\ n)$, 정답 수치 계산을 $O(n)$으로 두고 해법을 찾아보자.

편하게 생각하면 탐색의 최솟값을 1, 최대값을 $N^2$으로 두고 탐색해도 되겠지만 최댓값을 K로 설정해도 무방하다. 그 이유는 아래와 같다.

탐색의 최댓값이 K여도 되는 이유

A를 정렬되지 않은 1차원 형태의 B' 배열로 만들었다고 치자. $B' = {1,\cdots, n, 2,\cdots, 2n, 3, \cdots, n^2 }$의 형태가 될 것이다. 그리고 K는 n보다 작거나 같거나 큰 3가지 경우의 수가 존재하는데 K가 n보다 작을 경우 K보다 작은 수는 K-1개가 된다. K가 n과 같을 땐 K보다 작은 수는 n-1이 되고 K가 N보다 큰 경우는 다시 상수가 곱해진 형태로 1~n을 반복하므로 중복된 숫자가 발생하여 K번 좌표의 수는 K보다 작을 수밖에 없다.

B[idx]보다 작은 A의 원소 개수

이진 탐색의 적용 방법은 최소 좌표를 1로 두고 최대 좌표를 K로 설정한 뒤 탐색 좌표에 대해 작거나 같은 A의 원소가 얼마나 있는지 계산해야 한다. 이 문제는 최소, 최대 좌표 설정은 어렵지 않으나 A의 원소를 카운트 하는 함수 작성이 난이도를 결정했다.

그렇다면 특정값 V에 대해 보다 작거나 같은 A의 원소의 개수를 계산하는 방법을 구상하자. 우선 idx에 대해 A의 각 행 1~n까지 나눈다고 했을 때 V // i가 V보다 작거나 같은 원소의 개수임은 알 수 있다. 그리고 V //i > N인 경우 행렬의 범위를 초과하기 때문에 min 함수로 보정해준다. 이런 식으로 n행에 대해 모두 수행하면 V보다 작거나 같은 A의 원소의 개수를 셀 수 있고 V에 대한 개수가 요구하는 좌표와 일치한다면 그 값이 B[idx]가 될 것이다.

python 코드

import sys
input = sys.stdin.readline

N = int(input())
k = int(input())

def search(N, k):
    def count_num(val):
        result = 0
        for i in range(1, N + 1):
            result += min(val // i, N)
        return result
    min_val,  max_val = 1, k
    sol = 0
    while min_val < max_val:
        mid_val = min_val + (max_val - min_val) // 2
        cnt = count_num(mid_val)
        if cnt >= k:  # cnt가 k보다 같거나 큰 수들 중 최소값
            max_val = mid_val - 1
            sol = mid_val
        elif cnt < k: # lower bound로 잡으면 k - 1 직후의 값을 잡는다.
            min_val = mid_val + 1
             # 그러면 배열에는 없으나 조건을 만족하는 수를 리턴해버림
    return sol

print(search(N, k))

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 2110. 공유기 설치

문제 풀이

이진 탐색 유형의 문제들 중 탐색 알고리즘 적용 방법이 단순 검색이 아니라 문제를 변형해서 적용할 수 있는 형태들에 대해 취약한 듯하다. 이 문제도 집들 간 간격에 대해 모두 탐색하지 않고 1개의 간격에 대해 $O(n)$의 시간이 소요되지만 정답 간격을 찾는데까지 $O(log\ n)$에 찾을 수 있다면 $O(nlog\ n)$에 문제를 해결할 수 있음을 보여준다.

집들 간 존재할 수 있는 최소 간격은 1이고 최대 간격은 마지막 집에서 첫 번째 집까지의 거리다. 그리고 탐색 간격은 (최대 + 최소) // 2가 된다. 탐색 간격은 적어도 만족해야 하는 최소한의 기준이므로 해당 간격을 최소한으로 잡고 설치했을 시 얼마나 넣을 수 있는가에 대한 함수만 작성하면 된다. 그리하여 설치할 수 있는 공유기의 대수와 문제에서 주어진 공유기 대수와 일치하는 간격들 중 최대값을 반환하면 되겠다.

• 문제로부터 진짜 공유기의 개수, 집들의 좌표를 입력받는다.

• 집들의 좌표를 정렬한다.

• 설치할 수 있는 공유기의 개수를 카운트하는 함수를 작성한다.

  첫집부터 공유기를 넣는다고 가정, 이전 좌표 + 간격 <= 다음 좌표 시 설치 가능 대수를 1 더하고 이전 좌표를 다음 좌표로 갱신한다.

• 이진 탐색 알고리즘을 적용한다.

  설치할 수 있는 공유기 개수가 요구량보다 작으면 최대 간격 갱신, 설치할 수 있는 공유기 개수가 요구량보다 크면 최소 간격 갱신을 하며 같은 경우엔 문제에서 요구하는 해답이 간격의 최대값이므로 최소 간격을 조정하는 경우에 등호를 넣고 별도의 버퍼에 탐색했던 간격을 저장하여 종결상황을 준비한다.

• 최소 간격과 최대 간격이 같아질 때까지 반복한다.

  최대 간격이 감소해서 종결되던 최소 간격이 증가해서 종결되던 버퍼에 while 문 종료 직전 조건을 만족했던 값이 버퍼에 저장되어 있는 상태다.

• 이후 저장된 버퍼의 값을 반환한다.

공유기 카운트 시 주의점

왜 첫 번째 집에 무조건 설치해야 하냐는 의문이 있을 수 있다. 이는 $a_1 + dist < a_2+dist$이기 때문에 최대한의 공유기를 설치하기 위함이다.(특정 탐색 간격으로만 설치하라는 제한이 없기 때문에 가능) 만약 $a_1 + dist$위치에 집이 없고 $a_2+dist$위치에 집이 있더라도 $a_1$에 설치 후 $a_2+dist$ 위치에 설치할 수 있음을 의미한다.

python 코드

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(int(input()))
arr.sort()

def search(arr, C):
    def counting(dist):
        target = 0
        result = 1
        for i in range(1, len(arr)):
            if arr[target] + dist <= arr[i]:
                result += 1
                target = i
        return result
    min_dist, max_dist = 1, arr[-1] - arr[0]
    sol = 0
    while min_dist <= max_dist:
        mid_dist = min_dist + (max_dist - min_dist) // 2
        cnt = counting(mid_dst)
        if cnt >= C:
            min_dist = mid_dist + 1
            sol = mid_dist
        elif cnt < C:
            max_dist = mid_dist - 1
    return sol
print(search(arr, C))

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 1654. 랜선 자르기

문제 풀이

단순 탐색이 아니라 이진 탐색의 Upper Bound를 다루는 문제다. 이진 탐색의 조금 고난도 문제는 Bound 문제와 탐색할 수 있는 형태의 문제로 분해하는 과정으로 이루어지는 듯하다. 얻을 수 있는 랜선의 개수를 카운트 하는 함수는 $O(n)$이겠지만 자르는 랜선 간격을 탐색하는 횟수는 이진 탐색을 적용하여 $O(log\ n)$ 내에 발견해야 $O(nlog\ n)$에 해결이 가능하다.

얻을 수 있는 랜선의 최대 길이를 구해야 한다. 여러개라도 1개만 요구하면 갖고 있는 랜선들 중 가장 긴 랜선을 주어야 하므로 최대 시작 간격은 max(보유 랜선 길이)이고 최소 시작 간격은 역시 1이다.

• 보유하고 있는 랜선의 개수, 요구 랜선 개수, 랜선 목록을 입력받는다.

• 랜선 배열들 중 최대값을 추출한다.

• 얻을 수 있는 랜선 개수를 계산하는 함수를 작성한다. (각 랜선에 대해 탐색 간격으로 나눈 몫이다.)

• 이진 탐색 알고리즘을 수행한다. (최소 간격이 최대 간격과 동일해질 때까지)

  얻고사 하는 전선의 길이가 가능한 최대 길이이므로 최소 간격의 조정이 필요한 경우에 등호를 넣고 버퍼에 현재 탐색 간격을 저장하여 종결 상황을 준비한다.

• 종료 후 버퍼에 저장된 길이 반환

python 코드

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
arr = []
for _ in range(K):
    arr.append(int(input()))

def search(arr, N):
    def get_lines(dist):
        result = 0
        for a in arr:
            result += a // dist
        return result
    min_dist, max_dist = 1, max(arr)
    sol = 1
    while min_dist <= max_dist:
        mid_dist = min_dist + (max_dist - min_dist) // 2
        cnt = get_lines(mid_dist)
        if cnt >= N:
            min_dist = mid_dist + 1
            sol = mid_dist
        elif cnt < N:
            max_dist = mid_dist - 1
    return sol

print(search(arr, N))