[20210707] DP를 이용한 회문(Palindrome)
DP를 활용해서 회문을 풀어보자.
회문(Palindrome)이란?
회문은 거꾸로 읽어도 똑같이 읽히는 단어를 회문이라고 한다.
aba는 회문이다, 거꾸로 읽어도 aba이기 때문이다. abab는 회문이 아니다, 거꾸로 읽으면 baba ≠ abab 이기 때문이다.
처음 접근
DP를 활용해야 한다는 생각에 DP는 기억하여 사용하기와 유사하기 때문에, 주어진 문자열에서 회문인 범위를 모두 알아낸 뒤 Set에 저장하여 사용하였다. 하지만, 어김없이 시간초과를 받았다…
모든 경우의 수를 파악하였기 때문에, 문자열의 길이를 N이라고 한다면, 문자열의 각 요소(문자, i)를 모두 탐색하므로 N X 각 요소(문자)에서 문자열의 길이까지 매번 탐색(1..N-i)하므로 N X 정해진 길이의 문자열이 회문인지 탐색하므로 N
결론적으로 O(N^3^) 시간 복잡도가 된다.
DP를 이용
회문에서 양쪽 끝을 제거한 문자열도 회문이다. x + (회문) + x => 회문
위의 점화식을 이용해서 회문을 길이가 작은 문자열부터 회문인지 파악해 간다. DP배열을 2차원 배열로 선언하여 사용한다. DP[i][j] = 문자열 i부터 j까지의 문자열이 회문인가를 의미한다.
예로, abcba라는 문자열이 있다. DP 배열의 값에서 0은 회문이 아님을 뜻하고, 1은 회문임을 뜻한다고 하자.
DP[0][0] = 1이다. 왜냐하면 a는 회문이기 때문이다.
DP[2][2] = 1이다. 왜냐하면 c도 회문이기 떄문이다.
이처럼 문자열의 길이가 1인 문자열은 모두 회문이다. DP[i][i] = 1
1번째 부터 3번째까지의 문자열인 bcb를 점화식으로 나타내면, DP[1][3] = b + DP[2][2] + b 이며, 회문의 양쪽에 같은 문자가 존재하므로 이 또한 회문이다. 그렇기 때문에 bcb는 회문이다.
이처럼 짧은 문자열이 회문인지 아닌지를 알고 있으므로 더 긴 문자열의 회문 여부를 요소 2개만 비교해서 같으면 회문인지 알 수 있게 된다.
그래서 처음 접근했던 정해진 길이의 문자열이 회문인지 탐색하는 과정이 N에서 2로 줄어들었기 때문에, DP를 이용하면 O(N^2^)의 시간 복잡도를 갖게 된다.