김낭만

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

백준(BOJ) 10775 공항 파이썬(Python)

문제 링크

정석은 분리 집합(Disjoint Set, Union Find)으로 푸는 것 같은데,
찾아보면 set의 lower bound를 활용했다는 사람도 있고, 세그먼트 트리로 풀었다는 사람도 있다.
그다지 효율적인 답은 아닌 것 같지만, 비트마스킹으로도 풀려서 비트마스킹으로 풀었다.
기본적으로, 공항의 도킹 과정은 번호가 높은 것부터 도킹하는 그리디(Greedy) 알고리즘에 기반한다.
Straightforward하게 생각하면 gi의 번호부터 아래로 내려가면서 빈 게이트에 도킹하면 되지만, 그러면 최대 10 ** 5 * 10 ** 5 계산으로 시간 초과가 된다.
A & (-A)가 가장 작은 1을 가지는 비트를 나타낸다는 점을 활용해, 게이트의 번호를 뒤집고, gi보다 높은 번호를 가진 비트 중 가장 낮은 비트의 1을 추출한다.
만약 A & (-A)가 0이라면 그런 비트가 없다는 것이므로 더이상 비행기를 도킹할 수 없다.
2 ** (10 ** 5)라는 무지막지하게 큰 수를 그냥 비트마스킹하는 나름 참신하다고 생각한 방법.

#!python

from sys import stdin

g = int(stdin.readline())
p = int(stdin.readline())
gis = [g - int(stdin.readline()) for _ in range(p)]
gates = 2 ** g - 1 # 게이트를 0b11111....1로 초기화
ans = 0

for gi in gis:
    temp = gates >> gi        # gi보다 높은 번호를 찾아야 하므로 시프트
    lowest = temp & (-temp)   # 가장 작은 비트 추출
    if not lowest:            # 가장 작은 비트가 없으면 탈출
        break
    ans += 1                  # 가장 작은 비트가 있다면 답의 개수를 증가시키고,
    gates ^= lowest << gi     # 게이트의 해당 비트를 0으로 변경

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑