[묘공단]코딩 테스트 합격자 되기(10주차) 동적 계획법

Erdos·2024년 3월 10일

책감상 코딩테스트

코딩테스트

목록 보기

18/20

📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

🗓️TIL (this week I learned)
월 여행
화
수 몸풀기 문제2, 조약돌
목
금 -------------------------- 이 날까지 완료

15-1 동적 계획법 개념 ⭐⭐

dynamic programming: 한 번에 문제 해결 x, 작은 부분 문제들을 해결하고 이를 활용하여 전체 문제를 해결하는 방법
조건
- 큰 문제를 작은 문제로 나누었을 떄 동일한 작은 문제가 반복해서 등장해야 한다.
- 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다.
점화식: 팩토리얼, 재귀 활용
메모이제이션(memoization): 재귀 호출의 횟수를 줄이는 방법

최장 증가 부분 수열

long increasing subsequence(LIS): 부분 수열의 원소가 오름차순을 유지하면서 길이가 가장 긴 수열, 주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 알고리즘.
점화식
- dp[n] = 수열의 길이를 저장하는 배열(n번째 수로 끝나는 부분 수열 중 가장 긴 것의 길이를 저장)
- dp[N] = max(dp[K]) + 1(단, K는 1 <= K < N, arr[K] < arr[N])
- dp[1] = 1(종료 조건) <- 🤔🤔🤔🤔🤔??

def lis(arr):
    n = len(arr)

    # DP 배열 초기화: 모든 요소가 자기 자신만을 포함하는 길이 1의 LIS를 형성한다.
    dp = [1] * n

    # DP 배열이 의미하는 바: dp[i]는 arr[i]를 마지막으로 하는 LIS의 길이를 나타낸다.
    
    # 배열의 각 요소에 대해
    for i in range(1, n):
        for j in range(i):
            # 증가하는 부분 수열을 찾으면 DP 배열 업데이트
            if arr[i] > arr[j] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1

    # DP 배열의 최대값을 찾아 반환
    return max(dp)

시간복잡도: O(n^2)
해당 알고리즘으로 풀 수 있는 문제 예시
- 주어진 배열에서 최장 증가 부분 수열의 길이를 찾는 문제
- 시퀀스 정렬 문제에서 최적 부분 구조 찾기

최장 공통 부분 수열

longest common subsequence(LCS): 두 수열이 어떤 기준에 따라 양쪽에서 공통으로 발견 될 수 있는 가장 긴 부분 수열, 두 문자열에서 가장 긴 공통 부분 문자열을 찾는 알고리즘.
점화식 LCS(i,j)
- LCS(0,0) = 0
- x[i] == y[j]이면 LCS(i-1, j-1) + 1
- x[i] != y[j]이면 max(LCS(i-1, j), LCS(i, j-1))

def LCS(X, Y):
  # DP 테이블 초기화
  dp = [[0] * (len(Y) + 1) for _ in range(len(X) + 1)]
  
  # DP 테이블 채우기
  for i in range(1, len(X) + 1):
      for j in range(1, len(Y) + 1):
          if X[i - 1] == Y[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[len(X)][len(Y)]

시간복잡도: O(m*n) → m,n은 각각 두 문자열의 길이
해당 알고리즘으로 풀 수 있는 문제 예시
- DNA 서열 정리
- 텍스트 비교 및 유사도 측정

문제

[묘공단]코딩 테스트 합격자 되기(10주차) 동적 계획법

코딩테스트

15-1 동적 계획법 개념 ⭐⭐

최장 증가 부분 수열

최장 공통 부분 수열

문제

1. 피보나치 수

2. 2 x n 타일링

3. 정수 삼각형

4. 땅따먹기

5. 도둑질(고난이도)

6. 가장 큰 정사각형 찾기

7. 단어 퍼즐

추천 문제

[묘공단]코딩 테스트 합격자 되기(9주차) 정렬, 시뮬레이션

[묘공단]코딩 테스트 합격자 되기(11주차) 그리디

0개의 댓글