[알고리즘] 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.
