투포인터(Two Pointer) 알고리즘 총 정리 - 개념, 원리, 시간복잡도, 활용, 장단점, 주의점, C언어, Java, Python 예시코드

투 포인터 알고리즘

 

 

1. 투포인터 알고리즘이란?

투포인터(Two Pointer) 알고리즘은 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 탐색 범위를 조절하며 문제를 해결하는 기법입니다. 주로 정렬된 배열에서 특정 조건을 만족하는 부분을 찾거나, 구간 합을 구하는 등의 문제에서 효과적으로 사용됩니다.

반응형

 

 

2. 투포인터 알고리즘의 동작 원리

투포인터 알고리즘은 두 개의 포인터를 적절히 이동시키며 문제를 해결하는 방식입니다. 다음과 같은 원리로 동작합니다.

예제: 정렬된 배열에서 특정 합을 갖는 두 수 찾기

예를 들어, 정렬된 배열 [1, 3, 5, 7, 10, 15]에서 합이 12가 되는 두 수를 찾는 문제를 생각해 봅시다.

1. 초기 설정
   • left 포인터를 배열의 첫 번째 요소(0번째 인덱스)에 위치시킵니다.
   • right 포인터를 배열의 마지막 요소(5번째 인덱스)에 위치시킵니다.
2. 두 포인터가 가리키는 값을 더함
   • arr[left] + arr[right] = 1 + 15 = 16 (목표보다 크므로 right를 감소)
   • arr[left] + arr[right] = 1 + 10 = 11 (목표보다 작으므로 left를 증가)
   • arr[left] + arr[right] = 3 + 10 = 13 (목표보다 크므로 right를 감소)
   • arr[left] + arr[right] = 3 + 7 = 10 (목표보다 작으므로 left를 증가)
   • arr[left] + arr[right] = 5 + 7 = 12 (목표값과 일치)
3. 결과 도출
   • 합이 12인 두 수는 5와 7입니다.

이 방식은 불필요한 탐색을 줄이면서 효율적으로 값을 찾을 수 있도록 합니다.

 

 

 

3. 시간 복잡도 분석

• 브루트포스(완전 탐색) 방법: O(N^2)
• 투포인터 알고리즘: O(N)

두 포인터를 사용하면 한 번의 순회(또는 두 개의 포인터가 이동하는 방식)만으로 결과를 찾을 수 있으므로, 완전 탐색보다 훨씬 효율적입니다.

 

 

 

4. 투포인터 알고리즘의 주요 사용처

1️⃣ 정렬된 배열에서 특정 합을 찾는 문제

• 두 개의 수를 더해서 특정 값을 만들어야 하는 문제에서 활용됩니다.
• 예: Two Sum 문제 (정렬된 배열에서 특정 합 찾기)

 

2️⃣ 구간 합 (부분 배열 합) 문제

• 특정 조건을 만족하는 연속된 부분 배열을 찾는 데 사용됩니다.
• 예: 연속된 부분 배열의 합이 특정 값 이상이 되는 최소 길이 찾기

 

3️⃣ 문자열 또는 배열 내 특정 패턴 찾기

• 팰린드롬 검사와 같은 문제에서 유용합니다.
• 예: 주어진 문자열이 회문인지 확인하는 문제

 

4️⃣ 교차 검증 및 병합 문제

• 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 병합하는 과정에서도 사용됩니다.

 

 

 

5. 투포인터 알고리즘의 장단점

✅ 장점

• 시간 복잡도 감소: 완전 탐색(O(N²))보다 훨씬 빠른 O(N) 또는 O(N log N)으로 문제를 해결할 수 있음.
• 메모리 효율성: 별도의 추가 메모리 없이 인덱스만을 이용하여 해결 가능.
• 다양한 문제 해결 가능: 정렬된 배열을 기반으로 한 문제에서 매우 유용함.

 

❌ 단점

• 정렬이 필수적: 대부분의 경우 정렬된 배열에서만 사용 가능하므로, 정렬이 필요할 경우 O(N log N)의 추가 비용이 발생.
• 적용 범위 제한: 투포인터를 사용할 수 있는 문제 유형이 제한적이며, 모든 문제에 적용할 수 없음.
• 포인터 이동 방식이 문제마다 다름: 문제마다 포인터를 어떻게 이동해야 하는지에 대한 분석이 필요함.

 

 

 

6. 투포인터 알고리즘 구현 예제

1️⃣ C 언어 예제: 정렬된 배열에서 두 수의 합 찾기

#include <stdio.h>

void twoSum(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            printf("두 수의 위치: %d, %d\n", left, right);
            return;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    printf("합을 만족하는 두 수가 없습니다.\n");
}

int main() {
    int arr[] = {1, 2, 3, 5, 7, 10};
    int target = 9;
    int size = sizeof(arr) / sizeof(arr[0]);
    twoSum(arr, size, target);
    return 0;
}

 

2️⃣ Java 예제: 부분 배열의 합이 특정 값을 만족하는 최소 길이 찾기

public class TwoPointerExample {
    public static int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
        }
        return (minLen == Integer.MAX_VALUE) ? 0 : minLen;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println("최소 부분 배열 길이: " + minSubArrayLen(target, nums));
    }
}

 

3️⃣ Python 예제: 팰린드롬 검사

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

s = "racecar"
print(f"'{s}'는 팰린드롬인가? {is_palindrome(s)}")

 

 

7. 투포인터 사용 시 주의할 점

1. 배열이 정렬되지 않은 경우 사용할 수 없음
   • 대부분의 투포인터 문제는 정렬된 배열에서만 유효합니다.
2. 무한 루프 방지
   • 종료 조건을 명확하게 설정해야 합니다.
3. 경우에 따라 포인터 이동 방향을 다르게 설정해야 함
   • 예를 들어, left를 증가시킬지, right를 감소시킬지 적절한 로직을 설정해야 합니다.

 

 

투포인터 알고리즘은 배열 및 문자열 탐색에서 매우 유용한 기법으로, 다양한 문제에 응용될 수 있습니다. 특히 정렬된 배열을 활용하는 문제에서 효율성을 극대화할 수 있으며, 슬라이딩 윈도우 기법과 조합하여 사용하면 더욱 강력한 문제 해결 능력을 발휘할 수 있습니다.

 

 

슬라이딩 윈도우 기법에 대한 내용은 아래 글에 자세히 잘 정리했습니다.

2024.12.26 - [알고리즘] - 슬라이딩 윈도우 완벽 정리: 개념부터 실전 활용까지

슬라이딩 윈도우 완벽 정리: 개념부터 실전 활용까지