[ SWEA 1264 ] 이미지 유사도 검사 (C++)

SWExpertAcademy의 이미지 유사도 검사 (1266 / D6) 문제이다.

[ 문제풀이 ]

1) 문제가 조금 길어보이지만 이 문제를 한마디로 요약하자면 LCS를 구하여라 ! 이다.

   LCS는 '최장 공통 부분 수열' 을 의미한다.

   즉, 2개의 문자열을 비교하면서 부분 수열 중에서 공통된 가장 긴 부분수열을 골라내면 되는 문제이다.

   이 문제에 대해서 예전에 포스팅 해놓은 글이 있다.

   [ 백준(9251) - LCS 풀이 ]

   하지만, 위의 글이 너무 간략하게만 설명이 되어 있는 것 같아서 이번 글에서 보다 구체적으로 설명해보려 한다.

   LCS는 기본적으로 2개의 문자열을 비교하는 과정이 필요하다. 지금부터 이 2개의 문자열을 문자열A, B로 표현해보자.

   LCS는 Dynamic Programming 방법을 이용해서 일반적으로 풀이를 하게 된다.

   이를 위해서 점화식에 따른 결과값을 저장해주기 위한 int형 2차원 배열을 하나 사용하게 된다.

   ( 지금 부터 이 배열의 이름을 편하게 LCS[][] 라고 표현하겠다. )

   LCS[a][b] = c 의 의미는 "문자열 A를 a번째까지, 문자열 B를 b번째까지 비교했을 때, 최장 공통 부분 수열의

   길이는 c입니다." 를 의미한다.

   그럼 문자열 A = "abcde", 문자열 B = "abdef" 라는 예시로 구체적으로 알아보자.

   LCS[1][1]의 값은 얼마일까 ?? 이 말을 풀어쓰면

   "abcde와 abdef를 비교하는데, abcde에서 1번째 문자인 a, abdef에서 1번째 문자인 a까지 비교했을 때, 최장 공통 부분

   수열의 길이는 얼마인가요?" 라고 묻는 것이다.

   당연히 a와 a가 같기 때문에 1일 것이다. 그렇다면, LCS[1][2] 는 ?? 또한 1일 것이다.

   이러한 값들을 구하는 과정을 구체적으로 알아보자.

   LCS를 구하기 위해서는 딱 한가지만 생각해주면 된다. "비교하는 두 문자가 같은지 아닌지 !"

   같은 경우에는 "이전의 최장 공통 부분 수열의 길이 + 1" 을 해주면 된다.

   다른 경우에는 "A문자열에 해당하는 문자를 선택했을 때의 길이 vs B문자열에 해당하는 문자를 선택했을 때의 길이" 중

   더 큰 길이를 선택해주면 된다.

   무슨말인지 "abcde", "abdef" 로 천천히 알아보자.

   첫번째 문자열 'a'와 'a'를 비교하면 같으므로 LCS[1][1] = 1

   위와 같은 계산으로 LCS[1] [1][2][3][4][5] = 1 이 될 것이다. 왜냐하면, 첫 번재 문자열은 첫 번째 까지만 비교를

   하기 때문에 !

   LCS[2][2] = ?? "ab"와 "ab"이므로 LCS[2][2] = 2 가 될 것이다. 마찬가지로 LCS[2] [3][4][5] 모두 2가 될 것이다.

   LCS[3][1] = 1 / LCS[3][2] = 2 까지는 쉽게 계산할 수 있을 것이다.

   LCS[3][3]의 경우를 보자. 문자가 'c'와 'd'로 서로 다른 경우이다.

   서로 다른 경우에는 ? "A를 선택했을때의 길이 vs B를 선택했을때의 길이" 라고 했다.

   A를 선택했을 때의 길이 라는 것은 무엇을 의미할까 ?? 바로 LCS[3][2]의 값을 의미하는 것이다.

   B를 선택했을 때의 길이는 ?? LCS[2][3]의 값을 의미한다. 

   LCS의 의미를 잘 생각한다면 LCS[3][2]와 LCS[2][3] 인 이유를 알 수 있을 것이다.

   즉, 이 2개의 값 중 더 큰 값을 선택해 주면 된다. 왜냐하면, 두 문자가 서로 다르기 때문에 LCS의 값이 증가하거나

   할 수는 없다. 단지, 기존까지 구한 값들 중에서 가장 큰 값을 가져온다고 생각하면 된다.

   그렇다면, LCS[4][2], [4][3], [4][4]의 값을 계산해보자.

   LCS[4][2] = "abcd"와 ,"ab"를 비교하므로 = 2

   LCS[4][3] = "abcd"와 "abd"를 비교하므로 3이 될것이다.

   LCS[4][3] 같은 경우 'd'와 'd'로 같기 때문에 기존의 최장길이인 2에서 + 1을 해줘서 3이 되는 것이다.

   LCS[4][4]의 경우는 ?? ''d'와 'e'의 비교이다. 서로 다르기 떄문에 기존의 최장길이인 3이 된다.

   마지막 5로 넘어가보자. LCS[5][1] = "abcde" 와 "a"를 비교하므로 1

   LCS[5][2] = "abcde"와 "ab"를 비교하므로 2

   LCS[5][3] = "abcde"와 "abd"를 비교하므로 3

   LCS[5][4] = "abcde"와 "Abde"를 비교하므로 4

   LCS[5][5] = 마지막 문자가 서로 다르므로 기존의 최장길이인 4가 된다.

   따라서, "abcde"와 "abdef"의 LCS값은 4가 된다.

  

   마지막으로 정리하자면, 문자열을 비교하면서 해당 문자가 같은지 아닌지만 구분해주면서 계산을 진행해가면 된다 !

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
 
#define MAX 510
#define endl "\n"
using namespace std;
 
int Len;
int LCS[MAX][MAX];
double Answer;
string A, B;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    memset(LCS, 0, sizeof(LCS));
}
 
void Input()
{
    cin >> Len;
    cin >> A >> B;
}
 
void Solution()
{
    for (int i = 1; i <= Len; i++)
    {
        for (int j = 1; j <= Len; j++)
        {
            if (A[i - 1] == B[j - 1]) LCS[i][j] = LCS[i - 1][j - 1] + 1;
            else LCS[i][j] = Bigger(LCS[i - 1][j], LCS[i][j - 1]);
        }
    }
    
    Answer = (double)LCS[Len][Len] / (double)Len * 100.0;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fixed;
    cout.precision(2);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}