알고리즘 :: 투포인터 예제 백준 1806 파이썬

투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 특정 조건을 만족하는 부분 배열이나 부분 집합을 찾기 위해 두 개의 포인터를 사용하는 기법입니다. 이 기법은 주로 배열을 효율적으로 탐색하면서 O(N^2) 이상의 시간 복잡도를 O(N)으로 줄일 때 사용됩니다.

투 포인터 기법의 기본 원리

1. 포인터 초기화:
   • 배열의 시작 위치에 두 개의 포인터를 설정합니다. 일반적으로 하나는 start 포인터, 다른 하나는 end 포인터입니다.
2. 포인터 이동:
   • 조건을 만족할 때까지 두 포인터를 이동시킵니다.
   • 각 포인터의 이동은 문제의 조건에 따라 다릅니다. 예를 들어, 부분합이 일정 값을 넘는 경우 start 포인터를 이동시키고, 그렇지 않으면 end 포인터를 이동시킵니다.
3. 조건 만족 확인:
   • 두 포인터가 가리키는 구간이나 값이 문제의 조건을 만족하는지 확인합니다.
   • 조건을 만족하면 필요한 계산을 수행하거나 결과를 갱신합니다.
4. 종료 조건:
   • 일반적으로 end 포인터가 배열의 끝에 도달하면 반복을 종료합니다.

투 포인터 기법의 예제: 부분합이 특정 값 이상이 되는 가장 짧은 부분 배열의 길이 찾기

문제 설명

• 주어진 배열에서 연속된 수들의 부분합 중 특정 값 이상이 되는 가장 짧은 부분 배열의 길이를 구합니다.

알고리즘 단계

1. 포인터 초기화:
   • start와 end 포인터를 배열의 시작 위치인 0으로 초기화합니다.
   • current_sum을 0으로 초기화하여 현재 부분합을 추적합니다.
   • min_length를 무한대로 초기화하여 최소 부분 배열의 길이를 추적합니다.
2. 포인터 이동 및 부분합 계산:
   • end 포인터를 오른쪽으로 이동시키며 current_sum에 현재 end가 가리키는 값을 더합니다.
   • current_sum이 특정 값 S 이상이 되면 start 포인터를 오른쪽으로 이동시키며 current_sum에서 start가 가리키는 값을 뺍니다.
   • 이 과정에서 부분합이 S 이상인 경우의 길이를 계산하여 min_length를 갱신합니다.
3. 결과 반환:
   • 반복이 종료된 후 min_length가 갱신되지 않았다면 조건을 만족하는 부분 배열이 없다는 의미이므로 0을 반환합니다.
   • 그렇지 않으면 min_length를 반환합니다.

예제 코드

import sys

def min_subarray_length(N, S, arr):
    start = 0
    end = 0
    current_sum = 0
    min_length = sys.maxsize

    while True:
        if current_sum >= S:
            # start를 이동하고, sum = 0 , end = start로 초기화할 수도 있지만
            # 어차피 S보다 작은 값이므로 한번 더 연산을 수행하지 않고 start만 이동하여 계산함
            min_length = min(min_length, end - start)
            current_sum -= arr[start]
            start += 1
        elif end == N:
            break
        else:
            current_sum += arr[end]
            end += 1

    return 0 if min_length == sys.maxsize else min_length

# 입력
N, S = map(int, input().split())
arr = list(map(int, input().split()))

# 결과 출력
print(min_subarray_length(N, S, arr))

코드 설명

1. 입력 받기:
   • N과 S를 입력받고, 수열을 arr에 저장합니다.
2. 함수 정의:
   • min_subarray_length 함수에서 투 포인터 기법을 사용하여 부분합이 S 이상이 되는 가장 짧은 부분 배열의 길이를 찾습니다.
3. 투 포인터 초기화:
   • start와 end를 0으로 초기화하고, current_sum을 0으로 설정합니다.
   • min_length를 무한대로 설정합니다.
4. 포인터 이동 및 부분합 계산:
   • end를 증가시키며 current_sum에 arr[end]를 더합니다.
   • current_sum이 S 이상이 되는 동안 start를 증가시키며 부분합을 줄이고, 부분 배열의 길이를 계산하여 min_length를 갱신합니다.
5. 결과 반환:
   • min_length가 갱신되지 않았다면 0을 반환하고, 그렇지 않으면 min_length를 반환합니다.

이 코드는 투 포인터 기법을 사용하여 각 요소를 한 번씩만 처리하므로 시간 복잡도는 O(N)입니다.