2025 국가직 9급 알고리즘 해설

핵심 개념

최대 연속 부분합(Maximum Subarray Sum)과 카데인 알고리즘

연속 부분합의 최댓값이란 배열에서 이웃한 원소들을 끊김 없이 이어 붙였을 때 나올 수 있는 합 중 가장 큰 값을 말합니다. 모든 구간을 다 더해 보면 O(n²)이지만, 카데인(Kadane) 알고리즘을 쓰면 O(n)에 풀립니다. 방법은 간단합니다. 왼쪽부터 훑으면서 '현재 원소에서 끝나는 최대 구간합'을 계속 갱신하는데, 직전까지의 누적합에 현재 원소를 더한 값과 현재 원소 하나만 취한 값 중 큰 쪽을 고릅니다. 누적합이 음수가 되면 그 구간은 버리고 새로 시작하는 것이 핵심입니다. 그렇게 갱신되는 값들 중 최댓값이 정답이 됩니다.

핵심 개념

이진 탐색(binary search)의 전제 조건과 시간 복잡도

이진 탐색은 정렬된 데이터의 중앙값과 찾는 값을 비교해, 찾는 값이 더 작으면 왼쪽 절반, 크면 오른쪽 절반만 남기는 방식으로 탐색 범위를 매번 절반으로 줄여 나가는 알고리즘입니다. 가장 중요한 전제는 '데이터가 정렬되어 있어야 한다'는 점입니다. 정렬되어 있지 않으면 중앙값 비교만으로 어느 쪽을 버릴지 판단할 수 없어 알고리즘 자체가 성립하지 않습니다. n개의 데이터를 절반씩 줄이므로 비교 횟수는 log₂n에 비례하고, 시간 복잡도는 O(log n)입니다. 또한 임의 위치 접근이 가능해야 하므로 배열처럼 인덱스 접근이 O(1)인 자료구조에 적합합니다.