투 포인터, 슬라이딩 윈도우, 구간 합 (개념, 예제)

다히·2023년 1월 16일
0

Algorithm

목록 보기
3/8

배열의 특정 연속된 구간을 처리하는 경우

예시

  • 부분 연속 수열의 개수
  • [L, R] 주어질 때마다 L번째 원소부터 R번째 원소까지의 합 구하기

아래의 기법들을 활용하면 O(N) 시간에 처리가 가능하다


투 포인터

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

시작 인덱스, 종료 인덱스를 지정해 접근할 데이터의 범위를 표현

  • 투 포인터 알고리즘 대표 유형
  1. 2개의 포인터 변수 시작점이 배열의 시작점인 경우
  2. 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점(arr.length-1)에 위치한 경우

구현) 구간이 연속적일 때

투 포인터를 활용한, 특정한 합을 가지는 부분 연속 수열 개수 찾기

  • 완전 탐색으로 해결하면 O(N2)O(N^2), 투 포인터로 해결하면 O(N)O(N)
  1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
  2. 현재 부분 합이 M과 같다면, 카운트 한다.
  3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.
  4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다.
  5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.
  • 부분 합이 M과 같을 때 start를 증가시키는 이유: 다음 배열을 탐색해야 하므로!

예시

  • M = 5일 때
  1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 함
  • 현재 부분 합 = 1 -> 무시, count: 0
  1. 부분 합 1 < 5 이므로 end 1 증가
  • 현재 부분 합 = 3 -> 무시, count: 0
  1. 부분 합 3 < 5 이므로 end 1 증가
  • 현재 부분 합 = 3 -> 무시, count: 0
  1. 부분 합 6 > 5 이므로 start 1 증가
  • 현재 부분 합 = 5 -> 카운트, count: 1
  1. 부분 합 5 == 5 이므로 start 1 증가
  • 현재 부분 합 = 3 -> 무시, count: 1
  1. 과정 반복

구현) 구간이 연속적이지 않을 때

무작위로 두 개의 데이터를 골라 찾는 값인지 확인하는 문제

⇒ 연속성을 만들어줘야 함
1. 데이터 정렬
2. end(오른쪽 인덱스)를 처음(0)에서부터가 아닌, 마지막(len(arr)-1)에서 시작

예시

  • 나열된 수 중에 2개를 합쳐 M 만들기(BOJ #1940)
  • 서로 다른 두 수의 합으로 표현되는 수 찾기(BOJ #1253)

start < end일 동안

  • 합 > 원하는 값 : end -= 1
  • 합 < 원하는 값 : start += 1
  • 합 == 원하는 값 : (start += 1 end -= 1 )count++

관련 문제

백준 2018번 연속된 자연수의 합 구하기

코드
-> 다시 풀고 벨로그 글로 수정하기

백준 1940번 주몽
코드
-> 다시 풀고 벨로그 글로 수정하기

백준 1253번 좋다⭐

코드


슬라이딩 윈도우

두 개의 포인터로 window 지정, window 유지한 채로 이동하며 문제 해결
⇒ 찾는 범위 크기 고정일 때

  • 배열 길이가 고정이므로 포인터 하나만 있어도 가능

  • 오른쪽으로 한 칸 이동해도 옮기기 전과 후에 겹치는 부분 존재
    → 기존 검사 결과에서 새로 들어오는 값, 빠지는 값만 반영

  • 오른쪽으로 한 번 슬라이딩할 때, 빠지게 되는 왼쪽 첫 번째 값과 추가되는 오른쪽의 값을 반영하도록 코딩

  • 슬라이딩 윈도우를 덱으로 구현하면 빠른 정렬 효과 볼 수 있음


관련 문제

백준 12891번 DNA 비밀번호
코드
-> 다시 풀고 벨로그 글로 수정하기

백준 11003번 최솟값 찾기 1⭐
코드
-> 다시 풀고 벨로그 글로 수정하기


구간 합

  • 위의 두 알고리즘과 비슷하게 배열의 특정 연속된 구간에 대한 처리를 목적으로 하는 알고리즘

  • 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

  • 합 배열 말고 접두사 합이라고 많이 하는 것 같음

합 배열

배열 A에 대한 합 배열 S 정의

S[i] = A[0] + A[1] + ... + A[i-1] + A[i]S[i] = S[i-1] + A[i]

  • 합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합
    을 구하는 시간 복잡도가 O(N) → O(1)로 감소

합 배열을 이용한 구간 합 구하기

1. L번째 원소부터 R번째 원소까지 구간의 합 구하기

S[R] - S[L-1]


2. (X1, Y1) 부터 (X2, Y2) 까지 구간의 합 구하기

  • D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합

D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]


관련 문제

백준 11659번 구간 합 구하기 4 ⭐

코드
-> 다시 풀고 벨로그 글로 수정하기

백준 11660번 구간 합 구하기 5

코드
-> 풀고 벨로그 글로 수정하기

백준 10986번 나머지 합

코드
-> 다시 풀고 벨로그 글로 수정하기




Source
이코테 2021
Do it! 알고리즘 코딩테스트 파이썬편 교재
velog

0개의 댓글