04 투 포인터와 슬라이딩 윈도우

공부하는 감자·2024년 5월 13일
0

코딩 테스트

목록 보기
4/17

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

투 포인터

  • 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
    • 두 개의 포인터를 이동해가며 리스트에 순차적으로 접근한다.
  • O(n)O(n)의 시간 복잡도 알고리즘을 갖고 있다.
    • 루프를 돌면서 두 포인터 중 하나를 1씩 증가시키고, 각 포인터가 배열의 끝까지 도달(N번)하면 루프가 끝난다.

연속된 자연수의 합

투 포인터 알고리즘의 대표적인 문제로, 연속된 자연수의 합이 특정한 값인 것을 찾는 문제이다.

몇 개의 연속된 자연수의 합으로 나타낼 수 있는 어떠한 자연수 N이 있다. 이때, N을 몇 개의 연속된 자연수의 합으로 나타낼 수 있는 가지수를 구할 때 투 포인터를 사용할 수 있다.

예를 들어, N이 15라면 다음 총 4가지가 있다.
1) 15
2) 7+8
3) 4+5+6
4) 1+2+3+4+5

또 다른 예로, N이 10이라면 다음 총 2가지가 있다.
1) 10
2) 1+2+3+4

예제: N=10인 경우

다음과 같이 1부터 10까지의 자연수를 값으로 가진 배열을 생성한다.

이때, 첫 번째 포인터(START)와 두 번째 포인터(END)는 모두 첫 번째 인덱스를 가리킨다.

1번

END 포인터를 오른쪽으로 한 칸씩 옮기면서(인덱스+1) 합을 구한다.

2번

START 포인터와 END 포인터 사이의 값들의 합이 10이 된다면, Count를 1 올린다.

  • 1 + 2 + 3 + 4 = 10

3번

END 포인터를 한 칸 다시 옮겼을 때, 합이 N(여기서는 10)을 넘어서면 START 포인터를 한 칸 앞으로 옮긴다.

4번

이렇게 다음 동작을 반복하다가 END 포인터가 배열 끝에 도달하면 루프를 끝낸다.

  • START 포인터와 END 포인터 사이의 합을 sum 이라고 할 때,
    1) sum이 10보다 작으면 END 포인터를 이동 (범위 증가)
    2) sum이 10보다 크면 START 포인터를 이동 (범위 감소)
    3) sum이 10이라면 Count를 증가시키고 END 포인터를 이동 (범위 증가)

5번

정리

이렇게 두 개의 포인터를 지정하고, 각 포인터를 이동해가면서 값을 구하는 알고리즘을 투 포인터라고 한다.


슬라이딩 윈도우

  • 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다.
  • 투 포인터 알고리즘과 매우 비슷하지만, 범위를 유지한다는 점에서 차이가 있다.
  • 배열의 길이만큼만 탐색을 진행하면 되므로 O(n)O(n)의 시간 복잡도로 문제를 해결할 수 있다.

원리

다음과 같이 범위를 지정했다고 가정하자.

1번

START와 END 포인터를 동시에 1씩 증가시켜서 범위를 유지한 채로 이동시킨다.

  • 창문을 옆으로 미는 것과 유사한 동작이라고 생각하면 된다.

2번

이렇게 END 포인터가 배열의 끝에 다다를 때까지 옆으로 미는 것을 반복한다.

3번


Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

profile
책을 읽거나 강의를 들으며 공부한 내용을 정리합니다. 가끔 개발하는데 있었던 이슈도 올립니다.

0개의 댓글