학습 철학 회고
알고리즘 템플릿을 무작정 외우는 것을 경계하며, 뼈대 코드의 아주 사소한 '초기화 값' 하나까지 극한으로 의심해 보았습니다. "왜 뻔히 더할 첫 번째 값을 놔두고0으로 시작해서 덧셈 연산을 한 번 낭비하는가?"에 대한 답을 치열하게 고민했고, 그 결과 우아한 템플릿이 지불하는 '가장 값싼 보험료'의 비밀을 깨달았습니다.
📌 문제 요약: 백준 2003번 (수들의 합 2)
N개의 자연수로 이루어진 배열에서, 연속된 부분 배열의 합이 정확히 M이 되는 경우의 수를 구하는 문제입니다.
- 이 최대 10,000이므로 이중
for문을 돌리면 이 되어 비효율적입니다. - 배열의 원소가 모두 '자연수'라는 단조성(Monotonicity)이 보장되므로, 같은 방향으로 전진하는 투 포인터(애벌레 방식)를 사용하여 단 한 번의 스캔 으로 해결할 수 있습니다.
💻 정답 코드 (SOP 적용)
import sys
input = sys.stdin.readline
def two_pointers(N, M, A):
# 배열 구간 [start, end)의 시작점과 끝점, 그리고 구간의 합 초기화
end = 0
total = 0
count = 0
# start를 0부터 N-1까지 차례대로 순회
for start in range(N):
# 1. 합이 M보다 작고, end가 배열의 끝에 도달하지 않았다면 계속 합을 키움
while total < M and end < N:
total += A[end]
end += 1
# 2. while문을 빠져나왔을 때 합이 정확히 M과 일치하는지 확인
if total == M:
count += 1
# 3. 다음 start로 넘어가기 전, 현재 꼬리(start)가 가리키는 값을 합에서 빼줌
total -= A[start]
return count
def solution():
N, M = map(int, input().split())
A = list(map(int, input().split()))
print(two_pointers(N, M, A))
if __name__ == "__main__":
solution()🚨 [핵심 회고] 우리는 왜 total = 0으로 시작해야 하는가?
투 포인터를 구현하면서 가장 납득하기 어려웠던 부분은 초기화 로직이었습니다.
"어차피 첫 번째 원소를 참조할 거라면, 처음부터 total = A[0]으로 꽉 채워서 시작하면 while문의 첫 번째 0 + A[0] 덧셈 연산을 아낄 수 있는 것 아닌가? 왜 쓸데없이 0으로 시작해서 루프를 낭비하게 만들까?"
이 1회의 연산을 아끼기 위한 '수동 언롤링(Manual Loop Unrolling)' 최적화 시도가 왜 오히려 독이 되는지, 컴퓨터의 시각에서 3가지 근거를 찾아냈습니다.
💡 나의 깨달음: 0으로 초기화하는 것은 낭비가 아니라 '영점 조절'이다.
1. 배열 참조 횟수는 사실 똑같다.
밖에서A[0]을 미리 꺼내든, 안에서A[0]을 더하든 결국 메모리 접근 횟수는 정확히 1번으로 동일하다. 절대적인 시간 이득이 생각보다 미미하다.2. 덧셈 1번 아끼려다 '분기문(Branch)' 폭탄을 맞는다.
만약 밖에서A[0]을 무작정 참조하려면, 배열이 비어있을 때(N = 0) 발생하는IndexError를 막기 위해 함수 최상단에if N == 0: return 0이라는 방어 로직을 반드시 넣어야 한다. 현대 CPU 아키텍처에서 단순 덧셈 비용은 거의 0에 수렴하지만, 이 조건 분기문(Branch)은 파이프라인을 깰 수 있어 비용이 훨씬 비싸다. 배보다 배꼽이 더 커진다.3. 가장 버그가 적은 수학적 구간 설계:
[start, end)(start 포함, end 미포함)
투 포인터에서 창문(Window)의 범위를[start, end)로 설계하는 것이 실전에서 헷갈리지 않고 버그를 최소화하는 핵심 비결이다.
처음start = 0, end = 0, total = 0으로 시작하면 구간의 길이는end - start = 0, 즉 아무 원소도 포함하지 않은 텅 빈 창문 상태가 되어 수학적으로 완벽히 들어맞는다. 이때end포인터는 "다음에 더해야 할 새로운 원소의 인덱스"라는 아주 명확한 역할을 갖게 된다.
반면 시작부터A[0]을 미리 더해버리면,end가 '이미 더해진 값'을 가리키게 되어 변수의 역할이 오염된다. 이를 막기 위해end = 1부터 시작하게 억지로 끼워 맞추다 보면 온갖 엣지 케이스에서 누더기 코드가 탄생한다.
결론적으로 total = 0, start = 0, end = 0으로 시작하는 것은 불필요한 연산 낭비가 아니었다. 어떤 형태의 배열(빈 배열, 길이 1짜리 배열)이 들어와도 에러 없이 수학적 구간 [start, end)를 완벽하게 유지하기 위해 기꺼이 지불하는 가장 값싸고 확실한 보험료였다.
