파이썬 - 투 포인터(two pointers)

목차

-시작

-문제 1 : 가장 비효율 적인 코드부터 효율적인 코드까지

-실전 문제 : 카카오 보석 쇼핑 문제 풀기

 

시작

이번 시간에는 투 포인터 알고리즘에 대해 알아보겠습니다.

투 포인터 알고리즘은 리스트에서 연속된 구간을 처리하는 데 사용합니다.

투 포인터 알고리즘의 경우 예제 보면 쉽게 이해할 수 있습니다.

바로 예제로 들어가 봅시다.

 

문제 1번 : 가장 비효율 적인 코드부터 효율적인 코드까지

길이가 N이고 자연수로 구성된 리스트 a와 정수 target이 인풋으로 주어집니다.

sum(a [i:j+1]) == target인 i , j 중 j-i가 가장 작은 값을 리턴하여라.

리턴 형식은 [i, j]처럼 리스트로 하면 된다.

가장 작은 값이 여러 개 존재한다면 i가 작은 값을 리턴하면 됩니다.

 

(단 N은 100,000 이하이다)

 

예제

[1, 2, 4, 4, 2, 2, 2, 2, 1, 1, 8, ,8 ,8 ], target = 10

리턴 --> [1,3]

 

가장 먼저 떠오르는 방법

머리가 시키는 대로가 아닌 몸이 시키는 대로 의사 코드를 작성해 봅시다.

 

1. for i in range(len(a))를 이용하여 인풋 리스트 a를 순회한다.

2. for j in range(i, len(a))를 이용하여 i순회 중 i부터 a끝까지 다시 순회한다.

3. result = sum(a [i:j+1])을 이용하여 합을 구해본다.

4. 만약 result == 10이면 [i, j]를 저장한고 j loop를 빠져나온다.

5...........

이런 식으로 진행이 됩니다.

 

위 의사 코드의 문제점을 찾아봅시다.

1번과 2번에서 O(1+2+...+n) = O(n**2)이 사용됩니다.

3번에서 리스트의 슬라이싱 기능을 이용할 때 O(k)가 사용되고,

sum() 함수에서 O(k)가 사용되어 O(k**2)이 사용됩니다.

그러면 이게..

O(n**2 * k**2)으로 말도 안 됩니다.

 

이중 for loop부분을 투 포인터를 이용하여 O(n)으로 만들기

자 여기서 2중 for loop인 1번 2번을 효율적으로 변경 가능합니다.

투 포인터를 이용하면 됩니다.

투 포인터는 start, end를 지정하고 loop를 도는 알고리즘입니다.

loop를 돌 때마다 start와 end 중 1개만 더하기 1이 됩니다.

 

그럼 투 포인터로 작성한 의사 코드를 봐봅시다.

 

1. 시작(s) 끝점(e)을 0으로 초기화한다.

2. sum(a [i:j+1])이 target과 같으면 답 제출에 대한 코드로 넘긴다.

3. sum(a [i:j+1])이 target보다 작거나 같으면 e += 1

4. sum(a [i:j+1])이 target보다 크면 s += 1

 

자 이 의사 코드에 대해 그림을 그려가며 확인해 봅시다.

(각자 종이에 그리며 확인해 봅시다. 나중에 복습 1번 덜해도 되는 효과가 있습니다.)

손이 아프니 앞의 4번 인덱스까지만 잘라서 해봅시다.

note 그림을 그리신 분들은 e가 마지막 index에 도달했을때 이상한 것을  발견 하셧을 것입니다. 구현할때 염두해 두었다가 처리하면 됩니다.

그럼 시간 복잡도는 몇일까요?

loop에서 O(2*n) = O(n)입니다.

한번 loop를 돌 때마다 s 또는 e가 1씩 증가하고

s와 e가 n까지 진행해야 하기 때문입니다.

그리고 sum(a [i:j+1]에서 O(k**2)이 사용됩니다.

결국 위 의사 코드의 시간 복잡도는 O(n*k**2)입니다.

 

sum(a [i:j+1] ) 부분을 O(1)로 줄이기.

리스트의 슬라이씽은 리스트를 복사해 오는 개념이라

복사해 오는 리스트의 길이만큼의 시간 복잡도가 소모됩니다.

iterable에 사용되는 sum() 함수 역시 길이만큼의 시간 복잡도가 소모됩니다.

결국 sum(a [i:j+1]은 O(k**2)의 시간 복잡도가 사용됩니다.

이 말은 왠 만하면 sum(a [i:j+1])은 사용되면 안 된다는 뜻입니다.

 

그럼 저 부분을 처리하는 방법을 봅시다.

아이디어는 loop마다 복사해서 사용하는 것이 아니라.

loop밖에서 관리하는 하는 방법입니다.

 

1. 시작(s) 끝점(e)을 0으로 초기화한다. 

    sub_sum = a [0]으로 초기화한다.

2. sub_sum이 target과 같으면 답 제출에 대한 코드로 넘긴다.

3. sub_sum이 target보다 작거나 같으면 e += 1, sum_sum += a [e]

4. sub_sum이 target보다 크면 s += 1, sum_sum -= a [s-1]

 

sum(a [i:j+1] ) 부분을 중앙으로 관리하는 식으로 변경하니.

O(k**2)에서 O(1)으로 변경된 것을 확인할 수 있습니다.

 

이제 구현하면 된다!

마지막에 작성한 의사 코드는 아래와 같습니다.

 

1. 시작(s) 끝점(e)을 0으로 초기화한다.

    sub_sum = a [0]으로 초기화한다.

2. sub_sum이 target과 같으면 답 제출에 대한 코드로 넘긴다.

3. sub_sum이 target보다 작거나 같으면 e += 1, sum_sum += a [e]

4. sub_sum이 target보다 크면 s += 1, sum_sum -= a [s-1]

 

이 의사 코드의 시간 복잡도는 O(N)으로 문제에서 주어진 N = 100,000 조건에서도 

충분히 정답 판정을 받을 수 있을 것 같습니다.

 

그럼 이제 구현해 봅시다.

def solution(a, target):
    e = 0
    sub_sum = a[0]
    answer = [[0, len(a)]]
    for s in range(len(a)):

        while True:
            if sub_sum >= target or e >= len(a) -1: break
            e += 1
            sub_sum += a[e]
        if sub_sum == target and answer[0][1]-answer[0][0] > e-s:
            answer[0] = [s, e]
        sub_sum -= a[s]
    return answer[0]

solution([1, 2, 4, 4, 2, 2, 2, 2, 1, 1, 8 ,8 ,8 ], 10)
            
            
---> 출력결과
[1, 3]

구현법은 대략 이렇습니다.

일단 s를 증가시키는 loop를 만듭니다.

그리고 s내에서 e를 증가시킬 수 있는 만큼 최대로 증가시킵니다.

note 투 포인터 구현은 제일 처음에 생각한 2중 for loop와 비슷해 보이지만. while loop안에서 e를 사용한 다는 점에서 차이가 있다. 결국 시간 복잡도는 O(n)로 2중 for loop와 명확히 다르다.

실전 문제 : 카카오 보석 쇼핑 문제 풀기

답을 보기 전에 문제를 풀어보는 것을 추천드립니다.

https://programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

문제

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾는 문제이다.

(정확한 문제 내용은 위의 링크에서 꼭 읽어 보자)

 

문제를 보면

"아 리스트에서 연속된 부분 찾아서 장난질 치는 거네?"

"그러면 투 포인터로 풀면 되겠다."

"인풋 리스트의 길이가 100,000이니 O(nlogn) 정도의 시간 복잡도로 만들면 되겠군"

이런 생각을 해야 합니다.

 

문제를 읽고 위와 같은 생각이 아니 였다면. 아래의 사이트로 접속해 문제들을 풀면서 감을 익혀야 합니다.

그리고 다시 트라이합시다.

https://www.acmicpc.net/problemset?sort=ac_desc&algo=80

 

생각이 들었다면 의사 코드로 넘어갑시다.

1. e = 0으로 초기화한다.

  중앙에서 관리할 sub_arr를 dictionary 자료구조를 이용한다.

2. for s in range()를 순회한다.

3. while loop를 순회한다.

   s에 대해 e를 최대한 진행할 수 있을 때까지 진행시킨다.

   sub_arr에 gems [e] 성분을 추가한다.

   만약 sub_arr이 모든 보석을 포함하고 있다면 answer리스트에 추가하고 탈출한다.

   만약 e가 len(gems) -1보다 크면 탈출한다.

   

4. sub_arr에 gems [s]를 제거하고 다음다음 s에 대해 진행한다.

 

구현 : 파이썬 이해도 부족으로 인한 나쁜 사례

def solution(gems):
    e = 0
    sub_arr = { gem : 0 for gem in gems}
    answer = [[0,len(gems)]]
    for s in range(len(gems)):
        print(s,e,gems[s:e+1])
        while True:
            if 0 not in sub_arr.values(): 
                if answer[0][1]-answer[0][0] > e - s:
                    answer[0] = [s, e]
                break
            if e > len(gems) - 1: break
            sub_arr[gems[e]] += 1
            e += 1
        print(sub_arr)
        sub_arr[gems[s]] -= 1
            
    return [answer[0][0] , answer[0][1]]
solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"])

0 not in sub_arr.values()에서 O(k)의 시간 복잡도를 가져 위의 경우 실패합니다.

sub_arr.values()는 dictionary의 value를 generator로 가져오는 dictionary의 메서드로 O(1)의 시간 복잡도를 가집니다.

하지만 0이 generator sub_arr.values()에 있는지 확인하는데 O(n)이 소모됩니다.

note 0 not in dictionary은 O(1)입니다. 하지만 0 not in dictionary.values()은 O(n)입니다.

이와 비슷한 예로 파이썬의 대표적인 generator인 range()에 대해 실험해 봅시다.

range()는 반복 가능하여 for loop에 사용되지만.

리스트와 달리 실제 값이 저장되는 게 아니라 필요할 때 데이터를 생성하여 사용합니다.

range(11)을 생성하는데 O(1) 시간 복잡도가 사용됩니다.

7이 range(11)에 있는지 확인하는데 O(n)의 시간 복잡도를 가집니다.

이 이유는 0부터 10까지 생성하고 그중에 7이 있는지 확인을 해야 하기 때문입니다.

 

 

구현 : 0 not in sub_arr.values()을 수정하여 O(1)으로 만들기

def solution(gems):
    l = len(set(gems))
    e = 0
    sub_arr = {}
    answer = [[0,len(gems)]]
    
    for s in range(len(gems)):
        while True:
            if l == len(sub_arr): 
                if answer[0][1]-answer[0][0] > e - s:
                    answer[0] = [s, e]
                break
            if e > len(gems) - 1: break
            sub_arr.setdefault(gems[e], 0)
            sub_arr[gems[e]] += 1
            #마지막에 더하기 1이 되어서 정답에 +1 안해도 됨
            e += 1
            
        if sub_arr[gems[s]] == 1:
            sub_arr.pop(gems[s])
        else: 
            sub_arr[gems[s]] -= 1
            
    #마지막 앞에 더하는 이유는 s가 0부터 시작해서 그럼
    #e는 while에서 마지막에 +1해서 더 할 필요없음
    return [answer[0][0]+1 , answer[0][1]]

파이썬에서 len()은 O(1)의 시간 복잡도를 가집니다.

그래서 len()을 사용하여 처리할 수 있는 코드로 변경하였고 정답 판정을 받았습니다.

len()을 사용하기 위해 중간에 여러 코드가 추가되었지만

시간 복잡도를 계산해 보면 O(n)인 것을 확인할 수 있습니다.