안녕하세요!
알고리즘 고수가 되고싶은 개발자 꿈나무 김조현입니다.
이번 글에서는 백준 1912번 문제를 코틀린으로 풀어본 과정을 정리할 것입니다.
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력 1
10
10 -4 3 1 5 6 -35 12 21 -1예제 출력 1
33예제 입력 2
10
2 1 -4 3 4 -4 6 5 -5 1예제 출력 2
14예제 입력 3
5
-1 -2 -3 -4 -5예제 출력 3
-1첫 번째 풀이
fun main() {
val result = mutableListOf<Int>()
val n = readln().toInt()
val nList = readln().split(" ").map{ it.toInt() }
for (i in 0..nList.size) {
for (j in i + 1..nList.size) {
result.add(nList.subList(i, j).sumOf{ it })
}
}
println(result.maxOf{ it })
}결과
시간 초과
첫 번째 풀이는 리스트를 경우의 수대로 전부 쪼개서 그 리스트들의 합중 가장 큰 수를 출력하도록 풀었습니다. 하지만 시간초과로 틀리는 결과를 가져왔습니다.
이 때 들었던 생각은 이중 for문과 subList를 계속 사용하면서 시간복잡도가 커졌구나 라는 생각을 가졌습니다.
이 문제를 해결하기 위해 이중 for문 또는 subList를 하지 않는 방향으로 풀어보고자 노력했습니다. 하지만 제가 가진 지식으로는 못풀겠다는 생각이 들어 풀이를 참고한 후에 맞췄습니다.
두 번째 풀이
import kotlin.math.max
fun main() {
val n = readln().toInt()
val nList = readln().split(" ").map{ it.toInt() }
val dp = IntArray(n)
dp[0] = nList[0]
var maxNum = dp[0]
for (i in 1 until n) {
dp[i] = max(nList[i], dp[i - 1] + nList[i])
maxNum = max(dp[i], maxNum)
}
println(maxNum)
}결과
정답
이 풀이에서는 DP를 사용하여 풀었습니다. DP에 대해서는 따로 글을 작성하여 후에 링크를 첨부하겠습니다.
알고리즘의 순서는 다음과 같습니다.
- 리스트의 크기만큼의 배열을 만들고 배열의 첫 번째 값은 입력 리스트의 첫 번째 값으로 저장합니다.
- 각 배열에는 해당 인덱스의 리스트 값과 해당 인덱스까지 더한 값을 비교하여 더 큰 수를 배열의 다음 인덱스에 지정합니다.
이런 풀이가 허용되는 이유는 해당 인덱스까지 리스트의 수를 전부 더한 값이 리스트의 다음 인덱스의 값보다 작다면 앞에서 더한 값은 최선이 아니게 됩니다. 그렇기에 배열의 다음 인덱스를 리스트의 앞의 수를 더한 수가 아닌 리스트의 다음 인덱스의 값으로 지정하는 과정으로 쓸데없는 계산을 막아줄 수 있습니다. - 배열을 지정한 후에 최대값과 비교하여 더 큰 수를 최대값으로 지정합니다.
마무리입니다!
처음에는 이 문제에 대한 정리글을 쓸까? 고민을 했었습니다. 왜냐하면 이 문제는 제가 스스로 푼 문제가 아니라 다른 사람들의 풀이를 참고해서 풀은 문제이기 때문입니다.
하지만 블로그의 목적은 내가 잘한 것을 자랑하는게 아니라 내가 공부 과정에서 배우고 느낀 점을 공유하고 글로 정리해보는 공간이라고 생각이 드는 순간 일단 써보고 봐야겠다고 생각했습니다.
또한 처음에는 풀지 못하는 문제에 대해 풀이를 보는 것이 무척 꺼렸었습니다. 하지만 크루분이 했던 1시간 지나도 풀지 못하는 문제는 계속 봐도 못푼다는 말을 생각하며 풀이를 봤습니다. 문제를 푸는 것만 공부가 아니라 내가 모르는 것을 알고 배우는 것도 공부구나 라는 것을 깨달을 수 있었습니다.
풀이를 보며 잊고 지내던 DP 개념을 다시 떠올리며 문제를 이해할 수 있었습니다. 사실 DP로 푼다는 것을 알아도 이 문제를 풀 수 있었을까? 라는 생각이 들긴하지만, 다음에 이런 문제를 풀면 시도는 해볼 수 있겠다라는 자신감이 생겼습니다.
이렇게 못푼 문제는 캘린더에 따로 적어놓고 3일 후에 다시 풀어보며 개념 정리를 확실히 하는 방향으로 학습하고자 합니다.
DP도 하향식, 상향식, 메모이제이션? 처럼 다양한 종류를 가지는데 이는 아직 확실하게 알지 못해 따로 DP에 대한 개념 정리글을 작성해보며 공부할 계획입니다.
이렇게 저의 첫 알고리즘 풀이 글을 마무리해보겠습니다. 매일 하나씩 풀고 써보려고 노력해보겠습니다.
읽어주셔서 감사합니다!🙂↕️
