[Python]알고리즘/백준
[다이나믹 프로그래밍] ★★ 9251번 - LCS
[백준] 9251번 - LCS (한줄평) 접근 방식은 맞았지만 점화식을 세우지 못해 어려웠던 문제.. 1차원 리스트로 접근하는 방식은 아예 생각하지도 못했고 이해하기도 어렵다.. 무조건 복습해야할듯하다 두 문자열의 LCS 길이를 구하는 문제다. 이 문제는 각 문자열의 길이를 하나씩 늘려가며 두 문자열의 LCS를 반복적으로 구하는 것이 핵심이다!! dp 테이블을 2차원 혹은 1차원 리스트로 풀이하는 방식 2가지가 있는데 1차원 리스트를 이용하여 구현항 방식이 조금 더 효율적인 방식이다. 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴것을 찾는 문제 (풀이1) 2차원 리스트 이용 풀이 시간: 50분 이내 1) 문제 해결 아이디어 dp 테이블을 2차원 리스트로 생성하여 푼 방식이다. 1. ..
