투 포인터 알고리즘 개념, 쉬운 예시 문제, 리트코드 문제

투 포인터 알고리즘 개념 설명

투 포인터(Two-pointers) 알고리즘은 주로 배열이나 리스트와 같은 선형 구조에서 특정 조건을 만족하는 요소들을 찾거나, 작업을 수행할 때 사용되는 기법입니다.

 

 

 

이 기법은 주로 두 개의 다른 위치를 가리키는 포인터를 활용하여, 중첩된 루프의 사용 없이 문제를 효율적으로 해결할 수 있게 도와줍니다. 이를 통해 시간 복잡도를 줄일 수 있으며, 주로 정렬된 배열이나 리스트에서 두 요소의 합이나 차이와 같은 특정 조건을 만족하는 쌍을 찾을 때 유용합니다.

 

예를 들어, 정렬된 두 배열의 모든 요소를 합치거나, 주어진 합을 이루는 두 요소를 찾는 문제에 투 포인터 알고리즘을 적용할 수 있습니다. 이 알고리즘의 기본 아이디어는 시작점과 끝점이라는 두 포인터를 배열의 시작과 끝에 배치하고, 이들을 조건에 따라 좁혀가며 해결책을 찾아가는 것입니다.

 

투 포인터 알고리즘은 간단한 로직에도 불구하고 매우 효과적이며, 다양한 문제에 적용 가능합니다. 특히 이진 탐색, 슬라이딩 윈도우, 연속된 부분 배열의 문제 등에서 그 효용을 발휘합니다. 따라서, 이 기법을 숙지하고 있으면 알고리즘 문제를 해결하는 데 있어 매우 유용한 도구가 될 수 있습니다.

 

 

 

 

 

 

이해가 잘 되지 않으실 분들을 위해 해당 개념에 대해 영상으로 잘 설명해둔 링크를 함께 첨부합니다.

 

 

 

 

 

 

 

 

투 포인터 알고리즘의 유형

충돌(Collision)

충돌 유형의 투 포인터 알고리즘은 배열이나 리스트의 양쪽 끝에서 시작하여 서로를 향해 이동하는 두 포인터를 사용합니다. 이 방법은 주로 정렬된 배열에서 두 숫자의 합이 특정 값에 해당하는 쌍을 찾거나, 특정 조건을 만족하는 요소의 범위를 찾는 데 사용됩니다. 대표적인 예로는 'Two Sum', 'Three Sum', 'Valid Palindrome' 등이 있습니다.

 

전진(Forward)

전진 유형의 투 포인터 알고리즘은 배열이나 리스트를 한 방향으로만 전진하며 문제를 해결합니다. 이 유형은 보통 최소 길이의 부분 배열을 찾거나, 특정 조건을 만족하는 연속된 요소들을 처리할 때 사용됩니다. 이 방법은 'Minimum Size Subarray Sum', 'Longest Substring Without Repeating Characters', 'Minimum Window Substring' 등의 문제에 적용됩니다.

이러한 유형을 이해하고 활용함으로써, 다양한 알고리즘 문제에 대한 해결 능력을 향상시킬 수 있습니다.

 

슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우는 배열이나 리스트에서 일정 범위의 연속된 데이터를 처리할 때 사용되는 투 포인터 알고리즘의 변형입니다. 이 기법은 두 포인터가 배열을 같은 방향으로 이동하면서 일정한 길이의 윈도우를 유지하는 형태로 작동합니다. 주로 부분 배열의 최대 합, 연속된 요소의 최대 평균 등을 찾는 문제에 사용됩니다.

 

조건 충족(Condition Satisfaction)

특정 조건을 만족하는 연속적인 구간을 찾기 위해 두 포인터가 다양한 조건하에서 움직이는 방식입니다. 예를 들어, 부분 배열의 합이 특정 값 이상이 되는 최소 길이를 찾거나, 특정 조건을 만족하는 연속적인 요소들의 집합을 찾는 데 사용될 수 있습니다.

 

병합 과정(Merging Process)

두 개의 정렬된 배열이나 리스트를 합병하는 과정에서도 투 포인터 알고리즘을 적용할 수 있습니다. 각 배열에서 한 포인터씩 사용하여, 두 배열의 요소를 하나씩 비교하며 새로운 배열로 합병하는 과정에 사용됩니다. 이는 효율적인 정렬 알고리즘 구현에 필수적인 기법 중 하나입니다.

 

 

 

 

 

투 포인터 알고리즘 쉬운 예시 문제

해당 내용은 인프런 강의 '자바스크립트 알고리즘 문제풀이 입문'에서 발췌하였습니다.

자바스크립트로 된 비교적 난이도 낮은 예제로 코딩테스트를 대비하고 싶으신 분들에게 강력 추천하는 강의입니다.

 

 

 

두 배열 합치기

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

▣ 출력설명
오름차순으로 정렬된 배열을 출력합니다.

▣ 입력예제 1
3
1 3 5
5
2 3 6 7 9

▣ 출력예제 1
1 2 3 3 5 6 7 9

 

 

유의사항

sort를 해서 두 배열 arr1 과 arr2를 합치면 시간복잡도가 증가합니다.

투 포인터를 사용하는 이유는 for문 하나로만 진행할 수 있어서 시간복잡도가 O(n+m)이 되어 훨씬 간단해집니다.

 

예제 문제 접근방법

이 문제의 핵심은 투 포인터 알고리즘을 활용하여 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는 것입니다. 

아래 단계별로 절차를 설명해보겠습니다.

1. 두 배열 arr1과 arr2의 각각 첫 번째 원소를 가리키는 두 포인터로, pointer1(p1)과 pointer2(p2)를 0으로 초기화합니다.
2. p1과 p2가 각각 배열 arr1과 arr2의 끝에 도달할 때까지 반복합니다.
   • 만약 arr1[p1]이 arr2[p2]보다 작거나 같다면, arr1[p1]을 결과 배열에 추가하고 p1을 한 칸 이동합니다.
   • 그렇지 않다면 (즉, arr2[p2]가 더 작다면), arr2[p2]를 결과 배열에 추가하고 p2를 한 칸 이동합니다.
3. 한 배열의 모든 원소가 결과 배열에 추가된 후, 다른 배열에 남은 원소들을 결과 배열에 추가합니다.
4. 최종적으로 합쳐진 결과 배열을 출력합니다.

예제 입력 배열:

• 첫 번째 배열: [1, 3, 5]
• 두 번째 배열: [2, 3, 6, 7, 9]

예제 출력 배열:

[1, 2, 3, 3, 5, 6, 7, 9]

 

 

예제 문제 풀이

        function solution(arr1, arr2) {
            let answer = [];
            let p1 = p2 = 0;
            let n = arr1.length; // 3
            let m = arr2.length; // 5
            while (p1 < n && p2 < m) {
                if (arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);
                else answer.push(arr2[p2++]);

            }
            console.log(p1, p2) // 3, 2
            // 위의 while문을 돌고 남은 수를 answer에 push한다
            while (p1 < n) answer.push(arr1[p1++]);
            while (p2 < m) answer.push(arr2[p2++]);
            // p2가 2일 때 answer.push(6), p2는 3
            // p2가 3일 때 answer.push(7), p2는 4
            // p2가 4일 때 answer.push(9), p2는 5로 반복 끝

            return answer;
        }

        let a = [1, 3, 5];
        let b = [2, 3, 6, 7, 9];
        console.log(solution(a, b));

 

 

 

 

투 포인터 알고리즘 리트코드 문제 바로가기

충돌(Collision)

LeetCode 167. Two Sum II LeetCode 15. 3Sum LeetCode 75. Sort Colors LeetCode125. Valid Palindrome

 

전진(Forward)

LeetCode 209. Minimum Size Subarray Sum LeetCode 3. Longest Substring Without Repeating Characters LeetCode 76. Minimum Window Substring LeetCode 19. Remove Nth Node From End of List