[SWEA 코딩] S/W 문제해결 응용 이미지 유사도 검사 - PYTHON #1264

소스 코드

T = int(input())

for tc in range(1,1+T):
    # 코드열의 길이
    n = int(input())

    # x,y
    x = list(input())
    y = list(input())

    # LCS를 구현하기 위한 2차원 배열
    board = [[0 for one in range(n+1)] for two in range(n+1)]

    res = 0
    for q in range(n):
        for w in range(n):
            
            # 값이 같을 때, 현재 위치(x,y)에서 -1만큼 해준 곳(x-1,y-1)의 값 +1
            if x[q] == y[w]:
                board[q+1][w+1] = board[q][w] + 1
                if board[q+1][w+1] > res:
                    res = board[q+1][w+1]

            # 값이 다를 때, 현재 위치 기준 왼쪽, 위의 값 중 큰 값을 현재 위치의 값으로
            else:
                board[q+1][w+1] = max(board[q+1][w],board[q][w+1])

    print('#{}'.format(tc),end=" ")
    print(format(res/n*100,".2f"))

 

---

해결 방법

1. LCS 알고리즘을 사용

(LCS 알고리즘이란 DP와 유사한 형태로 이루어짐)

 

초기형태

	-	B	D	C	D	F	E
-	0	0	0	0	0	0	0
C	0
D	0
B	0
F	0
E	0
A	0

 

위와 같은 형태에서, C D B F E A 순서로 BDCDFE를 확인할 예정

1) C의 경우

	-	B	D	C	D	F	E
-	0	0	0	0	0	0	0
C	0	0	0	1
D	0
B	0
F	0
E	0
A	0

B,D는 C와 같은 값이 아니므로 위쪽(0)과 왼쪽 값(0) 중 큰 값을 선택

C는 C와 같은 값이므로, 왼쪽 위[0,2]의 값 +1을 해준다

 

WHY?

1) 같은 값이 아닌 경우 위쪽과 왼쪽 값 중 큰 값을 선택하는 이유

(이 전까지의 최대 공통 값이 연속되기 때문, 즉 이전까지의 최대 값을 누적시켜가면서 진행하는 것)

2) 같은 값을 찾았을 때, 왼쪽 위의 값에서 +1을 해주는 이유

(현재 위치의 직전 상황까지의 최대 값 + 1 해주는 것과 같음)

 

>> 이해가 가지 않으신다면 반드시 LCS 알고리즘을 검색해서 해결 방법을 찾아보시길 바랍니다.

 

완성된 표

	-	B	D	C	D	F	E
-	0	0	0	0	0	0	0
C	0	0	0	1	1	1	1
D	0	0	1	1	2	2	2
B	0	1	1	1	2	2	2
F	0	1	1	1	2	3	3
E	0	1	1	1	2	3	4
A	0	1	1	1	2	3	4

 

---

느낀 점

문제를 해결하면서 LCS에 대해 완전히 이해하지 못한 상태이기 때문에 내가 푼 방법이나 이해한 내용을 글로 풀어쓰는 것이 부족하다

 

그러니 혹시 이 문제 해결방법을 보고 이해가 가지 않으신다면 반드시 LCS 알고리즘을 검색해서 찾아보시길 바란다.

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.