(백준) "7579번: 앱" 문제를 풀며 리소스 관리 공부하기(?) | pseudo, kotlin

백준 문제를 풀다 앱 개발자의 눈에 띈 문제 제목.

문제 내용을 읽어보며 효율적인 메모리 관리에 대해 다시 일깨울 수 있었던 좋은 시간이다.

음음 좋은 내용이군

 

 

문제 이해

문제 내용이 좀 길지만, 입출력 설명과 함께 읽으면 쉽게 이해할 수 있다.

 

각 줄의 역할을 간단히 요약해보자.

• 활성화된 앱 개수 N, 비워야하는 메모리 M.
• 활성화된 앱의 현재 메모리 나열.
• 활성화된 앱을 비활성화할 때 발생하는 비용 나열.

그리고 위의 입력 조건을 조금 단순화하여 읽어 보자.

• 개수 N, 최소 capacity M.
• capacity 나열.
• cost 나열.

그렇다... 이것은 최소 비용으로 짐을 싸는 0-1 knapsack 문제의 응용 버전이다!

 

응용이므로 차이점을 명확하게 파악하고 구현하는 것이 중요하다. 문제될만한 점을 몇 개 짚어보자.

knapsack 문제는 기존의 값을 이용할 때 dp 혹은 백트래킹을 사용하게 된다. 가장 단순한 dp는 O(NM)의 시간이 걸리고 백트래킹은 최대 O(2^n)의 시간이 걸리지만, 제한 시간은 1초이고 M은 최대 10,000,000의 값을 가질 수 있기 때문에 메모리 초과나 시간 초과의 위험성이 크다.

왜 다른 knapsack 문제와 조건이 다른데 O(NM)이 걸리는가? 문제를 역으로 해석하면, 배낭에서 제일 탐욕스럽게 가져가고 싶으므로 전부 다 넣은 다음 최소한의 리스크로 버리고 가는 방법을 구했다는 거다. 그러므로 필요 메모리 대신 (전체 메모리 - 필요 메모리) 매개변수를 전달하여 도출된 결과 비용을 전체 메모리에서 빼주면 된다. 그런 식으로 구하면 가장 단순한 O(NM)이 되며, M이 매우 큰 경우 시간 초과가 난다.

근데 질문 글 보면 O(NM)이 통과하는 경우도 있다고 함

 

그럼 어떻게 파훼하면 좋을까? 실력 향상을 위해 공부 중이라면 이 아래는 더 읽지 말고 직접 풀어보는 것을 추천한다. 결국 알고리즘 문제 풀기의 가장 중요한 키 포인트는 "문제 이해 능력"과, 이해한 내용에 대한 해결책을 "구현해낼 수 있는 능력" 이 두 가지라 생각한다. 간단한 문제 이해는 위에서 했으니, 스스로 구현해보면서 조건 파훼를 직접 해보는 것이 공부에 도움될 것이다.

 

그럼 문제를 다시 읽어 보면서 풀이 법을 개선해보자. 일단 메모리 초과는 분명히 일어날 것이기 때문에, 메모리(M)축 데이터를 변경해야한다. 문제의 조건 중 하나가 최소 메모리를 넘어야하는 것이므로, 축 데이터를 "비용"으로 변경해도 결과 값을 찾을 수 있다. 축 두 개를 (index, cost)로 하여 knapsack dp 배열을 모두 채운 뒤, 가장 낮은 cost 부터 순회하여 기준 M을 넘는 값을 찾으면 된다.

이 경우 최대 O(N*∑c) 시간이 걸리므로 안전한 탐색을 할 수 있다.

 

 

풀이

이제 문제를 이해했으니 직접 구현해보자.

나는 안드로이드 개발자이기 때문에 Kotlin으로 문제를 풀었다. 하지만 설명은 pseudo code(슈도 코드)로 작성할 것임.

 

코테 문제를 풀 때 main 함수 안에 70줄이 넘는 코드 줄을 다 때려넣어서 구현하는 사람들이 있다. 취미가 아니라 취업을 목적으로 하는 것이라면, 중복되거나 가독성이 최악인 부분은 분리해서 함수로 정리하는 버릇을 들여보자. 취업을 위한 코테의 심사위원이라면 무작정 돌아가게만 해놓은 사람과, 구현한 의도가 잘 보이는 사람 중 후자를 선택하지 않을까?

아래의 pseudo code도 그런 방식으로 작성할 예정이다. main 함수는 아래와 같이 단순하게 정의한다.

main(args)
    Input N Number of apps (1 ~ 100)
    Input M Memory to free up (1 ~ 10,000,000)
    Input memories occupied by each app
    Input costs of disabling each app
    
    Output appDeactivate(N, M, memories, costs)

 

dynamic programming은 배열 구조로 저장하거나 재귀의 형태로 구현할 수 있는데, 데이터를 구하는 방향이 행(row, n)이지만 결과 값을 찾는 방향은 열(column, cost)이므로 재귀로 구현하기 까다로울 것이라 판단하고 배열을 택했다. 1차원 배열이나 2차원 배열 선택은 원하는 것으로 구현하면 된다. 실제로 모두 구현해보았는데 전부 통과했다.

위(2차원 배열) 보다 아래(1차원 배열)의 효율이 더 좋다

Algorithm appDeactivate(N, M, memories, costs)
    Output minimum cost for exceeding M from dp

    // Calculate with dynamic programming
    FOR i <- 0 to (n-1) DO
    	FOR j <- maxCost down to costs[i] DO
        	dp[j] <- max(
                    dp[j], // previously set value
                    dp[j minus costs[i]] plus memories[i]
                )

 

return 값으로 1차원 dp를 순회하여 M을 넘는 최소 cost를 찾아서 내보내면 된다.

Kotlin으로 구현한 코드는 아래와 같다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max

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

fun main(args: Array<String>) = with(br) {
    val input = readLine().split(' ')
    val n = input[0].toInt()
    val m = input[1].toInt()
    val memories = readLine().split(' ').map { it.toInt() }
    val costs = readLine().split(' ').map { it.toInt() }

    bw.write("${calc(n, m, memories, costs)}")
    bw.close()
    close()
}

fun calc(n: Int, w: Int, memories: List<Int>, costs: List<Int>): Int {
    val maxCost = costs.sum()
    val dp = IntArray(maxCost) { 0 }

    for (i in 0 until n) {
    	for (j in maxCost downTo costs[i]) {
            dp[j] = max(dp[j], dp[j - costs[i]] + memories[i]);
        }
    }
    return dp.indexOfFirst { it >= w }
}

 

문제 하나를 깊게 파보며 이것 저것 시도해보는 게 알고리즘 공부에 매우 큰 도움이 되는 것 같다. 좋은 경험이었다. 앞으로 푸는 문제들도 정답을 얻었다고 단순히 지나가버리지 말고, 의문이 드는 부분이 있다면 꼭 테스트 해봐야겠다.