알고리즘 스터디 Recap (DP &Dijkstra)

📍Recap Day

: 이번주는 지금까지 진행했던 주제의 문제 중에서 못 푼 문제를 해결하고 공유!

1️⃣ DP & DnC

점화식이 필요한 문제는 DP 혹은 DnC?!?

• 알고리즘 공부하고 계속 점화식을 보면 DP 혹은 DnC를 떠올렸는데,,

  단방향으로 흘러갈 때 분할 정복,
  작은 값을 구해 큰 값에 사용해야 할 때 DP를 흔히 사용한다고 생각

  
  ↑ 이 말을 들으니,, 틀렸을지도 모른다는 생각이 들어따.. 그래서 GPT한테 물어봄

  • DP와 DnC 유형을 구분하는 기준을 세우자면 점화식인가?!? 보다는 부분 문제가 서로 독립적인가!? 가 더 잘 맞는다고 함..

  • DP는 부분 문제가 중복되어서 같은 연산을 반복적으로 해야하는 경우에 더 적합하고 DnC는 부분 문제가 독립적일 때 더 적합하다고 함

    

• DP(Top-Down) vs DnC

  • DP(Top-Down)도 재귀를 사용해서 약간 DnC랑 비슷해 보인다!

  • DP의 핵심은 “메모이제이션”!! DnC와는 다르게 중간 결과값을 기록해서 중복 연산을 방지함

    

🤔 재사용이랑 병합이 뭐가 달라?

: 다르다는 건 알겠는데 미묘한 차이가 있다고 느낌적으로밖에 모르겠음..ㅎ

본질적으로 “병합” 은 독립적인 결과를 합치는 과정이고,
“재사용” 은 중복된 계산을 피하기 위한 과정

• 병합 (Merge) → 여러 개의 부분 문제를 해결한 후 결과를 합쳐서 답을 구하는 과정
• 재사용 (Reuse) → 이전에 계산한 결과를 다시 사용하여 중복 계산을 줄이는 과정

  ⇒ 핵심 차이는 중복 계산을 줄이는 목적이 있는가?!? 로 이해하자

점화식 문제를 그럼 어떻게 접근할까!

1. 일단 DP를 먼저 떠올려보자!

   • 점화식은 일반적으로 이전의 값을 이용하여 현재 값을 결정하는 구조

   • 작은 작업으로 쪼개도 그 작업이 서로 독립적인 작은 작업이 아닐 가능성이 높음
     → 만약 독립적인 부분 작업으로 나뉘면 여기서 바로 DnC을 적용

   • 그러니 DnC 보다는 DP를 먼저 떠올리는게 좋다~

2. 근데 이제 $N$이 크면?!? DnC를 적용해서 최적화해보자!

   • $N$이 커서 시간초과가 날 것 같다면 DnC를 적용해서 DP를 최적화할 수 없을 지 생각해보자

   • DP는 일반적으로 시간복잡도가 $O(N)$.. 근데 $N$이 너무 크면 이것도 시간 초과 날 수도 있음

   • DnC를 적용해서 $O(log N)$으로 최적화할 수 있을지 생각해보자

     • 점화식을 행렬 거듭제곱으로 표현하는 등의 방식으로 DnC 적용 가능

2️⃣ 점화식을 행렬 곱으로 표현해보자!

점화식이 선형 관계를 가지면 행렬 곱셈으로 변환 가능!

• 선형 관계의 점화식

  • $F_{n+2} = F_{n+1} + F_{n}$ (피보나치 수열 점화식) 처럼 표현되는 점화식.
    그러니까..

  • $p_0A_n+p_1A_{n−1}+p_2A_{n−2}+⋯+p_{k−1}A_{n−k+1}=0$
    (단 $n≥k$ 이고 $p_1, p_2 ⋯p_{k-1}$은 상수)

  • 처럼 어떤 항의 값을 다른 항의 상수곱의 합으로 표현 가능한 점화식

• 행렬곱으로 어떻게 표현할까!

  • $F_{n+2} = aF_{n+1} + bF_{n}$ ($a, b$는 상수)
    

  • $\begin{bmatrix}F_{n+1} \\ F_{n} \\ \end{bmatrix} = \begin{bmatrix}a&b \\ 1&0\end{bmatrix}^{n}\begin{bmatrix}F_{1} \\ F_0\end{bmatrix}$

    
    
  • 구하는 과정 [접기/펼치기]

    1. 두 개의 관계식을 뽑기
    

    $\begin{bmatrix}F_{n+2} \ F_{n+1}\end{bmatrix}^T$ 의 형태를 표현하는 행렬곱을 만들어야하므로 $F_{n+1}$ 에 대한 등식 하나 더 뽑기

    $$ \begin{aligned} F_{n+2} &= aF_{n+1} + bF_{n} \\ F_{n+1} &= F_{n+1} \end{aligned} $$

    2. 이제 각 등식의 계수를 활용해서 $u_{k+1} = A u_{k}$ 형태로 표현

       $$ \begin{bmatrix}F_{n+2} \\ F_{n+1} \\ \end{bmatrix} = \begin{bmatrix}a&b \\ 1&0 \end{bmatrix} \begin{bmatrix}F_{n+1} \\ F_n \end{bmatrix} $$

    3. 등비수열 형태가 되었으니 $u_n = A^{n-1} u_0$ 으로 표현 가능

       $$ \begin{bmatrix}F_{n+1} \\ F_{n} \\ \end{bmatrix} = \begin{bmatrix}a & b \\ 1 & 0 \end{bmatrix}^{n} \begin{bmatrix}F_{1} \\ F_0 \end{bmatrix} $$

🤔 다시 생각해본 피보나치 수 6 문제 접근 방법

1. DP로 접근
2. $N$이 크니까 행렬곱의 형태로 점화식을 수정
3. 행렬 제곱 연산을 해야하므로 DnC 활용

DP 시간 복잡도를 DnC로 최적화하는 방법?

• 점화식을 행렬 곱셈으로 변환 ← 위에서 설명한 그거

• DnC Optimization (참고🔗)

  • 언제 가능?

    • $dp[i][j] = \min_{k}(dp[i][k] + dp[k+1][j] + C(k))$← 이런 형태의 점화식 문제에서 활용

    • 최적 $k$값이 항상 오른쪽으로 이동하는 모노톤 속성 (Monotonicity Property)을 만족해야 활용 가능
      → 그니까 “단방향으로 흘러갈 때 분할 정복“이 가능하니까 이런 속성을 얘도 가지고 있어야함

  • 뭐라는 거야? 예제로 이해해보자 [접기/펼치기]

         🏠 집1 - 2km - 🏪 슈퍼1 - 3km - 🏠 집2 - 2km - 🏪 슈퍼2 - 4km - 🏠 집3 - 5km - 🏪 슈퍼3

    • 마을에 N개의 집이 있고, M개의 슈퍼마켓이 있을 때 각 집에서 가장 가까운 슈퍼마켓을 찾아야 함
      ⇒ 각 집이 어느 슈퍼마켓에 배정되는지를 빠르게 찾아라!

    • 가장 가까운 슈퍼마켓 은 항상 한 방향(오른쪽)으로 이동
      = 집이 오른쪽으로 갈수록 가까운 슈퍼마켓도 오른쪽으로 이동해야 함!

    • 이진 탐색과 비슷한 방식으로 탐색해서 빠르게 구해보자!

    • 과정

      🏠 집1 (1km)  🏠 집2 (5km)  🏠 집3 (10km)  🏠 집4 (15km)
               🏪 슈퍼1 (3km)   🏪 슈퍼2 (8km)   🏪 슈퍼3 (13km)

    1. 집 리스트 반으로 나누기

        🏠 집1 (1km)  🏠 집2 (5km)   |   🏠 집3 (10km)  🏠 집4 (15km)

    2. 왼쪽 절반 (집1, 집2)에 대해 슈퍼마켓 찾기

       • 집1 (1km)은 슈퍼1 (3km)이 가장 가깝다.
       • 집2 (5km)은 슈퍼1 (3km)이 가장 가깝다.

    3. 오른쪽 절반 (집3, 집4)에 대해 슈퍼마켓 찾기

       • 집3 (10km)은 슈퍼2 (8km)이 가장 가깝다.
       • 집4 (15km)은 슈퍼3 (13km)이 가장 가깝다.

    4. 최종 결과

       집 위치	가장 가까운 슈퍼마켓 위치
       집1 (1km)	슈퍼1 (3km)
       집2 (5km)	슈퍼1 (3km)
       집3 (10km)	슈퍼2 (8km)
       집4 (15km)	슈퍼3 (13km)

DnC Optimization 중 하나로 얘도 어려운 문제에 나오더라..나중에 하자...

🔥 (번외) DP 최적화하는 방법

• DP도 $N$이 공간복잡도와 시간복잡도가 너무 커질 수 있어서 이를 최적화하는 방법이 있다 함
• 근데 이 내용은 현재 나에게는 난이도가 아주 높은 문제 풀이에 필요한 지식인 것 같아서 일단 읽어만 봤음
• 나중에 좀 더 다양한 문제 연습해보고 이 개념이 필요한 문제를 풀게 되면 정리해보겠음!! (지금 나에겐 과하다..)
• 한번 쭉 읽었던 포스트는 ⬇️⬇️ [접기/펼치기]

  • 구사과 동적 계획법을 최적화하는 9가지 방법 (1/4)
  • 구사과 동적 계획법을 최적화하는 9가지 방법 (2/4)
  • 구사과 동적 계획법을 최적화하는 9가지 방법 (3/4)
  • 구사과 동적 계획법을 최적화하는 9가지 방법 (4/4)

3️⃣ 다익스트라 내용 정리

‘데이크스트라’라고 해야 하나..? 걍 다익스트라라고 할래

Dijkstra 다익스트라 알고리즘?

• 한 정점(Vertex 또는 Node)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘

• 최단 경로를 구하는데 활용됨

  • Edge 마다 가중치가 다를 때 활용

  • 가중치는 음수가 아님

• Greedy & DP 개념이 결합된 알고리즘

  • Greedy : 현재 가장 짧은 경로를 선택하면 전체 최적해를 구할 수 있음

  • DP : 각 정점까지의 최단 거리를 점진적으로 구하고 저장해서 다음 단계에서 재활용

• Visited 처리할 필요 X ?

  • 최단 거리만 있으면 되는 경우엔 O

  • 우선순위 큐를 사용해서 최단 거리인 노드를 먼저 처리하기 때문에 이미 처리한 노드는 최단 거리가 확정된 상태

  • 방문 처리를 하지 않아도 해당 경로에서 이미 방문했던 노드는 뒤쪽으로 밀림

  ⇒ BFS로 경로를 탐색하면서 현재까지 구한 경로 중 가장 최단 거리인 경로를 우선적으로(우선순위 큐) 탐색하면서 처리

최단 거리로 갈 수 있는 경로도 구해야할 때?

: 다익스트라로 최단 거리를 찾으면서 중간중간 방문한 노드를 기록하여 최단 거리를 구한 후 경로를 역추적

• 언제 경로를 저장할까

  • 경로 탐색 중 우선순위 큐에서 노드를 뽑아 그 후에 방문할 노드를 탐색할 때

  • 만일 현재 조회하는 노드를 방문할 때의 경로가 기존의 경로보다 가중치가 낮으면 부모 노드 갱신

  • 여기서 부모 노드는 바로 직전에 방문한 노드 → 어디에서 이 노드로 왔는지를 저장

• 경로 저장은 배열에 저장하거나 아니면 부모 노드를 가리킬 수 있는 Node 클래스에 저장

• 각 노드에 최단 거리 경로에 위치하는 부모 노드가 저장되어 있으므로 도착 지점에서 역추적해 시작 지점까지 경로를 찾을 수 있음

🤔 경로가 다양하게 나올 경우, 모든 경로를 구해야 한다면?

• 부모 노드를 배열에 저장하는 게 아니라 부모 노드를 배열로 저장.. (후보를 모두 박아 넣겠다!)
• 출발할 때와 되돌아올 때 둘 다 다익스트라로 풀이
• 경로를 DFS로 찾으면서 최단 거리보다 거리값이 커지면 Pruning