시간복잡도를 고려한 알고리즘 선택전략(프로그래머스-퍼즐 게임 챌린지)
시간복잡도를 고려한 알고리즘 선택전략(프로그래머스-퍼즐 게임 챌린지) — #이진탐색 #브루트포스 #binarySearch #개발자의도구들 사용된 언어: 코틀린, 혹은 파이썬 순서: 로직, 코...
#이진탐색 #브루트포스 #binarySearch #개발자의도구들
- 사용된 언어: 코틀린, 혹은 파이썬
- 순서: 로직, 코드 구현, 코드 분석
Brute force를 섣불리 결정하지 말라
프로그래머스(lv2. 퍼즐 게임 챌린지)
https://school.programmers.co.kr/learn/courses/30/lessons/340212
이번 문제는 시간복잡도를 고려하는 것이 알고리즘 선택에 있어서 얼마나 중요한지 깨닫게 되는 문제였습니다. 이유는 한정된 시간동안 빠르게 문제의 본질을 파악해서 알고리즘을 잘 작성할 수 있냐가 중요하기 때문에, 코딩을 하는 생각 자체에 모순이 존재하면, 절대로 정답을 찾을 수 없기 때문입니다.
이번 문제는 Level 특정 set이 존재하지않아서 그냥 brute force로 푸는게 아니면 정답을 찾기 어렵다 판단하였습니다. 범위가 1부터 100,000이라서 그냥 처음부터 돌려버릴 생각을 했습니다.
하지만, brute force로 풀면 시간복잡도가 O(n²)이고 입력값이 10만 \* 30만으로 약 300억의 연산이 수행됩니다. 이는 절대로 해당 문제가 O(n²)이 아님을 시사합니다.
⚠️ 문제 풀이에 급급해서 섣부르게 알고리즘을 결정하지 말아요.
선형적인 탐색의 구세주
대부분의 알고리즘 문제가 선형탐색인 듯 하지만 아닌 경우가 상당히 많습니다. 선형탐색은 누구나 쉽게 생각할 수 있는 문제기도 하고, 정답으로 사용한다면 문제가 단순해지기 때문에 일부러 입력값을 높이는 것 같이 느껴지기도 합니다.
선형탐색을 사용할 때는 항상 1. 시간복잡도를 먼저 고려, 2. 입력값의 크기를 고려 할 필요가 있습니다. 대부분의 겨우 O(n²)과 10만 이상의 입력값이 주어져 선형탐색을 좌절케 합니다.
이에 따른 문제 해결전략은 대부분의 경우 이진탐색입니다. 그러고 보면 이진탐색은 이 선형 탐색의 한계를 개선하기 위해 만들어진 알고리즘이라 해도 과언이 아니겠네요.
😯 이진 탐색을 사용하면 O(n²) -> O(nlogn)으로 획기적으로 시간을 줄일 수 있다.
1차 시도
Brute force
1차적으로 Brute force로 시도했습니다. 입력값을 충분히 고려하지 않은 상태로 작성하는 오류를 범했습니다.
class Solution {
fun solution(diffs: IntArray, times: IntArray, limit: Long): Int {
var level: Int = 0
val qLen = diffs.size
while (true) {
level++
var test = 0L
for (i in 0 until qLen) {
// 1. 현재 레벨을 바탕으로 시간을 계산
if (level >= diffs[i]) {
test += times[i]
continue
}
// level 딸리는 경우
if (i > 0) {
test += (diffs[i] - level) * (times[i -1] + times[i])
} else {
test += (diffs[i] - level) * (times[i])
}
}
if (test <= limit) {
break
}
}
return level
}
}
해당 알고리즘은 애초에 시간 복잡도에서 탈락인데, 자신보다 큰 level을 푸는 부분에서 마지막에 자기 자신의 퍼즐을 푸는 시간을 더해주지 않아서 오답이 되기도 했습니다.
if (i > 0) {
test += (diffs[i] - level) * (times[i -1] + times[i]) + times[i]
} else {
test += (diffs[i] - level) * (times[i]) + times[i]
}
2차 시도
이진 탐색
start 와 end를 조절 하여 범위를 줄여나간다.
* middle = level이다.
1. 해당 level에 시간 초에 해결된다면, end를 낮춘다.
2. 시간 초과가 난다면, start를 높인다.
class Solution {
fun solution(diffs: IntArray, times: IntArray, limit: Long): Int {
var answer: Int = 0
var start = 1
var end = 100000
while (start <= end) {
val level = (start + end) / 2
var time = 0L
for (i in 0 until diffs.size) {
if (level >= diffs[i]) {
time += times[i]
continue
}
if (i == 0) {
time += (diffs[i] - level) * (times[i]) + times[i]
} else {
time += (diffs[i] - level) * (times[i] + times[i - 1]) + times[i]
}
}
if (time > limit) {
start = level + 1
} else {
end = level - 1
}
}
return start
}
}
👉 오류를 찾는건 너무 어렵다... 실제 환경에서는 멘붕이 올 것 같음
1. 경계값 명확하게 하기
2. 이진 탐색의 경우 값 업데이트를 명확하게 해야한다.
--- start = middle + 1로 초기화
--- end = middle - 1로 초기화 해야함
--- 단 조건이 while (start <= end) 인 경우
while문이 끝나면 start == end가 되므로 정답은 start or end이다.