# LCS
[파이썬] 백준 9251번: LCS(Longest Common Subsequence, 최장 공통 부분 수열)
⏰ 시간복잡도: O(M * N) / 공간복잡도: O(M * N) ✏️ 답안 👀 접근방법 1) DP 배열 초기화 큰 문제를 작은 문제로 쪼개어 문제를 해결해나가는 DP의 bottom-up 방식을 활용하여 문제를 풀었다. 먼저 LCS 길이를 저장할 수 있도록(첫 번째 문자열의 길이 + 1) * (두 번째 문자열의 길이 + 1)의 사이즈로 2차원 DP 배열을 만들었다. 연산을 쉽게 하기 위해 문자열의 길이에 1을 더한 사이즈로 만들었고, 모두 0으로 초기화했다. dpi는 첫 번째 문자열의 i번째 ~ 마지막 부분과 두 번째 문자열의 j번째 ~ 마지막 부분의 LCS 길이를 의미한다. 아래 그림을 예로 들어 살펴보면 주황색으로 표시한 dp_grid3에는 문자열 "YKP"와 "PCAK"의 LCS 길이가 들어간다. 
백준 9252 LCS 2 Kotlin
백준 9252번 https://www.acmicpc.net/problem/9252 문제 생각하기 LCS의 기초를 다질 수 있는 문제이다. TopDown(재귀) , BottomUp(반복문) 2가지 방식 모두로 구현했다. 의문점 : 재귀로 구현한 코드는 메모리초과가 발생하지 않는데, 똑같은 코드를 반복문으로 고칠경우 메모리 초과가 발생함 동작
백준 5582 공통 부분 문자열 Kotlin
백준 5582번 https://www.acmicpc.net/problem/5582 문제 생각하기 메모이제이션과 LCS를 응용해서 문제를 풀었다. LCS는 원래 sequence를 찾는데 사용하지만 substring을 찾는데도 메모이제이션과 같이 활용해서 풀 수 있었다. 동작 를 통해서 문자열 하나씩을 비교해보면서 작은 문제 부터 해결해나간
LCS (Longest Common Subsequence)
LCS (Longest Common Subsequence) LCS(Longest Common Subsequence) 알고리즘은 두 문자열(또는 두 시퀀스)에서 가장 긴 공통 서브시퀀스를 찾는 것이 목적이다. 공통 서브스트링을 찾는 것이 목적이 아니다. subsequence는 substring을 커버하는 더 넓은 범주이다. 서브스트링 (Substring) 과 서브시퀀스 (Subsequence) 서브스트링 (Substring): 문자열에서 연속된 일련의 문자들로 이루어져 있어야 합니다. 예를 들어, "apple"이라는 문자열에서 "ppl"은 서브스트링입니다. 서브시퀀스 (Subsequence): 문자열에서 연속되지 않을 수도 있는 일련의 문자들로 이루어져 있습니다. 예를 들어, "apple"에서 "apl"은 서브시퀀스입니다. 이는 원래 문자열에서 'a', 'p', 'l'이라는 문자들이 등장하면서 순서가 유지되기 때문입니다.
백준 9251 LCS Kotlin
백준 9251번 https://www.acmicpc.net/problem/9251 문제 생각하기 LCS 기초 문제이다. 메모이제이션 DP를 활용해서 해결했다. 동작 결과 
BOJ 9251 LCS Python
문제 링크:https://www.acmicpc.net/problem/9251 접근 LCS알고리즘을 검색해서 풀었다 코드1 우선 비교할 문자열을 입력받아 len(str1)+1, len(str2)+1의 길이만큼의 2차원 배열인 lcs를 선언해 준다 그리고 문자열을 하나씩 비교해가며 lcs 배열에 값을 하나씩 저장해간다 lcsx에 대해 str1[x-1]과 str2[y-2]의 문자가 서로 같다면 2차원 배열의 기준으로 왼쪽 대각선 위의 값에 +1을 하여 저장해 준다. (lcs 배열의 길이가 각각의 문자열의 길이 +1을 해준 이유가 문자열의 길이에 맞춰 선언하면 0번째 인덱스에서 에러가 나기 때문) 만약에 서로 같지 않은 경우는 2차원 배열 기준으로 위나 왼쪽 중 큰 값을 저장한다
알고리즘&자료구조 5 - LCS(Longest Common Subsequence)
9251번 LCS dp문제는 항상 어렵다. 이전의 값을 재사용해야하는데, 이 문제는 어떤방식으로 재사용 할지 도저히 생각이 안났다. 답지를 봤다. 쉬운데 어렵다. 그래서 유튜브쌤을 활용! > https://www.youtube.com/watch?v=P-mMvhfJhu8 이그림이 핵심임. 여기서 자세하게 설명해주신다. 원론은 이러하다. str1의 i번째 문자열 = str2의 j번째 문자열 이면, str1의 i-1번째 문자열과 j-1번째 문자열까지 최장부분수열의 값 + 1 => Xi = Yj 면 Xi-1 = Yj-1 이건 알겠다
LCS(Longest Common Subsequence)
다이나믹프로그래밍 문제를 풀어나가면서 LCS를 마주했다 LCS는 https://youtu.be/EAXDUxVYquY 신찬수 교수님께서 잘 설명해주셔서 해당 강의를 듣고 개념을 정리했고, 개념을 정리한 바탕으로 문제를 풀었다. 내가 마주한 문제는 백준의 9251번 문제이고 링크는 아래와 같다. https://www.acmicpc.net/problem/9251 LCS 란? 두 문자열이 주어졌을 때, 가장 긴 공통 부문자열을 찾는 것이다. 여기서 부문자열은 문자열에서 몇개를 지우고 남은 문자열을 의미한다. 이렇게 두 문자열이 존재할때, 공통 부문자열은 ABA, BCBA 이다. ABA 는 X 문자열에서 2,3,4,6 번째 인덱스를 지우면 ABA 가 남고, Y 문자열에서 0,1,2 번째 인덱스를 지우면 ABA 가 남는다. 그래서 ABA 는 공통 부문자열이다. BCBA는 X 문자열에서 0,4,6 번째 인덱스를 지우면 BCBA 가 남고, Y 문자열에서 1,3 번째 인덱
LCS
LCS 개요 Longest Common Subsequence. 최장 공통 부분수열 문자열 A = “ABCDE” , B = “KBCE” 라고 하자 → 최장 공통 부분 수열 : BCE 점화식 (LCS의 길이) 문자열 A와 문자열 B를 한글자씩 비교한다. 1. 두 문자가 다르다면, dpi-1와 dpi 중 큰값을 기록한다. 두 문자가 같다면, dpi-1의 값에 1을 더한값을 기록한다. 반복 점화식 ( LCS 문자열 ) LCS 배열의 가장 마지막 값에서 시작. dpi-1와 dpi 중 현재 값과 같은 값을 찾는다. 같은 값이 있다면, 해당 값으로 이동 같은 값이 없다면, result에 해당 문자르 추가하고 dpi-1로 이동 반복, dpi==0으로 이동하면 종료, result 문자의 reverse가 L
[DP][JAVA] LCS 알고리즘
LCS 알고리즘이란? > ❗ LCS는 Longest Common Subsequence의 줄임말로, 공통 부분 문자열 중 가장 길이가 긴 문자열을 말합니다. 이 때, Substring과 Subsequence와의 차이점을 보고 넘어가겠습니다. SubString: 전체 문자열에서 연속된 부분 문자열 ex) ABCDEFG 에서 Substring은 ABC, DEFG, ABCDEF, ... 등이 있다. Subsequence: 전체 문자열에서 꼭 연속된 문자열인 것은 아닌 부분 문자열 ex) ABCDEFGH 에서 Subsequence는 ABD, AEFGH, AFI, ... 등이 있다. 단, 앞에서부터가 아니라 순서가 뒤바뀐 IHE, BIDEHF 와 같은 문자열은 부분 문자열이 될 수 없다. 
[알고리즘 문제풀이] LCS
문제 제목 : LCS 문제 난이도 : 하 문제 유형 : 동적 프로그래밍, 문자열, LCS https://www.acmicpc.net/problem/9251 시간 제한 : 0.1초 메모리 제한 : 256MB 문제풀이 아이디어
백준 9521번
1. 문제 9521번 2. 풀이 3. Reference https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5%EA%B3%B5%ED%86%B5%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4
최장 공통 부분 수열 LCS
참고 링크 ✅ 최장 공통 부분 수열 LCS LCS(Longest Common Subsequence)는 주로 최장 공통 부분수열을 나타내지만 최장 공통 문자열을 말하기도 한다. 최장 공통 문자열은 반드시 부분 문자열이 연결된 형태여야 한다. banana, vbankn 최장 공통 부분 수열은 떨어져 있어도 상관없다. bdanvv, vbkkanm 최장 공통 부분 수열는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다. 1-1. LCS 길이 찾는 방법(DP) 이중 포문을 사용하여 각 원소들을 하나씩 직접 비교해주면서 dp값을 갱신해주면 된다. dp는 2차원 배열로 수열 n1과 n2의 LCS길이를 저장해준다. dp수열n1의 i번째 = 수열 n1과 수열 n2의 LCS의 길이
백준|9251번|LCS
문제 설명 두 문자열을 입력받고 두 문자열의 최장 공통 부분 수열(LCS)을 출력하는 문제입니다. 작동 순서 두 문자열 A, B를 입력받습니다. 두 문자열의 위치에서 LCS의 길이를 저장하는 2차원 배열 dp를 생성합니다. A의 문자와 B의 문자를 하나씩 비교해가며 A의 문자와 B의 문자가 같은 경우 이전 LCS 길이에서 +1을 해줍니다. A의 문자와 B의 문자의 길이가 다른 경우 이전 LCS 길이 중 가장 긴 LCS 값을 저장합니다. A 문자열과 B 문자열을 모두 비교한 뒤 가장 긴 LCS의 길이를 출력합니다. 소스코드
백준 9252번 LCS 2
백준 9252번 링크 LCS Longest common subsequence를 찾는 전형적인 DP 문제다. 점화식은 다음과 같다. $$ DPi = \begin{cases} DPi - 1 + 1 &\text{if } str[i] == str[j] \\ max(DPi - 1, DPi) &\text{o.w. }\end{cases} $$ 해당 문제에서는 결과값으로 LCS의 길이 뿐만 아니라 문자열도 요구한다. 두가지 방법이 있다. 2차원 배열을 만들어 해당 칸으로 온 방향을 기록해둔다. 단순하게 역추적한다. 2번 방법을 적용하여 풀었다. 코드
[백준] 9252번 : LCS2
🔗 문제 링크 https://www.acmicpc.net/problem/9252 ✍️ 문제 풀이 해당 문제는 다이나믹 프로그래밍 문제로, 1 ~ n 인덱스까지의 A 문자열이 있을 때, 1 ~ n 인덱스까지의 B 문자열과의 최장 공통 수열을 2차원 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다. 이 문제는 기존 LCS 문제와 같으나, 개수 뿐만 아니라 해당 수열을 직접 출력까지 해야한다. 따라서 LCS의 길이를 구하는 부분은 생략하고, 수열을 출력하는 부분만 알아보겠다. (9251번 : LCS 링크) 1) A 문자
[알고리즘] LCS 알고리즘
LCS 알고리즘이란 LCS (Longest Common Subsequence) 알고리즘은 두 문자열 내에 존재하는 최장 공통 부분 수열을 찾는 알고리즘을 말한다. 간혹 '최장 공통 문자열' (Longest Common Substring)을 뜻하기도 한다. 두 가지는 확실히 다르니 잘 구분해야 한다. 최장 공통 부분 수열 가령 ABCDGEF 라는 문자열과 BGAGEFE 라는 문자열이 있다고 했을 때, 공통 부분 수열은 부분수열이기 때문에 각 문자들을 뛰어넘을 수 있고, 두 문자열에 공통으로 존재하면서 가장 긴 부분 수열인 BGEF 를 찾는 것이다. 공통 부분 수열은 A, B, AG 등 여러 개가 있을 수 있으며, 최장 공통 부분 수열 역시 여러 개가 있을 수
[알고리즘] LCS 알고리즘인데 DP를 이용한
LCS 알고리즘(Longest Common Subsequence) LCS == 최장 공통 부분 수열로, 두 문자열을 비교했을 때 가장 긴 공통 부분 문자열 LCS는 최장 공통 문자열(Longest Common String)을 의미하기도 하는데, 둘의 차이점은 공통 부분이 연속하는지 아닌지 여부다. 두 문자열 ABCD, ABFC 가 있다고 할 때, 최장 공통 문자열 : AB 최장 공통 부분 수열 : ABC _ ✍️ DP를 이용한 LCS 풀이 방법 : DPi에는 i 인덱스까지의 문자열 1과 j인덱스까지의 문자열 2 사이의 LCS의 길이가 저장된다. 문자열 BCFD와 ABCD를 비교한다고 할 때 각 문자열의 세번째 인덱스까지의 LCS는 아래 두 가지 중 하나로 결정된다. 세 번째 글자가 같다면 : BC와 AB 사이의 LCS + 1