[알고리즘] 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.
[백준] 16948번 : 데스 나이트 – JAVA [자바]
https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 문제 풀이 방법 이 문제는 전형적인 그래프 문제이다. 조금 더 구체적인 그래프 이론을 알고 싶으면 밑에 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/자료구조-그래프Graph [자료구조] 그래프(Graph) 목차 그래프란? 그래프는 정점과 간선으로 이루어진 자료구조임. →..
2022. 1. 29.
[백준] 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.
