[알고리즘]#7_투 포인터

 

#1. 개념

 

1. 투 포인터

• [정의] : '투 포인터' 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다.
• [특징] : '투 포인터' 알고리즘은 일반적으로 정렬된 배열 혹은 리스트에서 활용합니다.
• [동작 방식] 
  1. 배열의 시작 지점을 가리키는 포인터, 그리고 끝 지점을 가리키는 포인터, 두 개의 포인터를 초기화합니다.
  2. 두 포인터가 움직이며 주어진 조건을 만족하는지 검사합니다.
  3. 조건을 만족할 경우, 원하는 동작을 수행하고, 조건을 만족하지 못할 경우, 포인터를 이동시킵니다.
  4. 원하는 결과 값을 얻을 때까지, 2~3번 동작을 반복합니다.

 

---

 

#2. 예제

 

1. 연속된 부분 수열의 합

[Programmers]#Level2_연속된 부분 수열의 합, 투 포인터

 

#include <string>
#include <vector>
#include <climits>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {

    vector<int> answer;

    int left = 0;
    int right = 0;
    int sum = 0;
    int min_length = INT_MAX;
    
    answer.resize(2, -1);
    
    while(right <= sequence.size() && left < sequence.size())
    {
        if(sum >= k || right == sequence.size())
        {
            if(sum == k && right-left+1 < min_length)
            {
                min_length = right-left+1;
                answer[0] = left;
                answer[1] = right-1;
            }
            sum -= sequence[left++];
        }
        else
        {
            sum+= sequence[right++];
        }
    }
    
    return answer;
    
}

 

Details

 

1. 배열의 시작점을 가리키는 두 개의 포인터를 초기화합니다.
2. left 포인터는 부분 배열의 왼쪽 경계, 그리고 right 포인터는 부분 배열의 오른쪽 경계입니다.
3. left ~ right 부분 배열의 원소들의 합을 구해 주어진 k값과 비교합니다.
4. left ~ right 부분 배열의 연속된 부분 수열의 합이 k값과 같다면, min_length(최소 길이) 값을 경신하고, 정답 배열에 left 포인터가 가리키는 위치와 right 포인터가 가리키는 위치를 삽입합니다.
5. left ~ right 부분 배열의 연속된 부분 수열의 합이 k값 보다 작다면, 부분 배열의 오른쪽 경계를 오른쪽으로 1칸 이동시킵니다.

 

2. 구명 보트

[Programmers_C++]#Level2_구명보트, 투 포인터 알고리즘

 

Details

 

1. left 포인터는 몸무게 목록의 시작 지점, right 포인터는 몸무게 목록의 마지막 지점으로 초기화합니다.
2. 현재 가장 적은 몸무게와 가장 큰 몸무게의 합이 limit보다 작을 경우, left+1과 right-1을 해줍니다.
3. 현재 가장 적은 몸무게와 가장 큰 몸무게의 합이 limit보다 클 경우, right-1만 해줍니다.
4. 결과적으로, limit 보다 작을 경우 투 포인터 알고리즘이 일찍 끝남과 동시에, 최소 보트 개수를 갖게 됩니다.

 

---