김낭만

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

백준(BOJ) 26077 서커스 나이트 파이썬(Python)

문제 링크

에라토스테네스의 체(Sieve of Eratosthenes)와 유니온 파인드(Union-Find, Disjoint Set) 문제.
우선 유니온 파인드를 떠올리는 것은 어렵지 않다.
돌고래는 자기 ID의 1이 아닌 약수가 되는 주파수를 발생시키거나 들을 수 있는데, 이는 즉 같은 약수를 지닌 돌고래끼리 연결된다는 뜻이기 때문이다.
한편 약수보다는 배수가 다루기 쉬우니까 저 말을 뒤집어서, 어떤 주파수가 발생했을 때, 이를 들을 수 있는 돌고래는 그 주파수의 배수 돌고래라고 할 수 있다.
배수와 약수를 다루는 간단한 방법 중 하나는 에라토스테네스의 체이다.
발생할 수 있는 2부터 1000000까지의 주파수에 대해, 해당 주파수를 들을 수 있는 돌고래들을 모두 유니온하면 된다.
어떤 주파수에 대해 이를 들을 수 있는 돌고래는 주파수의 배수 ID를 가지는 돌고래이고, 따라서 이를 에라토스테네스의 체로 걸러내면 된다
몇 가지 조심할 부분이 있긴 하다.
우선 assert문을 통해 확인해본 결과 중복된 ID의 돌고래가 있는 것으로 보인다.
ID가 중복 가능하다는 게 별로 직관적인 부분은 아닌데, 아무튼 처음에 돌고래들의 연결 요소 크기를 무작정 1로 초기화하면 안될 듯 하다.
또, 단순히 범위 내의 소수를 확인하는 게 아니라 배수에 대해 유니온 파인드를 해주는 것이 목적이므로 \(\sqrt{N}\)이 아니라 \(N\), 적어도 \(N \over 2\) 범위를 모두 확인해야 한다.
이를테면 \(1009\)는 소수인데, 단순히 소수를 걸러내기 위해 에라토스테네스의 체를 활용한다면 \(1009^{2} > 1000000\)이므로 확인할 필요가 없지만, 돌고래 \(1009\)와 돌고래 \(2018\)은 공통된 약수를 지니는 돌고래이므로 유니온되어야 한다.
아무튼 그 외엔 큰 특이사항은 없고, 나름 참신한 문제라고 할 수 있다.

#!python


# 파인드 함수
def root(node):
    if parent[node] != node:
        parent[node] = root(parent[node])
    return parent[node]


# 유니온 함수
# 추가로 size 리스트를 갱신해서 연결 요소의 크기를 저장한다
def union(a, b):
    ra, rb = root(a), root(b)
    if ra == rb:
        return
    parent[ra] = parent[rb] = min(ra, rb)
    size[ra] = size[rb] = size[ra] + size[rb]


# n은 돌고래 수(안 씀), N은 id의 상한
n = int(input())
N = 1_000_000

# nodes는 돌고래 id들
# parent는 유니온-파인드를 위한 부모 노드 리스트
# size는 해당 노드가 포함된 연결 요소의 노드 개수
# visited는 해당 노드의 방문 여부
nodes = map(int, input().split())
parent = list(range(N + 1))
size = [0] * (N + 1)
visited = [False] * (N + 1)
ans = 0

# 노드를 순회하며 size를 갱신한다
# 기본적으로는 size가 1인데,
# 중복 id가 있는 것으로 보임
for node in nodes:
    size[node] += 1
    ans = max(ans, size[node])

# 에라토스테네스의 체
# 여기서 node는 돌고래의 id가 아니라
# 주파수를 의미한다
for node in range(2, N + 1):
    # 에라토스테네스의 체이므로
    # 합성수(이미 방문한 수)는
    # 다시 방문할 필요가 없다
    if visited[node]:
        continue

    # 소수 주파수에 대해 그 배수를 훑는다
    for mult in range(2 * node, N + 1, node):
        visited[mult] = True

        # 만약 주파수를 들을 수 있는 돌고래라면
        # 유니온한다
        if not size[mult]:
            continue
        union(node, mult)
        ans = max(ans, size[node])

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑