파이썬으로 방정식의 최댓값 찾기: 투 포인터 알고리즘 완벽 가이드

문제 개요

2차원 평면 위의 좌표점들을 담은 배열 points가 있다고 가정해 보겠습니다. 이 배열은 x값을 기준으로 오름차순으로 정렬되어 있으며, 각 원소는 points[i] = (x_i, y_i) 형태로 표현됩니다. 즉, 모든 1 <= i < j <= 점의 개수에 대해 x_i < x_j가 성립합니다.

여기에 추가로 하나의 정수 k가 주어졌을 때, 다음 방정식의 최댓값을 구하는 것이 목표입니다.

y_i + y_j + |x_i − x_j|

단, 이때 조건 |x_i − x_j| <= k 를 만족하는 점 쌍(1 <= i < j <= 점의 개수)만 고려해야 합니다.

예시로 이해하기

입력이 다음과 같다고 가정해 봅시다.

points = [[2,4], [3,1], [6,11], [7,-9]]
k = 1

이 경우 출력값은 6입니다. 그 이유를 살펴보겠습니다.

첫 번째 점 (2,4)와 두 번째 점 (3,1)은 |2 − 3| = 1 <= k 조건을 만족하며, 방정식에 대입하면 4 + 1 + |2 − 3| = 6이 됩니다.
세 번째 점 (6,11)과 네 번째 점 (7,-9) 역시 |6 − 7| = 1 <= k 조건을 만족하지만, 계산 결과는 11 + (-9) + |6 − 7| = 3입니다.

따라서 두 값 중 더 큰 6이 정답이 됩니다.

해결 접근 방법: 투 포인터(Two Pointer)

이 문제는 두 개의 포인터를 활용한 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

left 포인터는 후보 영역의 시작점을, right 포인터는 현재 검사 중인 점을 가리킵니다.
두 점 사이의 거리 diff = |x_r − x_l|가 k 이하이면 방정식 값을 계산하여 최댓값을 갱신합니다.
y_l >= y_r − diff 인 경우에는 right를 증가시켜 더 많은 후보를 탐색하고, 그렇지 않으면 left를 증가시켜 불필요한 범위를 제거합니다.
diff가 k를 초과하면 left를 증가시켜 거리를 줄입니다.

알고리즘 단계

left := 0, right := 1 로 초기화합니다.
max_value := 음의 무한대(-inf)로 초기화합니다.
right가 points의 크기보다 작은 동안 다음을 반복합니다.
- (xl, yl) := points[left]
- (xr, yr) := points[right]
- diff := |xr − xl|
- 만약 left == right 라면 → right를 1 증가
- 그렇지 않고 diff <= k 라면:
  - m := yl + yr + diff
  - max_value := max(max_value, m)
  - yl >= yr − diff 이면 right를 1 증가, 아니면 left를 1 증가
- 그 외의 경우(diff > k) → left를 1 증가
반복이 끝나면 max_value를 반환합니다.

파이썬 구현 코드

아래 코드를 통해 실제 구현을 확인해 보세요.

def solve(points, k):
   left, right = 0, 1
   max_value = float('-inf')

   while right < len(points):
      xl, yl = points[left]
      xr, yr = points[right]

      diff = abs(xr - xl)
      if left == right:
         right += 1
      elif diff <= k:
         m = yl + yr + diff
         max_value = max(max_value, m)
         if yl >= yr - diff:
            right += 1
         else:
            left += 1
      else:
         left += 1

   return max_value

points = [[2,4],[3,1],[6,11],[7,-9]]
k = 1
print(solve(points, k))

입력

[[2,4],[3,1],[6,11],[7,-9]], 1

출력

마무리

이 알고리즘은 각 포인터가 배열을 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 모든 점 쌍을 일일이 비교하는 브루트포스 방식(O(n²))보다 훨씬 효율적이며, 특히 데이터 크기가 클 때 그 차이가 두드러집니다. 정렬된 좌표 배열에서 조건부 최적화 문제를 만난다면 투 포인터 기법을 먼저 떠올려 보시기 바랍니다.