백준 5582번
https://www.acmicpc.net/problem/5582

문제

---

생각하기

---

• 메모이제이션과 LCS를 응용해서 문제를 풀었다.

  • LCS는 원래 sequence를 찾는데 사용하지만 substring을 찾는데도 메모이제이션과 같이 활용해서 풀 수 있었다.

동작

    val size1 = s1.length
    val size2 = s2.length
    for (i in 1 .. size1) {
        for (j in 1 .. size2) {
            ans = ans.coerceAtLeast(LCS(i, j))
        }
    }

를 통해서 문자열 하나씩을 비교해보면서 작은 문제 부터 해결해나간다.

여기서 궁금해서

해당 반복문을 반대로 돌려봤는데

    for (i in size1 downTo 1) {
        for (j in size2 downTo 1) {
            ans = ans.coerceAtLeast(LCS(i, j))
        }
    }

아무래도 작은 문제부터 해결하는게 아닌 큰 문제부터 해결하려는 방식으로 메모이제이션을 활용해서 그런지 위의 1부터 시작하는 반복문과 비교해서 600ms정도의 성능차이가 극심하게 나타났다.
메모이제이션은 작은 문제부터 해결하는데 사용하자...

쉬운 예시로

ABABC
BABCAC

를 들어보자면 i는 A부터 시작해서 j는 BABCAC를 전체 탐색하면서 먼저 하나씩 비교하며
memo 배열의 1라인을 완성시킨다.

i가 2일때 부터 이제 memo를 활용하기 시작하는데, LCS(2, 3)이 실행되면

LCS(1, 2)로 재귀가 실행된다. 여기서 memo[1][2]는 이미 -1이 아닌 값인 1이 저장되어 있으므로 return하여 돌아갈 수 있게 된다.

그리고 LCS(2, 3)으로 다시 돌아와서 memo[2][3]을 2로 저장하고 return하게 된다.

결과

코드

---

Kotlin

재귀

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var s1 = ""
private var s2 = ""
private var ans = -1
private lateinit var memo: Array<IntArray>

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val size1 = s1.length
    val size2 = s2.length
    for (i in 1 .. size1) {
        for (j in 1 .. size2) {
            ans = ans.coerceAtLeast(LCS(i, j))
        }
    }

    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun LCS(n: Int, m: Int): Int {
    if (m == 0 || n == 0) return 0

    if (memo[n][m] != -1) {
        return memo[n][m]
    }

    if (s1[n - 1] == s2[m - 1]) {
        memo[n][m] = LCS(n - 1, m - 1) + 1
    } else {
        memo[n][m] = 0
    }

    return memo[n][m]
} // End of LCS

private fun input() {
    s1 = br.readLine()
    s2 = br.readLine()
    memo = Array(s1.length + 1) { IntArray(s2.length + 1) { -1 } }
} // End of input()

반복문

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var str = ""
private var str2 = ""


fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()
    var ans = 0
    var len1 = str.length
    var len2 = str2.length
    var arr = Array(len1 + 1) { IntArray(len2 + 1) }

    for (i in 1 .. len1) {
        for (j in 1 .. len2) {
            if (str[i - 1] == str2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1
                ans = Math.max(ans, arr[i][j])
            }
        }
    }

    sb.append(ans)
    bw.write(sb.toString())
    bw.close()
} // End of main

private fun input() {
    str = br.readLine()
    str2 = br.readLine()
} // End of input