728x90
반응형
백준 2003번 수들의 합2 (투포인터)
1. 문제
백준 2003번 '수들의 합 2' 문제를 풀면서 투 포인터를 제대로 활용하는 방법에 대해 고민했다. 처음에는 단순하게 sum() 함수를 이용했지만, 효율적인 풀이를 위해 투 포인터를 활용하는 방식으로 최적화할 수 있었다. 이 글에서는 두 가지 풀이를 비교하고, 왜 투 포인터를 제대로 사용하는 것이 중요한지 정리해보겠다.
문제링크
https://www.acmicpc.net/problem/2003
문제 분석
N개의 수로 이루어진 수열이 주어질 때, 연속된 부분 수열의 합이 M이 되는 경우의 수를 구하는 문제이다.
🔹 입력 조건
N (1 ≤ N ≤ 10,000),M (1 ≤ M ≤ 300,000,000)- 수열의 원소는
30,000을 넘지 않는 자연수
🔹 출력 조건
- 합이
M이 되는 경우의 수를 출력한다.
2. 풀이
sol1) 비효율적인 풀이 (O(N²))
처음에는 단순히 모든 부분합을 직접 계산하는 방식으로 접근했다. s와 e 두 개의 포인터를 두고, sum(nums[s:e+1])을 이용해서 합을 확인했다.
❌ 비효율적인 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nums = list(map(int, input().split()))
s, e, cnt = 0, 0, 0
while s < n and e < n:
temp = sum(nums[s:e+1]) # 부분합을 직접 계산
if temp == m:
cnt += 1
e += 1
elif temp > m:
s += 1
elif temp < m:
e += 1
print(cnt)❗ 문제점
sum(nums[s:e+1])를 반복적으로 호출하면서 O(N) 연산이 발생한다.- 최악의 경우 O(N²) (약 10⁸번 연산)가 되므로 시간 초과 가능성이 있다.
sol2) 최적화된 투 포인터 풀이 (O(N))
투 포인터를 제대로 활용하면, 매번 sum()을 호출하지 않고 현재 부분합을 변수로 저장하면서 업데이트할 수 있다. 이렇게 하면 O(N)만에 해결 가능하다.
✅ 효율적인 코드 (투 포인터 + 슬라이딩 윈도우)
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nums = list(map(int, input().split()))
s, e, cnt, temp = 0, 0, 0, 0 # temp: 현재 부분합
while e < n:
temp += nums[e] # e번째 값을 추가
e += 1 # e를 늘려가며 확장
# 현재 부분합이 M보다 크면 s를 이동시켜 줄인다
while temp > m and s < e:
temp -= nums[s] # s번째 값을 제거
s += 1 # s를 이동
# 부분합이 정확히 M이라면 카운트 증가
if temp == m:
cnt += 1
print(cnt)🔹 이 코드의 핵심 아이디어
e를 이동하면서temp(현재 부분합)를 누적한다.temp가M을 초과하면s를 이동하면서 범위를 줄인다.temp == M일 때 경우의 수를 증가시킨다.- 모든 요소를 한 번씩만 탐색하므로 O(N)에 해결할 수 있다.
3. 정리
| 방식 | 시간 복잡도 | 핵심 문제점 |
|---|---|---|
| 비효율적인 풀이 | O(N²) | sum()을 반복 호출하여 연산이 많음 |
| 투 포인터 최적화 | O(N) | 현재 부분합을 저장하여 불필요한 연산 제거 |
🚀 배운 점
- 투 포인터의 핵심은 한 번 계산한 값을 재활용하는 것!
- 매번
sum()을 호출하는 방식은 비효율적이므로 현재 합을 유지하면서 갱신하는 방식이 중요하다. - 이런 최적화 기법은 연속된 부분합을 찾는 문제에서 매우 자주 쓰이므로 익혀두면 좋다!
4. 결과
오.. 역시 투포인터 제대로 쓰는 게 확실히 빠르다..
728x90
반응형