[Algorithm] 최장 증가 부분 순열, 최장 공통 부분 수열
* Python을 기준으로 합니다 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) & 최장 공통 부분 수열 (Longest Common Subsequence, LCS) - 개념 부분 수열 : 주어진 수열 중 일부를 뽑아 새로운 수열을 만들 때, 기존의 상대적인 순서를 유지하는 수열 최장 증가 부분 수열 (LIS) : 부분 수열의 원소가 오름차순을 유지하면서 가장 길이가 긴 수열 일반적으로 다이나믹 프로그래밍으로 해결가능함 LIS 길이 계산에 다이나믹 프로그래밍 적용하기 다이나믹 프로그래밍을 활용하기 위해서는 전체 문제가 중복되는 최적 부분 구조로써 분해 가능해야함 - 최적 부분 구조 : 전체 수열에 대한 LIS 길이는 각 원소로 끝나는 LIS 길이 중 최대값을 구..
[Algorithm] 다이나믹 프로그래밍
* Python을 기준으로 합니다 다이나믹 프로그래밍 (Dynamic Programming) - 개념 다이나믹 프로그래밍 (동적 계획법) : 전체 문제를 각각의 부분 문제로 나눈 다음 하나의 결과로 합쳐서 해결하는 방법 즉, 전체 문제를 부분 문제로 나누어 해결할 수 있어야 하고 동시에 중복되는 부분 문제가 존재하는 경우 사용 다이나믹 프로그래밍의 구현 메모이제이션 (Memoization) : 하향식 (Top-down) 방식 - 주어진 문제를 작은 부분 문제로 나누어 가면서 전체 문제를 해결하는 방식 - 재귀를 기반으로 이전 값들이 모두 계산되어 있다는 가정 하에 나머지 계산을 수행함 타뷸레이션 (Tabulation) : 상향식 (Bottom-up) 방식 - 작은 부분 문제부터 해결한 다음, 해당 과정을..