문제 이해하기
로드 트립을 떠나는 자전거 타는 사람(바이커)이 있다고 가정해 보겠습니다. 그의 여행 경로에는 서로 다른 고도에 위치한 n개의 지점이 있으며, 바이커는 고도 0인 0번 지점에서 여행을 시작합니다.
n개의 원소를 가진 배열 gain이 주어졌을 때, gain[i]는 i번째 지점과 i+1번째 지점 사이의 순수한 고도 변화량을 의미합니다(0 <= i < n). 우리가 구해야 하는 것은 지나간 모든 지점 중 가장 높은 고도입니다.
예를 들어 입력이 gain = [-4, 2, 6, 1, -6]이라면 출력은 5가 됩니다. 각 지점의 고도는 시작점부터 차례대로 [0, -4, -2, 4, 5, -1]이 되고, 이중 최댓값은 5이기 때문입니다.
해결 접근 방법
이 문제는 누적 합(running sum) 개념을 활용하면 간단하게 해결할 수 있습니다. 각 지점에 도달할 때마다 고도 변화량을 계속 더해 나가면서, 그중 가장 큰 값을 기록하면 됩니다. 구체적인 단계는 다음과 같습니다.
maximum(최댓값)을 0으로 초기화합니다.
run_alt(현재까지의 누적 고도)를 0으로 초기화합니다.
gain 배열의 각 요소 delta에 대해 아래 과정을 반복합니다.
run_alt에 delta를 더해 현재 고도를 갱신합니다.
maximum과 run_alt를 비교하여 더 큰 값으로 maximum을 업데이트합니다.
모든 반복이 끝나면 maximum을 반환합니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리는 O(1)로 매우 효율적입니다.
예제 코드 (Python)
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
def solve(gain): maximum = 0 run_alt = 0 for delta in gain: run_alt += delta maximum = max(maximum, run_alt) return maximum gain = [-4,2,6,1,-6] print(solve(gain))
입력
[-4,2,6,1,-6]
출력
5