투 포인터 알고리즘(Two Pointers)

2024. 12. 26. 21:39· Algorithm
반응형

투 포인터(Two Pointers) 알고리즘은 정렬된 배열에서 효율적으로 특정 조건을 만족하는 값을 찾거나, 구간을 탐색하기 위해 사용되는 알고리즘입니다. 두 개의 포인터를 배열의 양 끝에 배치하거나 특정 위치에서 시작해, 이를 이동시키며 조건을 만족하는 값을 찾습니다.

 

  • 정렬된 배열에서 가장 많이 사용됩니다.
  • 두 포인터를 사용하여 한 번의 탐색으로 문제를 해결하므로 시간 복잡도는 보통 O(N)입니다.
  • 이분 탐색처럼 중간 값을 탐색하지 않고, 포인터를 이동시켜 범위를 좁혀 나가는 방식입니다.
투 포인터의 동작 원리
  1. 배열의 양 끝에서 시작하거나, 시작 지점을 설정합니다.
  2. 각 포인터의 값에 따라 조건을 확인합니다.
  3. 조건에 따라 왼쪽 포인터를 오른쪽으로 이동하거나 오른쪽 포인터를 왼쪽으로 이동합니다.
  4. 두 포인터가 교차하거나 더 이상 조건을 만족하지 않을 때 종료합니다.

백준의 예제를 하나 풀어보겠습니다.

문제

홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데,

같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다.

당신은 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 하는데, 각 용액은 10ml시험관에 10ml씩 들어있고, 빈 20ml 시험관이 단 하나 있다. 게다가 용액을 계량할 수 없어서, 두 용액을 섞을 때는 10ml씩 섞어서 20ml로 만드는데, 단 한번밖에 할 수 없다. 그래서 미리 용액의 특성값들을 보고, 어떤 두 용액을 섞을 것인지 정해야 한다.

예를 들어, 연구소에 있는 용액들의 특성값이 [-101, -3, -1, 5, 93]이라고 하자. 이 경우에 특성 값이 각각 -101, 93인 용액을 혼합하면 -8인 용액을 만들 수 있다. 또한 특성값이 5인 용액과 93인 용액을 혼합하면 특성 값이 98인 용액을 만들 수 있다. 모든 가능한 조합을 생각해 보면, 특성값이 2인 용액이 0에 가장 가까운 용액이다.

용액들의 특성값 A1, … ,AN이 오름차순으로 주어졌을 때, 이 중 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값 B를 출력하시오.

입력

N
A1 A2 … AN

출력

B

 

 

val n = readln().toInt()
val arr = readln().split(" ").map { it.toInt() }.sorted()

var left = 0
var right = n - 1
var closestSum = Int.MAX_VALUE // 0에 가장 가까운 합
var answer = Pair(0, 0) // 결과로 반환할 두 값

먼저 주어진 리스트를 선언해줍니다. 그리고 왼쪽 포인터는 0부터, 오른쪽 포인터는 마지막 인덱스 값부터 시작합니다.

 

while (left < right) {
    val sum = arr[left] + arr[right]

    // 현재 합이 0에 더 가까우면 결과 갱신
    if (kotlin.math.abs(sum) < kotlin.math.abs(closestSum)) {
        closestSum = sum
        answer = Pair(arr[left], arr[right])
    }

    ...
}

왼쪽 포인터가 오른쪽 포인터는 넘지 않는 동안 이동시키면서 두 포인터 위치 간의 값들을 더해서 검사합니다.

이전 합을 변수에 들고 있다가 새로운 합이 0에 가까운지를 검사하여 변수를 갱신합니다.

 

합에 따라 포인터를 이동하는데, 양수라면 큰 값을 줄여야합니다. 따라서 오른쪽 포인터를 왼쪽 방향으로 이동시켜야하고,

합이 음수라면 너무 작은 값을 줄이기 위해 왼쪽 포인터를 오른쪽으로 이동시켜야합니다.

합이 정확히 0이라면 그대로 로직이 종료됩니다.

// 합에 따라 포인터 이동
if (sum > 0) {
    right-- // 합이 양수면 큰 값을 줄이기 위해 오른쪽 포인터 이동
} else if (sum < 0) {
    left++ // 합이 음수면 작은 값을 줄이기 위해 왼쪽 포인터 이동
} else {
    break // 합이 정확히 0이면 종료
}

 

반응형
저작자표시 (새창열림)
'Algorithm' 카테고리의 다른 글
  • 최대 힙 - Kotlin
  • 이분 탐색 (Binary Search)
  • [Kotlin / DP] BOJ - 이친수
  • 선형 구조 VS 비선형 구조
SeungYong.Lee
SeungYong.Lee
반응형
SeungYong.Lee
Win-Dev
SeungYong.Lee
전체
오늘
어제
  • All (236)
    • Development (136)
      • Android (132)
      • iOS (0)
      • Flutter (4)
      • Backend (0)
    • Algorithm (5)
    • Knowledge (5)
      • IT (2)
      • Science (0)
      • ETC & Tip (3)
    • Today I Learn (28)
    • Coding Test (62)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 안녕하세요. 반갑습니다 :)

인기 글

태그

  • Imageview
  • Android
  • Java
  • Kotlin
  • Widget
  • dfs
  • 코딩테스트
  • HTTP
  • coroutine
  • 코틀린
  • compose
  • glance
  • Collection
  • exception
  • 프로그래머스
  • Animation
  • Flutter
  • 비동기처리
  • hilt
  • Retrofit

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
SeungYong.Lee
투 포인터 알고리즘(Two Pointers)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.