MancityBallboy 흔적 남기기

투 포인터 알고리즘

16 Feb 2021

투 포인터 알고리즘

2개의 포인터를 옮겨 가면서 복잡도를 최소한으로 하여 문제를 해결하는 방법입니다.

대표예제

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

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

투 포인터 알고리즘을 활용하는 문제 중 두 개의 포인터가 같은 위치에서 이동하는 대표 예제 입니다.

N, target = list(map(int, input().split()))
arr = list(map(int, input().split()))

def solution(N, target, arr):
    start = 0
    end = 0

    answer = 0
    while end < N:
        if sum(arr[start: end + 1]) < target:
            end += 1
        elif sum(arr[start: end + 1]) > target:
            start += 1
        else:
            answer += 1
            end += 1
    return answer

start와 end사이를 하나의 부분집합이라고 봤을때 그 부분집합의 합과 target 값을 비교하여서 target 값보다 작으면 end++ 하고 크면 start ++ 하는 방식으로 해서 end의 값이 배열의 인덱스를 벗어나면 종료하는 방식의 알고리즘 입니다.

이와 같은 방식의 투 포인터 알고리즘이 가능한 이유는 일단 모든 원소가 자연수이기 때문에 가능하다고 할 수 있습니다.

https://leetcode.com/problems/container-with-most-water/

Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

img

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

이 문제는 같은 index에서 출발하는 투 포인터가 아닌 양 끝에서 출발하는 투 포인터의 대표 예제 입니다.

def maxArea(self, height):
    start = 0
    end = len(height) - 1
    answer = 0
    while end - start > 0:
        answer = max(answer, height[end] * (end - start) if height[start] > height[end] else height[start] * (end - start))
        if end - start == 1:
            break
        if height[start] == height[end]:
            if height[end - 1] < height[start + 1]:
                start += 1
            else:
                end -= 1
        elif height[start] > height[end]:
            end -= 1
        else:
            start += 1
    return answer

양 끝을 기준으로 start와 end를 설정하고 한 칸씩 움직여 가면서 최대값이 될 수 있는 값을 갱신해 나가면서 최대로 담을 수 있는 물의 양을 구하는 것입니다.

이 문제에서 가장 중요하게 생각해야할 부분은 어떠한 기준으로 start와 end를 움직일 것인가라고 생각합니다.

  1. start와 end 중에 낮은 벽에 의해 물의 양이 정해진다는 것
  2. 두 벽중에 높은 벽을 계속 해서 유지해야 가장 높은 효율을 낼 수 있을 것

이 2가지 를 기준으로 생각해봤을때 start와 end를 움직이는 기준은 더 낮은 벽을 바꾸는 식으로 진행 하면 된다는 것을 알 수 있습니다.

투 포인터 알고리즘 원리 자체는 어렵지 않기 때문에 원리에 대한 이론 보다는 예제를 통해 알아 보았습니다.

Related posts