Coding Test/알고리즘 이론

Dynamic Programming (DP)-LeetCode

hyunkookim 2024. 12. 28. 22:11

1. 기본 DP (One-Dimensional DP)

Easy Problems

  1. Problem 1: Fibonacci Number (LeetCode 509)
    • 설명: 피보나치 수열의 nn번째 값을 계산합니다.
    • 핵심 개념: DFS, 메모이제이션, 점화식.
  2. Problem 2: Climbing Stairs (LeetCode 70)
    • 설명: 계단을 1칸 또는 2칸씩 올라가며 nn번째 계단에 도달하는 방법의 수를 구합니다.
    • 핵심 개념: DFS, DP-Bottom-Up, 점화식.
  3. Problem 3: Min Cost Climbing Stairs (LeetCode 746)
    • 설명: 계단을 오르는 최소 비용을 구합니다.
    • 핵심 개념: DP 배열, 점화식.
  4. Problem 4: Maximum Subarray (LeetCode 53)
    • 설명: 연속된 서브 배열의 최대 합을 구합니다.
    • 핵심 개념: DP 테이블, 상태 전이.
  5. Problem 5: House Robber (LeetCode 198)
    • 설명: 인접한 집을 털 수 없을 때 최대 얼마를 훔칠 수 있는지 계산합니다.
    • 핵심 개념: DFS, 메모이제이션.

Medium Problems

  1. Problem 1: Longest Increasing Subsequence (LeetCode 300)
    • 설명: 주어진 배열에서 가장 긴 증가 부분 수열의 길이를 구합니다.
    • 핵심 개념: DP 배열, 점화식.
  2. Problem 2: Word Break (LeetCode 139)
    • 설명: 문자열을 단어 사전에 있는 단어로 분할할 수 있는지 확인합니다.
    • 핵심 개념: 메모이제이션, 상태 전이.
  3. Problem 3: Coin Change (LeetCode 322)
    • 설명: 최소한의 동전 개수로 특정 금액을 구성합니다.
    • 핵심 개념: DP 배열, 점화식.
  4. Problem 4: Partition Equal Subset Sum (LeetCode 416)
    • 설명: 배열을 두 부분으로 나누어 각 부분의 합이 같은지 확인합니다.
    • 핵심 개념: DP 테이블, 부분 합.
  5. Problem 5: House Robber II (LeetCode 213)
    • 설명: 원형으로 배치된 집을 털 수 있는 경우 최대 얼마를 훔칠 수 있는지 계산합니다.
    • 핵심 개념: DP 배열, 두 케이스로 나누어 해결.

 

2. 이차원 DP (Two-Dimensional DP)

Easy Problems

  1. Problem 1: Unique Paths (LeetCode 62)
    • 설명: m x n 그리드에서 왼쪽 위에서 오른쪽 아래로 이동하는 경로의 수를 계산합니다.
    • 핵심 개념: DP 배열, 경로 계산.
  2. Problem 2: Minimum Path Sum (LeetCode 64)
    • 설명: 2D 그리드에서 왼쪽 위에서 오른쪽 아래로 이동할 때의 최소 경로 합을 구합니다.
    • 핵심 개념: DP 배열, 상태 저장.
  3. Problem 3: Pascal's Triangle (LeetCode 118)
    • 설명: 파스칼 삼각형을 생성합니다.
    • 핵심 개념: DP 배열, 중첩 상태 계산.
  4. Problem 4: Is Subsequence (LeetCode 392)
    • 설명: 문자열이 다른 문자열의 부분 수열인지 확인합니다.
    • 핵심 개념: DP 배열, 점화식.
  5. Problem 5: Counting Bits (LeetCode 338)
    • 설명: 0에서 nn까지 숫자에서 각 숫자의 1의 개수를 계산합니다.
    • 핵심 개념: DP 테이블, 점화식.

Medium Problems

  1. Problem 1: Longest Palindromic Substring (LeetCode 5)
    • 설명: 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾습니다.
    • 핵심 개념: DP 배열, 좌우 확장.
  2. Problem 2: Decode Ways (LeetCode 91)
    • 설명: 숫자 문자열을 문자로 변환할 수 있는 모든 방법의 수를 계산합니다.
    • 핵심 개념: DP 배열, 상태 저장.
  3. Problem 3: Unique Paths II (LeetCode 63)
    • 설명: 장애물이 있는 그리드에서 왼쪽 위에서 오른쪽 아래로 이동하는 경로의 수를 계산합니다.
    • 핵심 개념: DP 배열, 조건부 경로 계산.
  4. Problem 4: Triangle (LeetCode 120)
    • 설명: 삼각형 배열에서 위에서 아래로 이동하며 최소 합을 계산합니다.
    • 핵심 개념: DP 테이블, 하향식 접근.
  5. Problem 5: 0/1 Knapsack Problem (LeetCode 494)
    • 설명: 배열의 숫자로 특정 목표를 만들 수 있는 방법의 수를 계산합니다.
    • 핵심 개념: DP 배열, 부분 합.

 

3. DFS와 DP를 결합한 문제

이 카테고리는 DFS와 메모이제이션을 활용하여 상태를 저장하고 재사용하는 문제들입니다.

Easy Problems

  1. Problem 1: Fibonacci Number (LeetCode 509)
    • 설명: 피보나치 수열의 n번째 값을 계산합니다.
    • 핵심 개념: DFS, 메모이제이션, 점화식.
  2. Problem 2: Climbing Stairs (LeetCode 70)
    • 설명: 계단을 1칸 또는 2칸씩 올라가며 nn번째 계단에 도달하는 방법의 수를 구합니다.
    • 핵심 개념: DFS, DP-Bottom-Up, 점화식.
  3. Problem 3: Minimum Path Sum (LeetCode 64)
    • 설명: 2D 그리드에서 왼쪽 위에서 오른쪽 아래로 이동할 때 최소 경로 합을 구합니다.
    • 핵심 개념: DFS, DP 테이블.
  4. Problem 4: House Robber (LeetCode 198)
    • 설명: 인접한 집을 털 수 없을 때, 최대 얼마를 훔칠 수 있는지 계산합니다.
    • 핵심 개념: DFS, 메모이제이션.
  5. Problem 5: Unique Paths (LeetCode 62)
    • 설명: m x n 그리드에서 왼쪽 위에서 오른쪽 아래로 이동하는 경로의 수를 구합니다.
    • 핵심 개념: DFS, 메모이제이션.

Medium Problems

  1. Problem 1: Longest Increasing Subsequence (LeetCode 300)
    • 설명: 주어진 배열에서 가장 긴 증가 부분 수열의 길이를 구합니다.
    • 핵심 개념: DFS, 메모이제이션, DP 테이블.
  2. Problem 2: Word Break (LeetCode 139)
    • 설명: 문자열을 단어 사전에 있는 단어로 분할할 수 있는지 확인합니다.
    • 핵심 개념: DFS, 메모이제이션, 상태 저장.
  3. Problem 3: Partition Equal Subset Sum (LeetCode 416)
    • 설명: 배열을 두 부분으로 나누어 각 부분의 합이 같은지 확인합니다.
    • 핵심 개념: DFS, DP-Bottom-Up.
  4. Problem 4: Triangle (LeetCode 120)
    • 설명: 삼각형 배열에서 위에서 아래로 이동하며 최소 합을 구합니다.
    • 핵심 개념: DFS, DP 테이블.
  5. Problem 5: Coin Change (LeetCode 322)
    • 설명: 최소한의 동전을 사용해 금액을 만들 수 있는 방법을 구합니다.
    • 핵심 개념: DFS, DP-Bottom-Up.

 

4. 순수 DP 테이블 활용 문제

이 카테고리는 순수 DP 테이블을 사용하는 문제들로, 주로 상태를 업데이트하며 점진적으로 값을 계산합니다.

Easy Problems

  1. Problem 1: Maximum Subarray (LeetCode 53)
    • 설명: 연속된 서브 배열의 최대 합을 구합니다.
    • 핵심 개념: DP 테이블, 상태 전이.
  2. Problem 2: Best Time to Buy and Sell Stock (LeetCode 121)
    • 설명: 주식을 사고팔아 최대 이익을 구합니다.
    • 핵심 개념: DP 테이블, 단일 상태.
  3. Problem 3: Pascal's Triangle (LeetCode 118)
    • 설명: 파스칼 삼각형을 생성합니다.
    • 핵심 개념: DP 테이블.
  4. Problem 4: Is Subsequence (LeetCode 392)
    • 설명: 주어진 문자열이 다른 문자열의 부분 수열인지 확인합니다.
    • 핵심 개념: DP 테이블.
  5. Problem 5: Counting Bits (LeetCode 338)
    • 설명: 0에서 nn까지의 숫자에서 각 숫자의 1의 개수를 구합니다.
    • 핵심 개념: DP-Bottom-Up.

Medium Problems

  1. Problem 1: Longest Palindromic Substring (LeetCode 5)
    • 설명: 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾습니다.
    • 핵심 개념: DP 테이블.
  2. Problem 2: Decode Ways (LeetCode 91)
    • 설명: 숫자 문자열을 알파벳으로 변환할 수 있는 모든 방법의 수를 계산합니다.
    • 핵심 개념: DP 테이블.
  3. Problem 3: 0/1 Knapsack Problem (LeetCode 494)
    • 설명: 배열의 숫자를 더하고 빼서 목표 값을 만들 수 있는 방법의 수를 계산합니다.
    • 핵심 개념: DP 테이블, 부분 합.
  4. Problem 4: Minimum Edit Distance (LeetCode 72)
    • 설명: 두 문자열을 동일하게 만들기 위해 필요한 최소 편집 거리를 구합니다.
    • 핵심 개념: DP 테이블.
  5. Problem 5: Unique Paths II (LeetCode 63)
    • 설명: 장애물이 있는 그리드에서 왼쪽 위에서 오른쪽 아래로 이동하는 경로의 수를 구합니다.
    • 핵심 개념: DP 테이블.

 

5. 문자열 DP (String DP)

문자열 비교, 변환, 분할과 관련된 문제.

Easy Problems

  1. Problem 1: Is Subsequence (LeetCode 392)
    • 설명: 주어진 문자열 ss가 문자열 tt의 부분 수열인지 확인합니다.
    • 핵심 개념: DP 배열, 상태 전이, 문자열 매칭.
  2. Problem 2: Longest Common Subsequence (LeetCode 1143)
    • 설명: 두 문자열 간 가장 긴 공통 부분 수열의 길이를 찾습니다.
    • 핵심 개념: DP 테이블, 2D 배열, 상태 저장.
  3. Problem 3: Edit Distance (LeetCode 72)
    • 설명: 두 문자열을 동일하게 만들기 위한 최소 편집 거리를 구합니다.
    • 핵심 개념: DP 배열, 문자 삽입/삭제/수정 연산.
  4. Problem 4: Palindrome Partitioning (LeetCode 131)
    • 설명: 문자열을 여러 팰린드롬으로 분할합니다.
    • 핵심 개념: DP 배열, 팰린드롬 확인.
  5. Problem 5: Scramble String (LeetCode 87)
    • 설명: 두 문자열이 스크램블된 상태인지 확인합니다.
    • 핵심 개념: DP 배열, 문자열 트리 매칭.

Medium Problems

  1. Problem 1: Longest Palindromic Subsequence (LeetCode 516)
    • 설명: 문자열에서 가장 긴 팰린드롬 부분 수열의 길이를 찾습니다.
    • 핵심 개념: DP 테이블, 상태 전이, 이중 포인터.
  2. Problem 2: Distinct Subsequences (LeetCode 115)
    • 설명: 문자열 ss에서 문자열 tt로 매칭되는 모든 부분 수열의 개수를 계산합니다.
    • 핵심 개념: DP 테이블, 상태 저장.
  3. Problem 3: Interleaving String (LeetCode 97)
    • 설명: 두 문자열이 교차하여 세 번째 문자열을 형성할 수 있는지 확인합니다.
    • 핵심 개념: DP 테이블, 상태 전이.
  4. Problem 4: Minimum Insertion Steps to Make a String Palindrome (LeetCode 1312)
    • 설명: 문자열을 팰린드롬으로 만들기 위한 최소 삽입 횟수를 계산합니다.
    • 핵심 개념: DP 배열, 상태 저장, 점화식.
  5. Problem 5: Wildcard Matching (LeetCode 44)
    • 설명: 문자열과 와일드카드 패턴이 매칭되는지 확인합니다.
    • 핵심 개념: DP 테이블, 상태 저장.

 

6. 상태 기반 DP (State-Based DP)

특정 상태(예: 부분 합, 이전 선택)에 따라 결과가 달라지는 문제.

Easy Problems

  1. Problem 1: Climbing Stairs (LeetCode 70)
    • 설명: 계단을 1칸 또는 2칸씩 올라가며 nn번째 계단에 도달하는 방법의 수를 구합니다.
    • 핵심 개념: DP 배열, 점화식.
  2. Problem 2: House Robber (LeetCode 198)
    • 설명: 인접한 집을 털 수 없을 때 최대 얼마를 훔칠 수 있는지 계산합니다.
    • 핵심 개념: DP 배열, 메모이제이션.
  3. Problem 3: Min Cost Climbing Stairs (LeetCode 746)
    • 설명: 계단을 오르는 최소 비용을 계산합니다.
    • 핵심 개념: DP 배열, 점화식.
  4. Problem 4: Paint House (LeetCode 256)
    • 설명: 최소 비용으로 집을 칠하는 방법을 계산합니다.
    • 핵심 개념: DP 테이블, 상태 저장.
  5. Problem 5: Maximum Subarray (LeetCode 53)
    • 설명: 연속된 서브 배열의 최대 합을 구합니다.
    • 핵심 개념: DP 배열, 카데인 알고리즘.

Medium Problems

  1. Problem 1: Job Scheduling (LeetCode 1235)
    • 설명: 최대 이익을 내는 작업 스케줄링을 계산합니다.
    • 핵심 개념: DP 배열, 이진 검색.
  2. Problem 2: Burst Balloons (LeetCode 312)
    • 설명: 풍선을 터뜨려 최대 코인을 얻는 방법을 계산합니다.
    • 핵심 개념: DP 테이블, 상태 저장.
  3. Problem 3: Best Time to Buy and Sell Stock III (LeetCode 123)
    • 설명: 두 번의 거래로 최대 이익을 계산합니다.
    • 핵심 개념: DP 배열, 상태 저장.
  4. Problem 4: Best Time to Buy and Sell Stock IV (LeetCode 188)
    • 설명: 최대 kk번의 거래로 최대 이익을 계산합니다.
    • 핵심 개념: DP 테이블, 상태 저장.
  5. Problem 5: Russian Doll Envelopes (LeetCode 354)
    • 설명: 러시아 인형처럼 중첩 가능한 봉투의 최대 개수를 계산합니다.
    • 핵심 개념: DP 테이블, 이진 검색.

'Coding Test > 알고리즘 이론' 카테고리의 다른 글

우선순위 큐  (1) 2024.12.29
후위 순회의 역순  (1) 2024.12.29
강하게 연결된 요소(a strongly connected component)-LeetCode 문제  (2) 2024.12.28
위상정렬 - Leetcode 문제(Medium 레벨)  (2) 2024.12.28
위상정렬 - Leetcode 문제(Easy 레벨)  (0) 2024.12.28

'Coding Test/알고리즘 이론'의 다른글

  • 현재글Dynamic Programming (DP)-LeetCode

관련글

티스토리툴바