C#/백준 알고리즘
2022.02.09 [백준] C# LCS
ian's coding
2022. 2. 9. 16:25
728x90
반응형
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
풀이
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.
velog.io
위의 블로그에서 LCS에 대해 공부 후 코드 작성했습니다.
s1, s2의 최장 공통 부분 수열의 길이를 저장할 arr 2차원배열을 각 문자열길이 +1로 설정해주고 i 또는 j 가 0이면 마진값 0 을 설정 해준다. 그리고 s1[i]의 문자와 s2[j]가 같으면 대각선 뒤의 값에 +1 해줌. 아니면 왼쪽이나 위의 값 중 큰값을 대입했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
using System;
using System.Text;
using System.IO;
using System.Collections.Generic;
class Program
{
static string s1;
static string s2;
static int[,] arr;
static void Cal()
{
for(int i = 0; i <= s1.Length; i++)
{
for(int j = 0; j <= s2.Length; j++)
{
if (i == 0 || j == 0)
{
arr[i, j] = 0;
}
else if (s1[i-1] == s2[j-1])
{
arr[i, j] = arr[i - 1, j - 1]+1;
}
else
{
arr[i, j] = Math.Max(arr[i - 1, j], arr[i, j - 1]);
}
}
}
}
static void Main()
{
StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
StringBuilder sb = new StringBuilder();
s1 = sr.ReadLine();
s2 = sr.ReadLine();
arr = new int[s1.Length+1, s2.Length+1];
Cal();
sw.WriteLine(arr[s1.Length,s2.Length]);
sr.Close();
sw.Close();
}
}
|
cs |
728x90
반응형