알면 도움되는 코딩 테스트 유형: 11) #Two_Pointer

투 포인터의 개념

 

• 투 포인터는 배열이나 리스트에서 두 개의 포인터(인덱스)를 활용하여 원하는 결과를 얻기 위한 알고리즘입니다. 주로 정렬된 배열이나 리스트에서 합, 차, 거리 등의 연산을 수행할 때 사용됩니다.

 

코딩 테스트에서의 투 포인터 문제 접근 방법

 

• 투 포인터 문제를 해결하기 위한 접근 방법은 다음과 같습니다.

 

1. 시작점과 끝점 설정: 문제의 조건에 맞게 시작점과 끝점을 설정합니다. 일반적으로 시작점은 배열/리스트의 첫 번째 요소를 가리키고, 끝점은 마지막 요소를 가리킵니다.
2. 조건 확인 및 이동: 두 포인터 사이의 조건을 확인하고 필요에 따라 각각의 포인터를 이동시킵니다. 예를 들어, 합이나 차가 주어진 값보다 큰 경우 한쪽 포인터를 왼쪽으로 이동시켜 값을 줄여나갑니다.
3. 결과 도출: 원하는 결과가 나올 때까지 반복적으로 조건 확인 및 이동 과정을 수행합니다. 최종적으로 원하는 결과 값을 얻게 되면 해당 값을 반환하거나 필요한 작업을 수행합니다.

 

2559번: 수열

 

  문제  

 

• 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
• 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,
• 3 -2 -4 -9 0 3 7 13 8 -3
• 모든 연속적인 이틀간의 온도의 합은 아래와 같다.

• 이때, 온도의 합이 가장 큰 값은 21이다.
• 또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

• 이때, 온도의 합이 가장 큰 값은 31이다.
• 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

 

  해결 방법  

 

• 이 문제는 N일 동안의 온도가 주어졌을 때, 연속적인 K일 동안의 최대 온도 합을 구하는 문제입니다.
• 우선 입력 받은 N과 K 값을 사용하여 처음 K일간의 온도 합을 구합니다.
• 그 후 for문에서 시작점(start)와 끝점(end)을 각각 한 칸씩 이동시키며 새로운 K일간의 온도 합을 계산합니다. 이때 기존 시작점의 값을 빼고 새로운 끝점 값을 추가함으로써 시간 복잡도를 O(N)으로 줄일 수 있습니다.

N, K = map(int,input().split())
temp = list(map(int,input().split()))

start = sum(temp[:K])
max_temp = start

for i in range(K, N):
    start += temp[i] - temp[i-K]
    max_temp = max(max_temp, start)

print(max_temp)

 

 

7453번: 합이 0인 네 정수

 

  문제  

 

• 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.
• A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

  해결 방법  

 

• 이 문제는 네 개의 배열 A,B,C,D가 주어졌을 때, 각 배열에서 한 개씩 원소를 골라서 그 합이 0이 되는 경우의 수를 찾는 문제입니다.

import sys; input=sys.stdin.readline
from collections import Counter

n = int(input())
A, B, C, D = [], [], [], []

for _ in range(n):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

AB = []
CD = []

for i in range(n):
    for j in range(n):
        AB.append(A[i] + B[j])
        CD.append(C[i] + D[j])

CD = Counter(CD)
result = 0

for ab in AB:
    if -ab in CD:
        result += CD[-ab]
        
print(result)

• 이 문제는 투 포인터 알고리즘을 활용하기 전에 먼저 두 배열의 합을 모두 구한 다음, 이들 중에서 합이 0이 되는 쌍을 찾습니다. 이를 위해 우선 A와 B의 가능한 모든 쌍의 합, 그리고 C와 D의 가능한 모든 쌍의 합을 각각 리스트에 저장합니다.
• 그런 다음, Counter를 사용하여 C와 D에서 나올 수 있는 모든 합과 그 개수를 딕셔너리 형태로 저장합니다. 마지막으로 A와 B에서 나올 수 있는 모든 합에 대해, 그 값에 -1을 곱한 값이 C와 D에서 나올 수 있는 합 중 하나인 경우 해당 개수만큼 결과값에 더합니다.

 

• 투 포인터 알고리즘은 배열 내 연속적인 부분 집합에 대해 연산할 때 유용하게 사용됩니다.
• 하지만 투 포인터 알고리즘은 단순히 '두 개의 포인터를 이동시키면서 연산한다'라는 점 외에도 주어진 문제 조건을 충족하는 최적화된 해결 방법을 찾아내는 데 있어 중요한 역할을 하므로 숙지하고 있으면 좋겠습니다.