[swjungle] WEEK03 - 알고리즘 주차 [ 01 ~ 03 ]

동적 프로그래밍(Dynamic Programming)

• 정의

  - 큰 문제를 작은 부분 문제로 나누어 해결한 후, 그 결과를 활용하여 큰 문제를 해결하는 방법 - 부분 문제의 해답을 저장하여 중복 계산을 방지함으로써 효율성을 높임

• 특징

  - 중복되는 부분 문제의 해답을 메모리에 저장하여 재사용 - 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)의 성질을 가짐

• 분할 정복과의 차이점

  - 분할 정복: 부분 문제가 중복되지 않음, 부분 문제의 해답을 재활용하지 않음 - 동적 프로그래밍: 부분 문제가 중복되며, 부분 문제의 해답을 재사용함

• 동적 프로그래밍 방법론

  - 탑다운(Top-down) 방식: 메모이제이션(Memoization)을 활용하여 큰 문제를 작은 문제로 나누어 해결 - 바텀업(Bottom-up) 방식: 작은 문제부터 차례대로 해결하여 큰 문제의 해답을 구함

• 피보나치 수열 예시

  • 탑다운 방식 (메모이제이션)

def fib(n, memo):
    if n <= 1:
        return n
    if memo[n] != -1:
        return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

n = 10
memo = [-1] * (n+1)
print(fib(n, memo))

• 바텀업 방식

def fib(n):
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

n = 10
print(fib(n))

• 느낀 점

  - 재귀 함수도 충분히 효율적인 코드라고 생각했는데, 그건 나의 기준이었고 컴퓨터가 계산하기에는 메모이제이션을 활용한 DP가 필요하다는 것을 알았습니다. - 탑다운 방식과 바텀업 방식의 차이점을 이해하고, 문제에 따라 적절한 방식을 선택하는 것이 중요하다는 것을 알았는데, 아직은 바텀업부터 익숙해진 다음에 탑다운을 노려봐야할 것 같았습니다. - 동적 프로그래밍을 적용할 수 있는 문제임을 파악하고, 점화식을 세우는 능력을 기르는 것이 중요하다고 느꼈습니다.

그리디 알고리즘(Greedy Algorithm)

• 정의

  - 매 순간 최적의 선택을 하는 방법으로 문제를 해결하는 알고리즘 - 현재 상황에서 가장 좋아 보이는 것을 선택하며, 전체에서 최적값을 구하는 것이 목표

• 느낀 점

  - DP를 풀다와서 그런지 그리디 알고리즘은 바로 직관적으로 이해가 돼서 너무 좋았습니다. - 그리디 알고리즘을 적용할 수 있는 문제를 파악하는 능력이 중요하다고 느꼈습니다.

어려웠던 문제: LCS(최장 공통 부분 수열)

LCS 문제는 동적 프로그래밍의 대표적인 예시 중 하나입니다. 두 문자열이 주어졌을 때, 두 문자열에 공통으로 존재하는 부분 수열 중 가장 긴 것의 길이를 찾는 문제입니다.

처음에는 문제를 이해하는 것부터 어려움을 겪었습니다. 부분 수열의 개념과 두 문자열에서 공통으로 존재하는 부분 수열을 찾는 방법이 직관적으로 와닿지가 않았다. (이걸 어떻게 재활용하라는거지??)

답을 보니, LCS(i, j)를 i번째 문자와 j번째 문자까지 고려했을 때의 LCS 길이라고 정의하고 시작했다.

def LCS(A, B):
    n, m = len(A), len(B)
    dp = [[0] * (m+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[n][m]

관련해서 간단한 예시코드인데, dp[i][j]는 A의 i번째 문자와 B의 j번째 문자까지 고려했을 때의 LCS 길이.

코드의 동작 방식
1. A의 i번째 문자와 B의 j번째 문자가 같은 경우 (A[i-1] == B[j-1]), 이 문자를 LCS에 포함시킬 수 있습니다. 따라서 dp[i][j]는 dp[i-1][j-1]에 1을 더한 값이다.
2. A의 i번째 문자와 B의 j번째 문자가 다른 경우, LCS에는 둘 중 하나의 문자만 포함될 수 있습니다. 이때는 dp[i-1][j]와 dp[i][j-1] 중 더 큰 값을 dp[i][j]에 저장합니다.

이렇게 점화식을 통해 부분 문제의 해답을 재활용하면서 전체 문제의 해답을 구할 수 있습니다.

LCS 문제를 해결하고 나서도 다른 DP 문제에서 어려움을 겪었습니다. DP 문제마다 점화식을 세우는 방법이 달랐고, 답을 보더라도 이해하기까지 좀 시간이 소요됐다. DP는 이후에도 정말 많이 풀면서 문제 해결과정 프로세스?를 좀 머리 속 DB에 저장해야할 것 같았습니다.

느낀 점

특히 동적 프로그래밍하면서 가장 크게 느낀점은 수학적인 사고력이 필요하다는 것을 깊게 체감했습니다.

지속적으로 풀면서 수학적 사고를 늘리는 방법밖에 없을 것 같았다. 그래서 어려운 카테고리로 뽑히는건가 싶었다.

다음 주 계획

• DP 유형별 문제 풀이

  - 펠린드롬을 비롯한 백준 DP분야에서 쉬운것부터 다 풀어보기

• 4주차 OS 개념 학습을 위한 C언어 공부

  - C언어 기본 문법 학습 - 자료구조(연결 리스트, 스택, 큐 등) 구현 연습

3주차에는 문제 풀이와 함께 4주차에 예정된 OS 개념 학습을 위해 C언어도 병행하여 공부할 계획입니다. C언어로 기본적인 자료구조를 구현해보면서 빠르게 따라잡을 수 있게 기반을 마련해놔야할 것 같습니다.