알고리즘 문제를 풀다보면, 어느 한 문제에서는 사용해야 풀 수 있던 어떤 기능이 다른 문제에선 오히려 그 문제를 푸는데 악영향을 끼치기도 한다. 이번에 논의할 max()와 min()도 바로 그러한데, max()와 min()는 처리되는데 O(n)의 시간이 걸리므로 무턱대고 반복문 내에서 사용했다간 시간을 엄청나게 잡아먹어버린다. 우선 max()와 min()의 시간복잡도를 먼저 알아보고 그 이후 예시와 함께 어떤 문제에서 이 기능을 활용하면 좋을지 살펴보기로 한다.
max(), min()의 시간복잡도
max()와 min()함수에는 입력값으로 배열을 넣을 수 있고, 배열을 넣게 되면 해당 함수는 모든 원소의 값을 비교해서 가장 큰 값을 반환해준다. 이렇게 max()와 min()은 함수 내부에서 모든 원소를 하나씩 비교하면서 최댓값 또는 최솟값을 찾기 때문에 시간복잡도는 O(n)이 된다. 이는 파이썬 뿐만 아니라 대부분의 언어가 배열에서 최댓값이나 최솟값을 찾아주는 함수에서는 시간복잡도 O(n)이 나온다.
그럼 max()나 min()은 어떤 상황에서 사용하면 좋을까?
max()와 min()을 어디에 사용하면 좋을지 논의하기 앞서 다음 두 문제를 살펴보자.
둘 중 하나는 max()를 사용하는 것이 효율적이지만, 다른 한 문제는 max()를 사용하면 성능에 매우 안 좋다.
배열의 원소로 디딤돌이 주어진다. 각 디딤돌에는 숫자가 쓰여 있어서 디딤돌을 밟을 때마다 숫자가 감소한다. 숫자가 0이 되면 밟을 수 없고 이 때부터는 건너뛸 수 있게된다. 한 번에 건너 뛰어서 갈 수 있는 칸 수는 k로 주어지게 되고, k보다 더 많이는 건너 뛸 수 없다. 예를 들어 k = 3으로 주어진다면, 두 칸의 0을 무시하고 세번째 칸에 착지할 수 있다. 세 칸의 0을 무시하고 건너뛸 순 없다. 이렇게 디딤돌 배열과 최대 점프 칸수 k가 주어질 때, 건널 수 있는 사람들의 수를 구하라 아래 예시에서는 총 3명이 건널 수 있다.
[입출력 예]
오답 - 순차탐색
이 문제에서 순차탐색(max 또는 min)을 사용하면 시간초과가 발생한다.
정답 - 이진탐색
이 문제는 이진탐색을 사용하면 시간내로 풀 수 있다.
중요한 것은 해당 문제에서 max(), min() 함수를 사용하면 O(n)에 의해 시간초과가 발생한다는 것이다.
스티커에는 숫자가 쓰여있고, 스티커를 한 칸씩 뜯을 수 있다. 하나의 스티커를 뜯으면 그 스티커의 양 옆 스티커는 뜯을 수 없고, 한 칸 건너서는 뜯을 수 있다. 배열의 처음과 마지막은 연결되어 있다. 즉, 스티커가 원형으로 연결되어있다. 모든 수를 합산해서 최댓값을 가지도록 최대한 스티커를 뜯을 때, 그 최댓값은 얼마인지 구하라. 아래 예시에서는 최댓값이 36이 나온다.
[입출력 예]
전형적인 다이나믹 프로그래밍 문제다. 다이나믹 프로그래밍은 연산을 기록할 수 있는 배열 공간을 생성하는 것부터 시작된다.
이문제의 경우 처음과 끝이 연결되어있다고 하니 조금 까다롭게 느껴질 수 있다. 이 경우엔 첫번째 스티커를 뜯을 때는 반드시 마지막 스티커는 뜯으면 안 되고, 두번째 스티커를 뜯을 때는 마지막 스티커를 뜯어도 된다. 이것을 case 별로 나눠서 각 case 별로 기록 배열을 다르게 사용해서 두 case 각각 최댓값을 구하고, 그렇게 구한 두 개의 최댓값을 다시 서로 비교하여 더 큰 값을 answer로 반환하면 된다.
이 문제는 전형적인 다이나믹 프로그래밍 문제로, 두 수를 비교할 때 max()함수가 매우 유용하게 사용된다. 시간초과 문제도 전혀 없다.
그렇다면, 학습하는 사람은 고민이 생길 수 있다.
'둘 다 똑같이 반복문 내에서 max()를 실행했는데, 어떤 문제는 오래 걸려서 시간초과가 발생하고, 어떤 문제는 시간 초과 문제가 없군?'
사소하지만 혼란스러움이 발생할 수도 있는 부분이다. max() <- 이 함수 자체가 오래 걸린다고 생각해서 아예 사용하지 않는 습관을 가졌다면, 이 다이나믹프로그래밍 문제를 빠르게 풀기는 어려웠을 것이다. 반대로 습관적으로 max()를 사용하다간 특정 문제에선 시간초과가 발생할 수 있다. 그럼 어떤 문제가 max()를 사용하기 적합할까?
max(), min()에 들어가는 인자의 개수를 잘 보자
징검다리 건너기
이 문제의 제약사항을 잘 살펴보면 다음과 같은 조건이 눈에 띈다.
주어지는 배열의 크기는 20만이하이고, 점프할 수 있는 최대치 k는 최대로 배열의 크기만큼 주어질 수도 있다. 즉, 슬라이딩윈도우 기법을 사용할 때 k 값이 적절히 커버리면, max()가 검사해야하는 원소의 개수가 많아져서 시간복잡도가 증가하게 된다. 예를 들어 주어진 배열의 크기는 20만이고, k는 10만이라고 한다면, 윈도우를 움직이는데 10만번이 소요되고, 각 윈도우에서 max()함수를 사용하는데에 10만번의 비교 연산이 일어난다면, 총 연산은 100만번이 되는 것이다. 연산의 수가 확 증가하게 되므로 시간초과가 당연히 날 수 밖에 없다.
그러므로 이와 같이 max()의 인자로 들어가는 배열의 크기가 얼마든지 길어질 수 있는 조건에서는 반복문 내에서 max()함수를 함부로 사용하지 않는 것이 좋다. 너무 시간이 많이 걸릴 것이기 때문이다.
스티커 모으기(2)
반대로 이 문제에선 max()에 들어갈 인자는 두 개로 제한된다. max()의 시간복잡도는 O(n)이라고 알려져있지만, 이 문제의 경우 주어지는 배열의 길이와는 상관없이 max()에 들어가는 인자의 값이 항상 두개로 제한되어있으므로 실질적으로 max()함수의 시간복잡도는 O(1)이 된다.
위 코드의 실질적인 시간복잡도는 O(n)이 된다. 그러므로 얼마든지 반복문 내에서도 max()함수를 사용할 수 있는 것이다.
결론
이처럼 max()나 min()함수를 사용할 때는 주어진 배열의 길이를 고려할 필요가 있다. 본문에서는 max()와 min() 함수만을 언급했지만, append나 pop 또는 in 또는 파이썬의 슬라이스 인덱싱을 사용할 때에도 시간복잡도를 반드시 고려해볼만 하다. 아래는 파이썬 공식 문서에서 각 기본 함수별 시간 복잡도를 기록해놓은 것을 가져온 것이다.
특정 기능을 사용할 때에는 그 기능이 우리에게 주어진 제약 조건에서 유효한 전략인지 반드시 따져볼 필요가 있는 것 같다. 기능이 가진 특성을 생각하지 않고 적용해버리면 효율성이 매우 나쁜 코드가 완성되기 때문이다.
