BJ9251 LCS(Longest Common Subsequence, 최장 공통 부분 수열)

https://www.acmicpc.net/problem/9251

 

 

🚀 Dynamic Programming (DP) 이해하기!

🧩 DP = 완전탐색(Brute Force) + 메모이제이션(Memoization)

---

🏗 DP의 핵심 개념

1️⃣ 완전탐색처럼 모든 경우의 수를 생각 🤯
2️⃣ 그 구조를 만들면서 점화식(Recurrence Relation)을 유도 🔄
3️⃣ 계산된 값을 저장하여 중복 계산을 방지 (메모이제이션) 💾

---

📌 메모이제이션(Memoization) 이란?

📂 이미 계산된 값을 저장하고 재사용하는 것!
📦 어디에 저장할까?
✅ array (배열)
✅ map (해시맵)
✅ set (중복 방지)

---

🔄 DP 해결 방식

🔼 Top-Down (재귀, 직관적) 🛠

• 재귀를 사용해 큰 문제를 작은 문제로 쪼개서 해결
• 이미 계산된 값이 있으면 반환 (메모이제이션 활용)
• ❌ 단점: 재귀 호출 오버헤드 발생 (느릴 수 있음!)

🔽 Bottom-Up (반복, 효율적) ⚡

• 작은 문제부터 차례로 계산하여 DP 테이블을 채움
• 모든 DP 값을 계산하고 최종 정답을 도출
• ✅ 보통 더 빠름 (오버헤드가 없음!)

---

🔍 정리

방법 설명 장점 단점

🔼 Top-Down	재귀 기반 DP	코드가 직관적	함수 호출이 많아 속도 저하 가능
🔽 Bottom-Up	반복문 기반 DP	속도가 빠름	DP 테이블을 미리 만들어야 함

📢 DP를 이해하는 가장 쉬운 방법:
👉 완전탐색처럼 풀고, 중복 계산을 방지하는 것! 💡

#include <iostream>
#include<vector>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	string str1, str2;
	cin >> str1;
	cin >> str2;

	int strSize = str1.size();
	int strSize2 = str2.size();

	//DP 초기화
	vector<vector<int>> DP(strSize + 1, vector<int>(strSize2 + 1, 0));

	for (int i = 1; i <= strSize; i++)
	{
		for (int j = 1; j <= strSize2; j++)
		{
			if (str1[i - 1] == str2[j - 1])
			{
				DP[i][j] = DP[i - 1][j - 1] + 1;

			}
			else
			{
				DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
			}
		}
	}

	cout << DP[strSize][strSize2] << "\n";

	return 0;
	
}