[이것이 코딩 테스트다 with Python]_39_투 포인터

220216 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=ttLRltNDiCo&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=39 

 

 

 

 

 

 

 

1. 투 포인터 (Two Pointers)

: 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

: 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작과 끝점 2개의 점으로 접근할 데이터의 범위 표현한다

 

 

EX) 특정한 합을 가지는 부분 연속 수열 찾기

- N개의 자연수로 구성된 수열

- 합이 M인 부분 연속 수열의 개수

- 수행 시간 O(N)

 

1) 시작점(strat)과 끝점(end)이 첫 번째 원소의 인덱스 가리키기

2) 현재 부분 합이 M 과 같다면 카운트

3) 현재 부분 합이 M보다 작다면, end 1 증가

4) 현재 부분 합이 M보다 크거나 같다면, start 1 증가

5) 모든 경우 확인할 때까지 2~4 과정 반복

 

 

 

 

 

 

 

• python

n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분합 M
data = [1, 2, 3, 2, 5] # 전체 수열

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
    # end를 가능한 만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]

print(count)

• c++

#include <bits/stdc++.h>

using namespace std;

int n = 5; // 데이터의 개수 N
int m = 5; // 찾고자 하는 부분합 M
int arr[] = {1, 2, 3, 2, 5}; // 전체 수열

int main() {
    int cnt = 0;
    int intervalSum = 0;
    int end = 0;

    // start를 차례대로 증가시키며 반복
    for (int start = 0; start < n; start++) {
        // end를 가능한 만큼 이동시키기
        while (intervalSum < m && end < n) {
            intervalSum += arr[end];
            end += 1;
        }
        // 부분합이 m일 때 카운트 증가
        if (intervalSum == m) {
            cnt += 1;
        }
        intervalSum -= arr[start];
    }

    cout << cnt << '\n';
}

• java

import java.util.*;

class Main {
    public static int n = 5; // 데이터의 개수 N
    public static int m = 5; // 찾고자 하는 부분합 M
    public static int[] arr = {1, 2, 3, 2, 5}; // 전체 수열

    public static void main(String[] args) {
        int cnt = 0;
        int intervalSum = 0;
        int end = 0;

        // start를 차례대로 증가시키며 반복
        for (int start = 0; start < n; start++) {
            // end를 가능한 만큼 이동시키기
            while (intervalSum < m && end < n) {
                intervalSum += arr[end];
                end += 1;
            }
            // 부분합이 m일 때 카운트 증가
            if (intervalSum == m) {
                cnt += 1;
            }
            intervalSum -= arr[start];
        }

        System.out.println(cnt);
    }
}