solved.ac Class 4 all solve

4단계를 다 풀었다. 난이도는 실버 상위~골드 하위 수준이고 dp, 그래프 탐색, 백트래킹, 구현 위주의 문제가 많았다. 한문제씩 풀 때는 그렇게 오랜 시간이 걸리지 않았는데, 확실히 정해진 48문제를 다 푸는 것은 마냥 쉽지는 않은 것 같다. 푼 문제 수가 늘어갈수록 남아있는 문제들은 더 까다롭게 다가오는 느낌이었다. 아이디어가 떠오르지 않아서 자력으로 푸는 데 꽤 많은 시도를 한 문제들도 있었다. 아무튼 이번에 새로 배웠거나 헷갈리는 개념(문제)들 위주로 간단히 정리해 본다.

 

 

LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)

LIS 자체는 dp로 $O(N^2)$만에 해결 가능하다. 수열 $A$에 대해 $dp[i]$=($A[i]$까지의 LIS)라고 생각하면, $j=0,\cdots,i-1$에 대해 다음과 같은 점화식을 쉽게 도출할 수 있다.

 

$$dp[i]=\max(\left\{dp[j]\;|\;A[j]<A[i]\right\})+1$$

 

조금 더 생각해 보면 $O(N\log N)$ 시간복잡도의 알고리즘도 생각해 볼 수 있다. $B[k]$=($k=dp[i]$가 되도록 하는 $A[i]$의 최솟값)으로 별도의 배열을 만들어서 관리해 주면, 배열 $B$는 정렬된 상태를 유지할 것이므로 파라메트릭 서치(이분 탐색)을 이용해 풀 수 있다. $B[x] \geq A[i]$인 $x$의 최솟값을 인덱스로 하여 업데이트해 주면 되므로, bisect_left를 이용한다.

dp = [0]*N
B = list()
for i in range(N):
    x = bisect_left(B, A[i])
    if x == len(B): B.append(A[i])
    else: B[x] = A[i]

    dp[i] = x+1

 

 

 

LCS(Longest Common Subsequence, 가장 긴 공통 부분 수열)

LCS도 dp로 해결하는데, 생각하기가 조금 더 까다롭다. 해결 방법은 두 수열 $A, B$의 길이 $N, M$에 대해 $N \times M$짜리 2차원 dp를 돌리는 것이다. $dp[i+1][j+1]$=($A[i], B[j]$까지의 LCS)라 생각하면, 다음과 같은 로직으로 해결 가능하다.

 

• 만약 $A[i] = B[j]$라면, $dp[i+1][j+1]=dp[i][j]+1$
• 아니라면, $dp[i+1][j+1] = \max(dp[i+1][j], dp[i][j+1])$

Class 4에 LCS와 함께 '사전 순 최대 공통 수열'(BOJ 30805)이라는 문제가 있어 한 번 낚였다.. 해당 문제는 길이보다 사전 순으로 뒤에 있음을 우선시하기 때문에, 단순히 수열의 남은 부분의 공통 원소들 중 최댓값을 뽑아내는 것으로 greedy하게 해결해야 한다.

 

 

숨바꼭질 2(BOJ 12851)

까탈스럽게 느껴질 수도 있지만 좋은 문제이다. 다음 두 가지 사실을 알게 해준다.

 

• 탐색(BFS) 시 큐에 넣기 전에 방문 처리를 하는 것이 더 효율적이라는 점
• visited 배열의 활용: bool 대신 int로 설정해 해당 지점을 방문한 횟수를 counting할 수 있다. 이때 visited[v]=visited[u]+1인지 검사하면 최단 거리로 방문했는지도 확인 가능하다.

 

웜홀(BOJ 1865)

제한을 고려했을 때 플로이드-워셜으로 풀릴 수도 있겠다 싶었는데, python이 쉽게 허락해 주지 않는다.. 대신 음수 사이클을 검사하는 문제로 생각하여 벨만-포드를 사용할 수 있다. 다만 원래 목적이 '한 점에서부터 최단 거리'를 구하도록 설계된 것과 달리, 음수 사이클을 검출하는 용도로 벨만-포드를 사용하고 있기 때문에, 변형을 좀 거쳐야 한다.

 

• 실제 최단 거리의 값보다는 갱신 여부가 더 중요하므로, 초기 거리를 임의로 설정해도(ex. dist = [0]*(N+1)) 무방하다. 다만 float('inf')로 설정하면 초기 점에서 도달하지 못한 점에서는 갱신 여부 파악이 불가능해 틀리게 된다.
• 만약 벨만-포드를 그대로 이용하려면, 모든 점에 대해 확실히 방문할 수 있도록 하기 위해 방문하지 않은 남은 점들에 대해 추가로 벨만-포드를 수행해야 한다. 물론 이렇게 구현하기보다는 앞서 말한 것처럼 구현하는 것이 더 효율적일 것이다.

dist = [0]*(N+1)
res = False
for i in range(N):
    for u, v in edges:
        if (new_dist := dist[u]+edges[(u, v)]) < dist[v]:
            dist[v] = new_dist
            if i == N-1:
                res = True
                print("YES")
                break
if not res: print("NO")

 

 

 

후위 표기식(BOJ 1918)

차량기지 알고리즘으로 알려져 있는 매우 유명한 문제이니 설명은 생략한다. 처음 풀 때는 스택으로 푼다는 아이디어 정도만 갖고 도전해봤는데, 은근 발상이 쉽지 않다. 괄호 처리에 대해 중점적으로 생각해 보면 좋다.

 

1. 들어오는 연산자보다 우선순위가 같거나 높은 연산자는 pop한다.
2. 왼쪽 괄호: 우선순위가 제일 높은 연산자로 취급한다.
3. 오른쪽 괄호: 괄호 안쪽에 대해서는, 1번 때문에 stack상에 우선순위 오름차순으로 정렬되어 있음이 보장된다. 따라서 별도의 처리 없이 왼쪽 괄호가 나올 때까지 pop하면 된다.