파이썬에서는 일렬로 늘어서 있는 형태인 선형 배열(Linear Array)로 리스트를 주로 사용하는데, 이 리스트를 순차적으로 두 개의 지점(index)을 이용하여 해결해 나가는 방법을 투 포인터 알고리즘이라고 한다. 명확하게 같은 알고리즘은 아니지만 활용 방법이 이진 탐색이나 슬라이딩 윈도우 알고리즘에도 같이 사용된다. 투 포인터 알고리즘의 포함 관계는 아니지만 활용 방법의 차이일 뿐 투 포인터를 활용하여 문제를 해결하기에 같이 살펴보며 차이점도 같이 보도록 하겠다.

1. 이진 탐색

이진 탐색은 주어진 배열의 크기를 1/2씩 범위를 좁혀가며 문제를 해결한다. 이 때 포인터의 위치는 처음과 끝에 위치하여 이 둘의 중앙을 기준으로 탐색하는 수가 큰지 작은지 판별하여 위치를 재조정해간다. 이진 탐색 시 '반드시' 정렬이 되어 있어야 한다. 문제를 보자.

문제:
길이가 n(2 < n <= 100)인 숫자카드가 정렬되어 있을 때 원하는 카드(m)를 찾는 프로그램을 작성하라.
n = [2, 3, 5, 7, 8, 12, 14, 19, 20, 25, 33, 47, 59, 68, 99, 101, 152, 228]
m = 99

풀이:
주어진 자료의 처음과 끝의 인덱스를 시작점과 끝점으로 두 개의 포인트 설정한다. '(시작점 인덱스 + 끝점 인덱스) // 2'를 중간으로 설정하여 찾으려는 숫자카드가 중간을 중심으로 작은 수인지 큰 수인지 판단하여 '중간 > 찾으려는 카드'면 중간보다 큰 범위는 당연히 찾으려는 카드보다 큰 카드이기에 탐색 범위에서 재외시키고 중간 지점의 앞 인덱스를 끝 점으로 재설정하고 중간도 재설정하여 탐색 범위를 좁혀나가는 방식이다.
m = 99 를 이분 탐색으로 재설정하면서 범위를 좁혀나가보자.
진행순서는
1. [2, 3, 5, 7, 8, 12, 14, 19, 20, 25, 33, 47, 59, 68, 99, 101, 152, 228] : 중앙은 '20'이므로 m 보다 작기에 20보다 작은 범위는 재외시킨 후 시작점으로 중앙 지점에서 +1 하여 재설정한다.
2. [25, 33, 47, 59, 68, 99, 101, 152, 228] : '68' 역시 m 보다 작기에 68 이하의 범위를 재외시킨 후 반복한다.
3. [99, 101, 152, 228] : '101'은 m보다 크기에 101 이상의 범위는 재외시킨 후 반복한다.
4. [99] : 정답
이런식으로 반복하며 찾으려는 카드가 작은지 큰지를 확인하여 전체 탐색지역을 반씩 줄여나가기에 처음부터 하나씩 모두 탐색하는 선형탐색보다 매우 빠른 탐색(로그 선형 시간-Big-O:O(logN))이 가능하다. 이처럼 큰지 작은지를 확인해야 하기에 반드시 정렬이 되어있어야 하니 주의해야 한다.

n = [2, 3, 5, 7, 8, 12, 14, 19, 20, 25, 33, 47, 59, 68, 99, 101, 152, 228]
m = 99
st = 0 # 시작지점 인덱스
en = len(n) - 1 #끝지점 인덱스
#while문 사용
while st <= en:
    mid = (st + en) // 2 # 시작과 끝지점의 중간 인덱스
    if n[mid] == m:
        print(m)
        break
    else:
        if n[mid] < m:
            st = mid + 1
        else:
            en = mid - 1
# for문 사용(이 경우는 while문이 더 적합하다)
for i in range(len(n)):
    mid = (st + en) // 2
    if n[mid] == m:
        print(m)
        break
    else:
        if n[mid] < m:
            st = mid + 1
        else:
            en = mid - 1

2. 슬라이딩 윈도우(Sliding Window)

알고리즘 재목과 같이 창문을 옆으로 밀듯이 일정 범위를 움직이며 탐색하여 문제를 해결하는 알고리즘 방법이다. 문제를 풀어보면 이해가 더 빠를 것이다.

문제:
빵집을 운영하는 용배는 매출이 가장 적은 날을 쉬는 날로 정하기 위해 일주일 동안 쉬지 않고 일을하며 매상을 매일 적었다. 그래서 3일 연속으로 매출이 가장 적은 3일을 쉬려고 한다. 가장 적은 매출은 얼마인지 반환하는 프로그램을 작성하시오.
입력 매출 :54, 77, 48, 92, 42, 84, 64

풀이:
첫날부터 3일씩 매출을 모두 살펴보며 그 중 매출이 가장 적었던 3일을 찾으면 된다. 슬라이딩 윈도우는 다음과 같이 움직이며 찾는다.
1. [[54, 77, 48], 92, 42, 84, 64] 첫 3일
2. [54, [77, 48, 92], 42, 84, 64] 1일째 되는 날의 매출은 빼고 4일째 되는 매출을 더한다
3. [54, 77, [48, 92, 42], 84, 64] 2일째 되는 날의 매출은 빼고 5일째 되는 매출을 더한다
4. [54, 77, 48, [92, 42, 84], 64] 3일째 되는 날의 매출은 빼고 6일째 되는 매출을 더한다
5. [54, 77, 48, 92, [42, 84, 64]] 4일째 되는 날의 매출은 빼고 7일째 되는 매출을 더한다
이렇게 일정한 크기의 창문이 옆으로 움직이듯이, 범위를 설정하여 3일씩 옆으로 이동하며 찾은 3일간의 더한 모든 매출 중 가장 낮은 매출을 반환하면 된다.

#1 투 포인터 활용
sales = [54, 77, 48, 92, 42, 84, 64]
st = 0 # 3일간 매출 중 첫 인덱스
en = 2 # 3일간 매출 중 끝 인덱스
sum_p = 1e9# 작은 값을 찾는 문제이므로 상대적으로 무한인 값을 설정.
while en < 7: #4번의 이동 중 가장 작은 값을 찾는다.
    sum_p = min(sum_p, sum(sales[st:en + 1]))#인덱스의 시작과 끝을 3칸으로 설정한 것을 슬라이싱 해서 더한 후 작은 값을 계속 업데이트한다.
    st += 1
    en += 1
print(sum_p)
출력:
179
--------------다른 풀이 #2 while문 사용
sum_p = sum(sales[:3])# 3일 동안의 매출을 더한 값을 시작으로
min_p = sum_p# 첫날의 매출을 가장 낮은 값으로 설정하여
k = 3
while k < 7:#첫 3일은 이미 합이 되어있으니 총 4번을 더 이동하고 종료되도록 설정한다.
    sum_p += sales[k] - sales[k - 3]# 1번째 날의 매출은 빼고 4번째 날의 매출은 더하도록 한다.
    min_p = min(sum_p, min_p)# 지금까지의 매출 중 낮은 값과 현재 한칸 옆으로 이동한 날짜의 합 중 낮은 매출을 업데이트한다.
    k += 1
print(min_p)
출력:
179
--------------다른 풀이 #3 for문 사용
sum_p = sum(sales[:3])# 3일 동안의 매출을 더한 값을 시작으로
min_p = sum_p# 첫날의 매출을 가장 낮은 값으로 설정하여
for i in range(3, len(sales)):
    sum_p += sales[i] - sales[i - 3]
    min_p = min(sum_p, min_p)
print(min_p)
출력:
179

3. 투 포인터

알고리즘 말 그대로 두 개의 포인터를 움직여가며 문제를 해결하는 방법이다. 이진 탐색은 투 포인터를 처음과 끝으로 설정하여 찾아가는 형식이고 슬라이딩 윈도우는 포인터를 일정 방향으로 이동시키며 풀 수도 있기에 방법론적으로 보았을 때 투 포인터의 활용만 잘 한다면 이와같은 형식의 문제는 해결할 수 있을 것이다. 위와 같은 투 포인터의 활용방식을 제외하고도 다른 활용을 통해 문제를 해결하는 방법도 문제를 통해서 알아보자.

문제:
길이 n(2 < n <= 100)인 문자가(소문자만 활용) 회문이면 1을 아니면 0을 반환하는 프로그램을 작성하시오.(회문 : 똑바로 읽으나 거꾸로 읽으나 같은 글귀)
문자 - dgayuguyagd

풀이:
문자가 주어지면 양 끝을 투 포인트로 설정한 후 하나씩 좁혀오면서 문자가 같으면 중간까지 계속 좁혀가고 중간에 도착하면 1을 반환, 투 포인터가 가리키는 문자가 같지 않으면 0을 반환하면 된다.

word1 = 'dgayuguyagd'
word2 = 'dgaysuguyoagd'
n = len(word1)
lt = 0 #왼쪽 인덱스
rt = n - 1 #오른쪽 인덱스
flag = 1
while lt < rt:
    if word1[lt] == word1[rt]:
        lt += 1
        rt -= 1
    else:
        flag = 0
        break
print(flag)
결과:
word1 : 1
word2 : 0

다른 풀이:

word1 = 'dgayuguyagd'
word2 = 'dgaysuguyoagd'
if word2 == word2[::-1]:
    print(1)
else:
    print(0)

word = 'apple'
for i in word:
    print(i)
출력:
a
p
p
l
e
-------------
for i in word[::-1]:
    print(i)
출력:
e
l
p
p
a

word[::-1]은 word을 끝에서부터 순차적으로 반환한다. 종종 편리하게 사용되니 알아두면 편하게 사용할 수 있을 것이다.
sort와 sorted
sort : 기존의 데이터가 정렬될 뿐 값을 반환하지 않는다. 리스트에 배열된 문자가 아닌 일반 문자('apple') 자체는 정렬하지 않는다.
sorted : 정렬한 것을 리스트로 반환하기에 변수가 선언되어야 한다. 정렬된 것은 변수에 담기고 기존의 데이터는 변환되지 않는다.

word = 'apple'
for i in word[::-1]:
    print(i)
출력:
e
l
p
p
a
-----
word = 'apple'
word_re = sorted(word, reverse=True)
for i in word_re:
    print(i)
출력:
p
p
l
e
a