푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 기본적인 LCS알고리즘 구현 문제입니다. 이차원 배열을 만든 후 두 문자열의 길이만큼 for문을 돌려주시면서 A[i-1] == B[j-1]이라면 map[i][j] = map[i-1][j-1] + 1; A[i-1] != B[j-1]이라면 map[i][j] = max(map[i - 1][j], map[i][j..

Algorithm 공부 #24 - dp 동적 계획법(Dynamic Programming) ● 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결하여 최동적으로 복잡한 문제의 답을 구함 ● 동적 계획법의 원리와 구현 방식 1. 큰 문제를 작은 문제로 나누기 2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값이 항상 같아야 함 3. 모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하여 추후 재사용, 이 방식을 메모이제이션이라 함 4. 동적 계획법은 톱 - 다운 방식과 바텀 - 업 방식으로 구현 가능 ● 톱-다운 구현 방식 : 위에서부터 문제를 파악해 내려오는 방식 / 주로 재귀 함수 형태로 구현 코드의 가독성이 좋고 이해하기가 편함 ● 바텀-업 구현 방식 : 가장 작은..