DP다이나믹프로그래밍-30문제

 

1. 피보나치 수열 (Fibonacci Sequence) - 1. 피보나치 수열 및 변형 문제

• Problem 1: Fibonacci Number (LeetCode 509)
  설명: 피보나치 수열의 n번째 값을 계산합니다.
  핵심 개념: 재귀, 메모이제이션, 동적 계획법.
  링크: LeetCode 509
• Problem 2: 피보나치 수 5 (BOJ 10870)
  설명: n번째 피보나치 수를 구하는 문제입니다.
  핵심 개념: 재귀, 동적 계획법.
  링크: BOJ 10870

---

2. 계단 오르기 (Climbing Stairs) - 1. 피보나치 수열 및 변형 문제

• Problem 3: Climbing Stairs (LeetCode 70)
  설명: n개의 계단을 오르는 방법의 수를 계산합니다.
  핵심 개념: 동적 계획법, 피보나치 수열.
  링크: LeetCode 70
• Problem 4: 계단 오르기 (BOJ 2579)
  설명: 계단을 오를 때 얻을 수 있는 최대 점수를 계산합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 2579

---

3. 최대 부분 배열 합 (Maximum Subarray Sum) - 4. 부분 수열 및 배열 문제

• Problem 5: Maximum Subarray (LeetCode 53)
  설명: 연속된 부분 배열의 합 중 최대값을 찾습니다.
  핵심 개념: 카데인 알고리즘, 동적 계획법.
  링크: LeetCode 53
• Problem 6: 연속합 (BOJ 1912)
  설명: 연속된 부분 수열의 합 중 최대값을 구합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 1912

---

4. 최장 증가 부분 수열 (Longest Increasing Subsequence) - 4. 부분 수열 및 배열 문제

• Problem 7: Longest Increasing Subsequence (LeetCode 300)
  설명: 가장 긴 증가하는 부분 수열의 길이를 찾습니다.
  핵심 개념: 동적 계획법, 이분 탐색.
  링크: LeetCode 300
• Problem 8: 가장 긴 증가하는 부분 수열 (BOJ 11053)
  설명: 수열에서 가장 긴 증가하는 부분 수열의 길이를 구합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 11053

---

5. 0/1 배낭 문제 (0/1 Knapsack Problem) - 2. 배낭 문제 (Knapsack Problems)

• Problem 9: 0/1 Knapsack (HackerRank)
  설명: 무게 제한 내에서 아이템의 최대 가치를 찾습니다.
  핵심 개념: 동적 계획법.
  링크: HackerRank 0/1 Knapsack
• Problem 10: 평범한 배낭 (BOJ 12865)
  설명: 무게 제한이 있는 배낭에 담을 수 있는 최대 가치를 구합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 12865

---

6. 무제한 배낭 문제 (Unbounded Knapsack Problem) - 2. 배낭 문제 (Knapsack Problems)

• Problem 11: Unbounded Knapsack (HackerRank)
  설명: 아이템을 여러 번 선택할 수 있는 배낭 문제를 해결합니다.
  핵심 개념: 동적 계획법.
  링크: HackerRank Unbounded Knapsack
• Problem 12: 동전 1 (BOJ 2293)
  설명: 주어진 동전들로 특정 금액을 만드는 방법의 수를 구합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 2293

---

7. 최장 공통 부분 수열 (Longest Common Subsequence) - 3. 문자열 문제 (String Problems)

• Problem 13: Longest Common Subsequence (LeetCode 1143)
  설명: 두 문자열의 최장 공통 부분 수열의 길이를 찾습니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 1143
• Problem 14: LCS (BOJ 9251)
  설명: 두 문자열의 최장 공통 부분 수열의 길이를 구합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 9251

---

8. 집 도둑 문제 (House Robber Problem)

• Problem 15: House Robber (LeetCode 198)
  설명: 인접한 집을 털 수 없을 때 최대 훔칠 수 있는 금액을 계산합니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 198
• Problem 16: 도둑질 (프로그래머스)
  설명: 인접한 집을 털 수 없을 때 최대 이익을 계산합니다.
  핵심 개념: 동적 계획법.
  링크: 프로그래머스 도둑질

9. 최소 편집 거리 (Edit Distance) - 3. 문자열 문제 (String Problems)

• Problem 17: Edit Distance (LeetCode 72)
  설명: 두 문자열을 동일하게 만들기 위해 필요한 최소 편집 횟수를 계산합니다.
  핵심 개념: 동적 계획법, 문자열 비교.
  링크: LeetCode 72
• Problem 18: 단어 맞추기 (BOJ 7620)
  설명: 두 문자열 사이의 최소 편집 거리 계산 문제입니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 7620

---

10. 삼각형 경로 합 (Triangle Path Sum) - 그리드 기반 문제 (Grid-Based Problems)

• Problem 19: Triangle (LeetCode 120)
  설명: 삼각형 배열의 위에서 아래로 내려가는 경로의 최소 합을 구합니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 120
• Problem 20: 내려가기 (BOJ 1932)
  설명: 삼각형에서 위에서 아래로 내려가는 최대 경로 합을 구합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 1932

---

11. 독립 집합 문제 (Largest Independent Set)

• Problem 21: Binary Tree Maximum Path Sum (LeetCode 124)
  설명: 이진 트리에서 가장 큰 경로 합을 계산합니다.
  핵심 개념: 동적 계획법, 트리.
  링크: LeetCode 124
• Problem 22: 트리의 독립 집합 (BOJ 관련 문제 - 알고리즘 유사 활용 가능)
  설명: 트리에서 독립적인 노드 집합의 최대 크기를 찾습니다.
  핵심 개념: 동적 계획법, 트리 탐색.

---

12. 팰린드롬 문제 (Palindrome Problems)

• Problem 23: Longest Palindromic Subsequence (LeetCode 516)
  설명: 주어진 문자열에서 가장 긴 팰린드롬 부분 수열의 길이를 찾습니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 516
• Problem 24: Longest Palindromic Substring (LeetCode 5)
  설명: 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾습니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 5

---

13. 경로 문제 (Path Problems) - 그리드 기반 문제 (Grid-Based Problems)

• Problem 25: Unique Paths (LeetCode 62)
  설명: 격자에서 좌상단에서 우하단으로 가는 고유한 경로의 수를 계산합니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 62
• Problem 26: Minimum Path Sum (LeetCode 64)
  설명: 격자에서 좌상단에서 우하단으로 이동하며 합이 최소가 되는 경로를 찾습니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 64

---

14. 코인 체인지 문제 (Coin Change)

• Problem 27: Coin Change (LeetCode 322)
  설명: 특정 금액을 만들기 위해 필요한 최소 동전 수를 계산합니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 322
• Problem 28: 동전 1 (BOJ 2293)
  설명: 특정 금액을 만들 수 있는 경우의 수를 계산합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 2293

---

15. 타일링 문제 (Tiling Problems)

• Problem 29: Domino and Tromino Tiling (LeetCode 790)
  설명: 주어진 길이를 채우는 타일링 방법의 수를 계산합니다.
  핵심 개념: 동적 계획법.
  링크: LeetCode 790
• Problem 30: 2×n 타일링 (BOJ 11726)
  설명: 2×n 크기의 직사각형을 채우는 방법의 수를 계산합니다.
  핵심 개념: 동적 계획법.
  링크: BOJ 11726