solved.ac Class 5 all solve

 

Class 4를 푼지 반년이나 지났는데, 이제야 Class 5 문제들을 다 풀었다. 마찬가지로 기억에 남는 문제들을 정리해 보았다.

 

 

문제의 난이도는 골드 중상위부터 플5까지이다. 본격적으로 다양한 알고리즘이 등장하는 난이도인 만큼 dp, 그리디, 분할 정복, 그래프, 자료구조, 문자열까지 골고루 연습해볼 수 있었다. 그래프는 동작 원리만 잘 알고 있다면 대부분의 문제를 수월하게 풀 수 있었으나, dp 문제는 어느 정도의 응용을 요구하여 초기 세팅에 대해 꽤 고민해야 했다. 또한 읽고 나서도 어떤 알고리즘을 써야 할지 감이 잘 잡히지 않는 문제들도 있었는데, 이러한 문제들 역시 적절한 알고리즘 및 자료 구조를 이용해야 시간 제한을 통과할 수 있는 경우가 있어 꽤 까다로웠다. 골드 상위 문제들의 위력을 잘 보여주는 클래스가 아닌가 싶다.

 

 

투 포인터

Class 5에서 소개하고 있는 주요 개념 중 하나가 투 포인터이다. 개념은 정말 쉬운데 문제에서 활용하기가 은근히 까다롭고, 구현도 마냥 쉽지만은 않다. 용액(BOJ 2467)과 같은 정렬 가능한 리스트를 스캔하는 상황에서 투 포인터를 활용한다고 기억해 두자.

 

합이 0인 네 정수(BOJ 7453)은 생소한 조건과 제한으로 꽤 까다로운 문제인데, $n<4000$이므로 두 리스트(ab, cd)씩 합쳐 비교한다는 생각을 하게 된다. 파이썬의 제한으로는 다소 쉽지 않은데, 처음에는 딕셔너리나 Counter를 이용한 풀이를 떠올렸으나 결국 메모리 제한을 우려하여 투 포인터를 이용하였다. 중복이 포함되어 있기 때문에, 합이 0이 되는 경우 ab와 cd 각각에서 같은 값의 개수를 세어 곱해 주는 방식으로 문제를 풀 수 있다.

 

 

DP 테크닉

배낭 문제(knapsack)는 총 비용 제한 내에서 물품을 골라 가치를 최대화시키는 문제이다. 해법은 역시나 dp인데, '비용을 dp 배열로 관리한다'는 아이디어만 갖고 있으면 간단하게 구현이 가능하다.

 

유명한 문제인 행렬 곱셈 순서(BOJ 11049)은 2차원 dp 배열 dp[l][r]을 떠올리는 것이 제일 어렵다. 팰린드롬 분할(BOJ 1509) 역시 지극히 발상 위주의 문제다. 1차원 dp[i] = (0~i번째까지 최소 팰린드롬 분할의 수)로 정의하고, 팰린드롬 여부를 사전에 전처리하여 점화식을 세우면 된다.

 

RGB거리 2(BOJ 17404)는 순환 구조라서 까다롭다고 느낄 수 있는데, 시간 제한이 넉넉하므로 모든 가능한 초기 상태에 대해 반복하면 된다. 이 아이디어는 또다른 유명한 문제인 습격자 초라기에도 응용된다.

 

 

우선순위 큐의 활용

우선순위 큐(힙)는 범용성이 높은 만큼 생각지도 못한 문제에서 등장해 풀이에 항상 애를 먹는 것 같다. 아직 한 번에 아이디어를 떠올리는 것이 쉽지 않아 조금 더 연습이 필요해 보인다.

 

보석 도둑(BOJ 1202)을 보자. 그리디까지는 쉽게 파악할 수 있으나 가치가 가장 높은 보석을 $M \leq C$인 최소 $C$의 가방을 찾아 담아야 한다. 사용한 가방은 제외해야 하므로 list를 사용할 수는 없다. c++의 경우에는 red-black tree로 구현된 multiset 자료형을 이용하여 삽입, 삭제, 탐색(in $O(\log n)$)이 가능하지만, 파이썬에서는 대응되는 표준 라이브러리가 없어 구현하기 쉽지 않다.

 

방법은 크게 2가지라고 볼 수 있다. 먼저 union-find를 활용한 경로 압축이 있다. 전체 가방을 정렬한 후 사용하지 않은 최소 무게의 가방을 찾기 위해, 다음과 같이 $low[i]$를 정의한다.

 

$low[i]$ = ($bag[i]$보다 무거우면서, 사용되지 않은 최소 무게 가방의 인덱스)

 

 즉 $low[i]$를 통해 바로 점프할 수 있게 한다. 이제 $low[i]$를 union-find로 관리해 주면, $O(N\alpha(K))$만에 문제를 풀 수 있다(공항(BOJ 10775)도 같은 방식을 활용하는 문제이다).

 

보다 정석적인 방법으로, 우선순위 큐를 활용하여 풀 수 있다. 반대로 생각해서 가장 작은 가방부터 시작해, 해당 가방에 넣을 수 있는 보석 중 가장 가치가 높은 보석을 넣는 방식이다. 입력 및 삭제를 유연하게 수행하면서 빠르게 최댓값을 찾아야 하므로, 최대 힙을 이용하여 구현하면 되겠다. 입력과 삭제 횟수를 고려하면 $O((N+K)\log N)$만에 풀이가 가능하다.

 

 

클래스 5 중에서 푸는 데 가장 고생했던 문제인 문제집(BOJ 1766)도 우선순위 큐를 사용하는 문제다. dfs를 활용한 일반적인 위상 정렬의 형식에 너무 매몰되어 힙을 어떻게 적용해야 할 지 생각하지 못했던 것 같다. 이 문제는 'dfs를 이용한 탐색'보다 '작은 번호의 문제부터 접근'이 우선순위가 더 높으므로, 힙으로 먼저 감싸고 Kahn's Algorithm을 적용해 in_degree 배열을 관리하여 진입차수가 0인 노드들을 힙에 넣어주면 된다.

res = []
finished = [False]*(N+1)
while q:
    u = heapq.heappop(q)
    finished[u] = True
    res.append(u)
    for v in adj[u]:
        if finished[v]: continue
        in_degree[v] -= 1
        if in_degree[v] == 0:
            heapq.heappush(q, v)

 

 

그 외의 인상적인 문제들

비숍(BOJ 1799)은 은근히 빡빡하면서 일정 수준의 구현력을 요하는 백트래킹 문제다. 비숍이 아니라 룩이라면 좀 더 쉽지 않을까라는 생각에서 출발해 가면 흑/백 보드를 분리해서 45도 회전시켜 각각 $N \times N$ 크기의 배열로 관리하는 아이디어를 떠올릴 수 있다. 구현이 머리가 좀 아프다.

 

그래프 중에서는 배열 정렬(BOJ 28707)이 인상적이었다. 결국 다른 접근이 쉽지 않아 다익스트라를 이용하는데, $N$이 충분히 작아서 배열 상태를 visited에 그대로 저장하고도 다익스트라를 돌릴 수 있다.

 

트리의 순회(BOJ 2263)를 마지막에 풀었다. 분할 정복의 접근은 쉬운데 inorder와 postorder의 인덱스 차이를 잘 생각해야 한다. 결국 서브트리 내 노드의 개수는 정해져 있으므로, 순회 list 내에서 서브트리가 시작하는 위치만 offset 변수를 이용해 조절해 주면 문제를 풀 수 있다. 재귀를 사용할 때 핵심 로직만큼이나 중요한 것이 종료 지점 설정과 메모리 관리임을 느끼게 해준다.