[백준] 1806 : 부분합 (파이썬)

투포인터, 누적합 문제

https://www.acmicpc.net/problem/1806

---

투포인터 알고리즘

 

1. 개념

투 포인터 알고리즘(Two Pointer Algorithm)은 배열이나 리스트와 같은 선형 자료 구조에서 두 개의 포인터를 사용하여 문제를 해결하는 기법이다. 이 알고리즘은 주로 다음과 같은 문제를 해결하는 데 사용된다.

• 부분 배열 또는 부분 수열에서 특정 조건을 만족하는 경우 찾기
• 두 배열에서의 교집합 구하기
• 정렬된 배열에서 특정 합을 가지는 쌍 찾기

 

투 포인터 알고리즘의 기본 아이디어는 다음과 같다.

두 개의 포인터를 사용하여 배열의 시작 부분과 끝 부분, 또는 특정 지점에서 시작하여 원하는 조건을 만족할 때까지 이동한다.
포인터를 이동시키면서 조건을 체크하고, 조건에 맞는 경우를 찾으면 결과를 갱신힌다.

 

2. 핵심

 

정답을 찾기 위해 봐야하는것들 중에서 꼭 봐야 하는 부분만 추리는게 핵심이다.

• 화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법
  • 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동
  • 2개의 포인터가 양 끝에서 서로를 향해 이동
• 관찰을 통해서 문제에 등장하는 변수 2개의 값을 두 포인터로 표현하는 경우

 

3. 꿀팁 키워드

• 1차원 배열에서의 “연속 부분 수열” 또는 “순서를 지키며 차례대로”
• 곱의 최소

---

💡 풀이코드 (성공)

import sys 
n, m = map(int, sys.stdin.readline().split())
arr = [0]
arr += list(map(int, sys.stdin.readline().split()))

def sol(n, m, arr):
    partSum = [0] * (n + 1)

    for i in range(1, n + 1):
        partSum[i] = partSum[i-1] + arr[i]

    arr.sort() # 부분합 구하고 정렬하도록 변경 

    start = end = 0
    ans = sys.maxsize

    while start <= end and end <= n:
        if (partSum[end] - partSum[start]) < m:
            end += 1
        else: 
            ans = min(ans, (end - start))
            start += 1 
    if ans == sys.maxsize:
        print(0)
    else:
        print(ans)
sol(n, m, arr)

 

0. 시간복잡도 = O(nlogn)

정렬하는 코드 때문에 O(nlogn)이다.

 

1. 누적합 구하기

 

문제를 해결하기 위해서는 수열의 부분합을 구하고, 그 합이 S 이상인지 비교하는 반복적인 작업이 필요하다. 

따라서 매번 부분수열의 합을 일일이 더하는 불필요한 반복 연산을 피하기 위해, 누적합 배열(partSum)을 만들어 활용하였다.

 

배열     : 5 1 3 5 10 7 4 9 2 8
누적합 : 5 6 9 14 24 31 35 44 46 54

 

partSum = [0] * (n + 1)

for i in range(1, n + 1):
    partSum[i] = partSum[i-1] + arr[i]

 

2. 투포인터 알고리즘

 

1) 변수 초기화

start = end = 0
ans = sys.maxsize

 

2) 메인 로직

• 부분합이 m보다 작다면 end(끝 포인터)를 1 증가한다.
  • 부분수열의 합이 m보다 작으므로 부분수열의 길이를 1 증가시켜준다.
• 부분합이 m 이상이라면 start(시작 포인터)를 1 증가한다.
  • 부분수열의 합의 조건을 만족한 경우이다. 가장 짧은 부분수열의 길이를 구하기 위해 ans에 기록된 값과 비교 후 업데이트를 수행한다.
  • while문의 조건을 만족할 때까지 다음 비교를 수행하여 합이 m 이상인 가장 짧은 부분수열을 구하기 위해 start를 1 증가시켜준다.
• 합이 m 이상인 부분수열을 찾지 못했다면 0을 출력한다. 

while start <= end and end <= n:
    if (partSum[end] - partSum[start]) < m: # 부분합이 m보다 작다면
        end += 1
    else: # 부분합이 m 이상이라면 
        ans = min(ans, (end - start))
        start += 1 
if ans == sys.maxsize:
    print(0)
else:
    print(ans)

 

 

3. 디버깅

누적합 배열(partSum)을 구하기도 전에 배열 정렬하는 코드를 넣었더니 오답이 나왔었다.

따라서, 누적합을 구한 후 arr 배열을 정렬하도록 위치를 바꿔주었더니 정답을 맞췄다. 

좀 더 생각을 해보니 배열 정렬 할 필요가 없었으므로 해당 코드를 제거해주었다. (역시 정답이었다.)

 

이전 코드
10 18 5  1 3 5 10 7 4 9 2 8
정답 : 3
출력 : 2 

arr.sort() # 부분합 구하고 정렬하도록 변경