[백준] 11053 (가장 긴 증가하는 부분 수열)

#1 알고리즘

Longest increasing subsequence - Wikipedia

위키백과에도 등재된 유명한 문제다. 위 링크에 문제 풀이 알고리즘을 표현한 GIF 이미지가 있다. 보자마자 문제 풀이 방향을 알게 된다.

 

#2 코드 - 코틀린

#2-1 첫번째 시도

lateinit var array: Array<Int>
lateinit var cached: HashMap<Pair<Int, Int>, Int>

fun main() {
    // array 만들기
    array = Array(readln().toInt()) { -1 }
    cached = HashMap()
    val arrayString: List<String> = readln().split(" ")
    for (i: Int in array.indices) {
        array[i] = arrayString[i].toInt()
    }

    // array 순회
    for (i: Int in array.indices) {
        recursiveTraversal(0, i, 0, array.size - (i + 1))
    }

    // 최댓값 출력
    println(cached.values.max())
}

fun recursiveTraversal(previousElement: Int, index: Int, previousSequenceSize: Int, elementCountToForward: Int) {
    if (
        index >= array.size || // index가 범위를 넘어갔거나,
        previousElement >= array[index] || // 증가 수열이 아니거나,
        (cached[Pair(previousElement, index)] ?: 0) >= previousSequenceSize + 1 || // 캐싱된 값보다 같 or 작거나,
        (cached[Pair(previousElement, index)] ?: 0) >= previousSequenceSize + 1 + elementCountToForward // 이번 순회와 앞으로 할 순회가 모두 증가 수열을 만족해도 현재 캐싱된 값보다 같 or 작다면
    ) {
        return
    }

    cached[Pair(previousElement, index)] = previousSequenceSize + 1

    for (i: Int in (index + 1)..<array.size) {
        recursiveTraversal(array[index], i, previousSequenceSize + 1, array.size - (i + 1))
    }
}

무식한 방법이다. 시간 초과가 뜨긴 하지만 맞긴 맞는 코드다. 나는 그 사실에 매몰되어 아래와 같은 방법을 매우 늦게 찾았다.

 

#2-2 두번째 시도

lateinit var array: Array<Int>
lateinit var cached: Array<Int> // cached[i]의 의미: array[0..i]에서 가장 긴 증가하는 부분 수열

fun main() {
    // array 만들기
    array = Array(readln().toInt()) { -1 }
    cached = Array(array.size) { 1 } // 기본값을 1로 둠
    val arrayString: List<String> = readln().split(" ")
    for (i: Int in array.indices) {
        array[i] = arrayString[i].toInt()
    }

    // array 순회
    for (i: Int in 1..<array.size) {
        traversal(i)
    }

    // 최댓값 출력
    println(cached.max())
}

fun traversal(nowIndex: Int) {
    // array[0..<nowIndex] 중에서 제일 크지만 동시에 현재 순회중인 원소(array[nowIndex])보단 작은 원소 탐색
    for (i: Int in 0..<nowIndex) {
        if (array[i] < array[nowIndex]) {
            cached[nowIndex] = maxOf(cached[nowIndex], cached[i] + 1)
        }
    }
}

첫번째 코드와 비교하면 쓸 데 없는 코드를 전부 삭제하고, 꼭 필요한 순회만 진행토록 변경했다. 두 코드 전부 2중으로 중첩된 for문이 사용된다는 것은 같지만, 첫번째 코드는 나만의 세계에 빠져서 문제 풀이 코드의 복잡도가 산으로 가고 있음에도 절제하지 않았다.

 

#3 동적 프로그래밍 사용 시의 마음가짐

#3-1 억지로 풀어선 안 된다

왜 나는 첫번째 코드에 매몰되었던걸까? 먼저, 동적 프로그래밍이 '중복 제거 도구'라는 사실에 너무나도 집착했다. 중복만 제거한다면 어떻든 상관없다는 마인드였다. 그렇게 문제 풀이 코드가 어거지로 동적 프로그래밍의 모양새를 갖추게 만들었다. 당연히 풀리긴 풀릴 것이다. 또, 브루트 포스 알고리즘보다는 더 빨리 풀리긴 할 것이다. 하지만 문제 풀이의 핵심 원리를 이해하려는 수고가 없는 영혼 없는 풀이다.

 

#3-2 '지식'이 아닌 '지혜'에 집중해야 한다

모든 난이도 있는 알고리즘 문제는 기술의 싸움이 아닌, 지혜의 싸움이라고 생각하자. 출제자는 내게 '동적 프로그래밍을 알고 있는가?'라고 묻지 않는다. 애초에 그런 문제는 누가봐도 쉽게 풀리게 생겼고 실제로도 그렇다.

 

기술은 기본이다. 내가 집중해야할 것은 그 지식을 활용하는 태도, 지혜다. 이 문제를 예로 들면, (테스트 케이스로서) 원소 하나하나 손으로 직접 써가면서 컴퓨터 입장에서 어떤 식으로 순회를 할 지 곰곰히 생각해봤어야 했다. 그렇게 동적 프로그래밍을 어떻게 접목시킬지 천천히 생각해봤더라면, 문제의 풀이 원리를 어렵지 않게 알 수 있었을 것이다.