김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1365 꼬인 전깃줄 파이썬(Python)

문제 링크

최장 증가 부분수열(Longest Increasing Subsequence, LIS) 문제.
전선이 꼬이는 부분은 이전 전봇대보다 번호가 낮은 전봇대에 연결되는 부분이므로, 결과적으로 꼬이는 전선을 모두 제거하면 LIS만이 남게 된다.
즉, 자를 전선 개수를 찾는 문제는 결과적으로 n에서 LIS의 길이를 빼는 문제가 된다.
입력이 최대 \(100000\)이므로 \(O(N\log N)\)시간 안에 LIS를 찾아야 하고, 따라서 나이브한 \(O(N^2)\) 알고리즘을 사용하면 안 된다.
방법은 간단한데, 수열을 순회하면서 maxs 리스트를 갱신하면 된다.
이때, maxs 리스트는 i 번째 인덱스에 길이가 i인 LIS의 마지막 원소(즉, 최대값)를 저장하고 있다.
이분 탐색을 사용하면 로그 시간 안에 수열의 현재 숫자가 들어갈 위치를 찾을 수 있으므로, 쉽게 풀 수 있다.

#!python

from bisect import bisect_right

# 이 문제는 LIS를 찾는 문제로 볼 수 있다
n = int(input())
nums = list(map(int, input().split()))

# maxs[i]는 길이가 i인 LIS의 마지막 원소
maxs = [0]

# 숫자들을 순회하며 LIS 갱신
for i in nums:
    if i > maxs[-1]:
        maxs.append(i)
    else:
        maxs[bisect_right(maxs, i)] = i

# n개의 전선 중 LIS인 전선들만 남겨두고 다 자르면 된다
print(n - len(maxs) + 1)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑