플레찍었으니 정리해보는 알고리즘 노트 2 - 중간에서 만나기, 투 포인터

투 포인터 알고리즘은 말 그대로 포인터 두 개를 이용해 문제를 해결하는 알고리즘을 말한다.

특정한 조건을 만족하는 배열의 연속된 부분합을 O(N)의 시간 안에 구해야 할 때 사용된다.

조건으로는 주로 더해서 특정한 수가 되는 부분합 찾기 등이 있다.

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

1806번: 부분합

이 문제의 조건은 주어진 수열에서 일정한 수 이상의 연속된 부분합 중 가장 짧은 것의 길이를 구하는 것이었다.

 

일반적인 투 포인터 알고리즘은 다음과 같이 작동한다.

포인터 두 개를 p1,p2라고 할 때

1. p1,p2를 모두 배열의 첫번째 인덱스를 가리키게 한다(p1 = 0, p2 = 0)

2. p1과 p2사이의 배열의 부분합을 구하고 조건에 맞는지 확인한다.

3. 조건을 충족시키지 못한다면 p2를 한칸 오른쪽으로 옮긴다(p2 += 1)

4. 조건을 충족시키면 모두 오른쪽으로 한칸씩 옮긴다 (p1 += 1, p2 +=1)

5. p2가 배열의 크기보다 커지기 전까지 2-5를 반복한다.

 

하지만 이 문제에선 일정 수 이상인 부분합의 길이 중 가장 짧은 것을 찾아야 하기 때문에 조건을 충족할 때 P1과 P2를 모두 이동시켜선 안된다.

(배열의 숫자 하나로도 일정 수 보다 클 수 있기 때문에 조건을 충족할때 배열의 길이를 줄여나가는 식으로 찾아야만 한다)

n,m = map(int,input().split())
lst = list(map(int,input().split()))

ans = 1000001
p1 = 0
p2 = 0
sumlst = lst[0]

while p1 <= p2:
    if sumlst >= m: #구간합이 m 이상일때
        if p2 - p1 +1 <ans:
            ans = p2 - p1 + 1
        sumlst -= lst[p1] #p1 1 증가
        p1 += 1
    else: #구간합이 m보다 작을때
        p2 += 1 #p2 1 증가
        if p2 >= n:
            break
        sumlst += lst[p2]
        
if ans == 1000001:
    print(0)
else:
    print(ans)

따라서 일반적인 투 포인터 알고리즘에서 조건 충족시에 p1만 증가하도록 바꾸고 반복문의 조건에 p1이 p2 보다 작을 때를 추가해주면 된다.

 

중간에서 만나기(meet in the middle) 알고리즘은 특정한 조건을 만족하는 조합(부분수열)을 구할때 배열을 두 부분으로 나누어 시간 복잡도를 줄이는 알고리즘이다.
https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

이 문제는 정수로 된 수열에서 부분수열의 합이 특정한 수 s가 되도록 하는 부분수열의 개수를 찾는 것이 목표이다.

모든 부분수열을 만들고 그 합을 확인해보면 풀 수 있지만 이러한 풀이의 시간 복잡도는 O(2^^n)이 되어 시간초과가 발생한다.

이때 주어진수열을 두개로 나눠 각각의 부분수열을 만든 후 합쳐본다면 시간 복잡도는 O(2^^n / 2)이 되어 문제를 풀 수 있게 된다.

n,s = map(int,input().split())
lst = list(map(int,input().split()))
center = n//2
lst1 = lst[:center] #1번째 배열
lst2 = lst[center:] #2번째 배열

dplst1 = []
dplst2 = []

def dfs1(start,count,last): # 첫번째 배열로 부분수열 만들기
    if start == last:
        dplst1.append(count)
    else:
        dfs1(start+1,count+lst1[start],last)
        dfs1(start+1,count,last)
        
def dfs2(start,count,last): # 두번째 배열로 부분수열 만들기
    if start == last:
        dplst2.append(count)
    else:
        dfs2(start+1,count+lst2[start],last)
        dfs2(start+1,count,last)
    
dfs1(0,0,center)
dfs2(0,0,n-center)
dplst1.sort()
dplst2.sort()

def lower_bound(nums, target):
    
    left, right = 0, len(nums)
    
    while left < right:  #left와 right가 만나는 지점이 target값 이상이 처음 나오는 위치
        mid = left + (right - left) // 2
        
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return right

def upper_bound(nums, target):

    left, right = 0, len(nums)

    while left < right:  #left와 right가 만나는 지점이 target값 보다 큰 값이 처음 나오는 위치
        mid = left + (right - left) // 2

        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid 

    return right

ans = 0
for i in dplst1:
    ans += upper_bound(dplst2,s-i) - lower_bound(dplst2,s-i)
    
# print(dplst1)
# print(dplst2)
if s == 0:
    print(ans - 1)
else:
    print(ans)

부분수열을 만드는 과정은 dfs를 이용하면 쉽게 구현할 수 있다.

부분수열을 만든 후 첫번째 부분수열 배열에서 고른 수와 두번째 부분수열 배열에서 고른 수의 합이 s가 되는 조합의 수를 찾으면 된다.

두 부분수열 배열을 정렬한 후 첫번째 부분수열 배열을 반복문을 이용해서 모두 탐색하면서

합이 s가 되는 수가 두번째 배열에 있는지 이진탐색을 이용해서 찾아보면 빠르게 구할 수 있다.