![[애드혹 대표문제] 원형 배열 문제 풀이: modulo 인덱싱, 배열 두 배 확장, 회전 감각까지](https://bscodelab.com/wp-content/uploads/2026/05/thumbnail-87.png "[애드혹 대표문제] 원형 배열 문제 풀이: modulo 인덱싱, 배열 두 배 확장, 회전 감각까지")
원형 배열 문제는 끝과 끝이 이어진다는 점 때문에 처음 보면 유난히 헷갈립니다. 하지만 핵심은 복잡한 공식을 더하는 것이 아니라, 원을 선형처럼 다시 표현하는 발상을 먼저 잡는 것입니다.
이번 글은 modulo 인덱싱, 배열 두 배 확장, 시작점 고정, wrap-around window라는 네 가지 축으로 원형 배열 문제를 차근차근 정리합니다. 코드보다 먼저 왜 이렇게 생각해야 하는지를 작은 예시로 설명하겠습니다.
원형 배열이 왜 헷갈릴까
일반 배열은 왼쪽 끝과 오른쪽 끝이 분리되어 있습니다. 그런데 원형 배열은 마지막 다음이 다시 처음으로 이어집니다. 이 연결 하나 때문에 선형 배열에서는 떨어져 보이던 구간이 원에서는 붙어 있는 구간이 됩니다.
예를 들어 [3, 1, 4, 2, 5]에서 원형으로 연속한 세 칸은 [2, 5, 3]처럼 보일 수도 있습니다. 직선 배열 눈으로 보면 끊겨 있지만, 원 위에서는 자연스럽게 이어진 구간입니다.
원형 배열의 핵심은 새로운 알고리즘을 외우는 것이 아니라, 끊어진 것처럼 보이는 구간을 다시 이어서 보는 표현 전환입니다.
원형 배열 첫 발상: modulo 인덱싱
가장 기본은 modulo 인덱싱입니다. 배열 길이가 n일 때 현재 위치가 i이고 오른쪽으로 k칸 간다면 보통 (i + k) % n으로 다음 위치를 표현합니다.
길이가 5인 배열에서 인덱스 4에서 한 칸 더 가면 5가 아니라 다시 0이 되어야 합니다. 이때 (4 + 1) % 5 = 0이므로 wrap-around를 깔끔하게 처리할 수 있습니다.
- 현재 위치만 갱신하는 시계 문제
- 회전 후 특정 위치의 값만 묻는 문제
- 다음 칸, 이전 칸처럼 이웃 인덱스만 계산하는 문제
이런 문제는 modulo만으로도 충분한 경우가 많습니다. 다만 왼쪽 이동처럼 음수가 섞일 수 있으면 (i - k + n) % n처럼 한 번 보정하는 습관이 안전합니다.
손으로 먼저 보기
배열이 [10, 20, 30, 40, 50]이고 현재 인덱스가 3이라고 해보겠습니다. 여기서 오른쪽으로 4칸 이동하면 3 -> 4 -> 0 -> 1 -> 2가 됩니다.
직접 세도 답은 인덱스 2입니다. 식으로 쓰면 (3 + 4) % 5 = 2입니다. 이 감각이 잡히면 원형 배열의 많은 위치 계산은 한 줄로 정리됩니다.
배열 두 배 확장
원형 구간을 다룰 때는 modulo를 계속 섞는 것보다 배열을 두 번 이어 붙이는 편이 더 직관적일 때가 많습니다. [3, 1, 4, 2, 5]를 [3, 1, 4, 2, 5, 3, 1, 4, 2, 5]처럼 보는 방식입니다.
이렇게 하면 원에서 이어지는 구간도 선형 배열의 평범한 연속 구간으로 바뀝니다. 원형 구간 [2, 5, 3]도 두 배 배열에서는 그냥 붙어 있는 세 칸이 됩니다.
그래서 누적합, 고정 길이 구간 합, 슬라이딩 윈도우처럼 원래 선형 배열에서 쓰던 도구를 더 자연스럽게 가져올 수 있습니다.
고정 길이 원형 구간
배열 [5, 1, 3, 7]에서 원형으로 연속한 길이 2 구간의 합 최댓값을 구한다고 해보겠습니다. 후보는 [5, 1], [1, 3], [3, 7], [7, 5]입니다.
마지막 [7, 5]가 바로 원형 문제의 핵심입니다. 선형 배열에서는 떨어져 보이지만 원형에서는 붙어 있습니다. 두 배 배열 [5, 1, 3, 7, 5, 1, 3, 7]로 보면 이 구간도 그냥 연속한 두 칸으로 처리할 수 있습니다.
시작점 고정
회전 문제는 값보다 시작점이 더 큰 함정입니다. [3, 4, 5, 1, 2]와 [1, 2, 3, 4, 5]는 배열로 보면 달라 보이지만 원 위의 상대적 순서는 같습니다.
이럴 때는 절대 위치를 비교하지 말고 기준 시작점을 먼저 정해야 합니다. 예를 들면 최소값 위치를 시작점으로 잡거나, 특정 기준 원소가 처음 나오는 위치를 시작점으로 삼을 수 있습니다.
원형 구조에서는 시작점이 사실상 임의적입니다. 그런데 사람은 늘 0번부터 읽으려 하기 때문에 같은 배치도 다른 배열처럼 느낍니다. 시작점 고정은 이 착시를 없애는 장치입니다.
wrap-around window
슬라이딩 윈도우를 원형 배열에 적용할 때도 발상은 같습니다. 원을 직접 따라가지 말고 두 배 배열 위에서 선형 윈도우처럼 움직이면 됩니다. 특히 길이 k가 고정된 원형 구간 합 문제에서 매우 자연스럽습니다.
다만 여기서 중요한 제한이 하나 있습니다. 두 배 배열을 만들었더라도 실제 시작점은 0부터 n - 1까지만 의미가 있고, 실제 구간 길이도 보통 n을 넘기면 안 됩니다.
원형 배열에서 두 배 확장을 썼더라도, 의미 있는 시작점은 n개뿐이고 실제 구간 길이도 보통 n을 넘기면 안 됩니다.
코드 예시: modulo 인덱싱
먼저 현재 위치에서 오른쪽으로 step칸 이동한 뒤의 값을 읽는 가장 기본 예시입니다. 시계 이동이나 회전 후 위치 조회처럼 위치 계산 중심 문제에서 바로 쓸 수 있습니다.
def next_value(nums, start, step):
n = len(nums)
idx = (start + step) % n
return nums[idx]코드 예시: 원형 고정 길이 윈도우
이번에는 길이 k인 원형 연속 구간의 최대 합을 구해보겠습니다. 두 배 배열을 만든 뒤, 시작점이 n개뿐이라는 점만 지키면 선형 슬라이딩 윈도우처럼 풀 수 있습니다.
def max_circular_window_sum(nums, k):
n = len(nums)
doubled = nums + nums
window_sum = sum(doubled[:k])
answer = window_sum
for right in range(k, n + k - 1):
window_sum += doubled[right]
window_sum -= doubled[right - k]
answer = max(answer, window_sum)
return answer왜 반복 범위가 n + k - 1인지 헷갈릴 수 있습니다. 이유는 가능한 시작점이 0부터 n - 1까지 정확히 n개이기 때문입니다.
코드 예시: 회전 시작점 찾기
정렬된 배열이 회전된 형태라면 어디서 오름차순이 한 번 끊기는지를 보면 시작점을 잡을 수 있습니다. 아래 코드는 가장 작은 값이 시작되는 위치를 찾는 가장 단순한 감각 예시입니다.
def rotation_start(nums):
n = len(nums)
for i in range(n):
if nums[i] > nums[(i + 1) % n]:
return (i + 1) % n
return 0문제를 보면 무엇부터 떠올릴까
- 위치만 바뀌면 modulo 인덱싱부터 본다
- 원형 구간을 다루면 배열 두 배 확장을 먼저 의심한다
- 같은 배치를 다른 시작점에서 본 것 같으면 시작점 고정을 생각한다
- 연속 구간을 빠르게 훑어야 하면 wrap-around window를 떠올린다
원형 배열이라고 해서 무조건 같은 기법을 쓰는 것은 아닙니다. 문제의 중심이 위치인지, 구간인지, 회전 비교인지 먼저 나누면 훨씬 빠르게 방향이 잡힙니다.
자주 틀리는 실수
- modulo를 빼먹고 범위를 벗어난 인덱스에 접근한다
- 음수 이동에서 언어별 modulo 차이를 놓친다
- 두 배 배열을 만들고도 시작점을 2n개 전부 본다
- 원래 길이보다 긴 구간을 허용해 같은 원소를 두 번 센다
- 회전 문제인데 시작점을 고정하지 않고 배열 모양만 비교한다
원형 배열 문제는 알고리즘이 부족해서 막히는 경우도 있지만, 더 자주 막히는 이유는 표현 방식을 잘못 잡기 때문입니다. 문제를 보자마자 원을 직접 시뮬레이션하려 하지 말고, 먼저 선형으로 바꿀 방법부터 찾는 습관이 중요합니다.
함께 보면 좋은 글
왜 이런 문제에서 공식보다 표현 전환이 중요한지는 애드혹 문제란 무엇인가에서 먼저 볼 수 있습니다. 반례를 어디서 잡아야 하는지는 애드혹 문제 풀이법: 규칙 찾기와 반례가 도움이 됩니다.
선형 구간 감각을 먼저 다지고 싶다면 투 포인터 알고리즘이란 무엇인가도 같이 읽어보면 좋습니다. modulo 연산의 기본 성질은 Python 공식 문서의 arithmetic operations 설명도 참고할 수 있습니다.
마무리
원형 배열 문제를 어렵게 만드는 것은 원 그 자체보다, 직선 배열 습관이 계속 남아 있기 때문입니다. 그래서 시작할 때부터 이걸 원 위에서 그대로 구현할까가 아니라 이걸 어떤 방식으로 선형처럼 바꿀까라고 질문해야 합니다.
이 감각만 잡히면 시계 문제도, 회전 배열도, 양끝이 이어진 구간 문제도 훨씬 차분하게 풀 수 있습니다. 원형 배열을 만나면 먼저 modulo, 두 배 확장, 시작점 고정, wrap-around window를 떠올려 보세요.
