[알고리즘] LCS (최장 공통 부분 수열)
목차 LCS란? LCS는 Longest Common Subsequence의 약자이다. 말 그대로 가장 긴 공통된 부분 수열이다. LCS는 보통 주어진 두 수열에서 각각의 부분 수열들 중, 서로 같은 부분 수열 중에서 가장 긴 부분 수열을 뜻한다. LCS는 DP(다이나믹 프로그래밍)의 대표 유형 중 하나고 백준에서는 최소 난이도가 골드5 정도 된다. 따라서 LCS를 알면 DP 골드 문제들을 조금씩 풀 수 있게 된다. 예시를 하나 보겠다. s1 = ACAYKP, 그리고 s2 = CAPACK라고 하겠다. 문제 예시로 보자면 ACAYKP의 부분 수열을 표현하면 다음과 같다. ACAYKP : {A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, ⋯ , {A, C, A, Y, K, P} CAPCAK의..
2022. 1. 30.
[백준] 15990번 : 1, 2, 3 더하기 5 – JAVA [자바]
https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 방법 이 문제는 다이나믹 프로그래밍 (DP) 문제이니 DP 이론은 밑에 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming [알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 목차 다이나믹 프로그래밍이란? 다이나믹 프로그래밍 (Dynamic Programming) 또는 동적 계획법은 큰 문제를 작은 문제로 쪼개서..
2022. 1. 26.
