코딩테스트/알고리즘6 [알고리즘] LCS (Longest Common Subsequence) 문제 LCS 문제는 두 문자열이 주어졌을 때 두 문자열이 공통으로 가지는 문자의 가장 긴 길이를 구하는 문제입니다. 이 때, 공통으로 가지는 문자의 순서가 바뀌어선 안됩니다. 예시는 다음과 같습니다. 해당 문제는 동적계획법을 이용해 O(N^2)의 시간 복잡도로 해결할 수 있습니다. 동적계획 방법입니다. 1. 각 문자열 별로 dp 테이블을 만들기 위해 2차원 배열을 선언합니다. 2. dp 테이블의 인덱스 0은 문자열이 0개일 때이므로 모두 0으로 초기화합니다. 3. 이후 테이블을 초기화 할 때 해당 자리의 문자열(Xi, Yj)을 비교합니다. 3-1. 문자열이 다르면 i 또는 j를 줄인 것 중 큰 값으로 테이블을 초기화합니다. 3-2. 문자열이 같으면 i와 j 모두 줄인 값에서 +1 하여 초기화합니다. 4. LC.. 2021. 2. 15. [알고리즘] 동적 계획법 (Dynamic Programming) 코딩테스트 대비 정리 알고리즘 문제를 풀던 중 동적계획법 풀이 방법 정리가 필요함을 느껴 동빈나님의 이코테 강의를 보고 제 생각을 더해 정리해 보았습니다. 풀이 언어는 파이썬을 사용했습니다. 목차 동적 계획법 개념 대표 풀이 예시 : 피보나치 수열 문제 리뷰 동적 계획법(DP) 개념 동적 계획법 메모리를 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산한 것을 메모리에 저장하여 중복 계산을 막는다. 최소/최대 문제 등에서 자주 사용된다. 점화식을 구해야 하며 이 과정이 어렵지만 코드는 대체적으로 간단한 편이다. 동적 계획법의 조건 1. 최적 부분 구조 : 큰 문제를 작은 문제를 나눌 수 있어야 함 2. 중복되는 부분 문제 : 중복되는 문제를 테이블에 저장하여 다시 계산하지 않음 동적 계획법의 두 가지 방법 1.. 2021. 2. 2. 이전 1 2 다음
