- 문제 : https://www.acmicpc.net/problem/9251
1. 알고리즘
문자열 두개를 s1, s2에 입력 받는다.
dp 테이블을 s1 + 1, s2 + 1 크기 만큼 생성한다. 초기값은 모두 0으로 세팅한다
이중 for문을 돌려서 1부터 s1의 크기하고 같을 때까지 돌려서 dp 테이블을 채운다.
for문안에는 2개의 조건이 존재한다.
1) 값이 매칭되는 경우, 대각선에 있는 값에서 +1을 한다.
2) 값이 매칭되징 않는 경우, 왼쪽이나 위쪽에 있는 값중에서 제일 큰 값을 가져와서 세팅한다
출력은 DP[s1.length][s2.length] 만큼 하면 된다.
2. 시간 복잡도
시간복잡도는 이중 for문으로 s1길이 * s2길이이다.
s1의 길이를 N, s2의 길이를 M이라고 표현한다면, 시간 복잡도는 O(NM)이 된다.
따라서, s1이 가질 수 있는 최대 길이는 10^3임으로 10^3 * 10^3으로 총 10^6이 필요하다.
10^8의 0.1초는 10^7임으로 해당 풀이과정으로 시간내에 푸는 것이 가능하다.
3. 결과
https://github.com/moonlight-duck/study-algorithms/pull/28
[민주] LCS 문제풀이 by min-99 · Pull Request #28 · moonlight-duck/study-algorithms
📌 문제 정보 문제 링크 : https://www.acmicpc.net/problem/9251 카테고리 (예: 구현, 탐색, DP) : LCS(DP) ✏️ 풀이 방법 결과 (성공/실패) : 성공 풀이 시간 : study 2h, cooding 5m 풀이 방법 : https://min-99.tistory.com/41
github.com
'알고리즘' 카테고리의 다른 글
| 시간/메모리 초과 개선 + 백준 환경이 잘못되었자나(개선후기, 구간 합 구하기, 백준 2042번 세그먼트 트리) (1) | 2025.11.19 |
|---|---|
| 공간복잡도 (0) | 2025.11.18 |
| 최장 공통 부분 수열 (Longest Common Subsequence, LCS) (0) | 2025.11.17 |
| 2×n 타일링 (DP) (0) | 2025.11.17 |
| 피보나치 함수 (DP, 백준 1003번) (0) | 2025.11.17 |