[알고리즘] 효율적인 배열/리스트 탐색을 위한 투 포인터와 슬라이딩 윈도우 알고리즘

배열이나 리스트에서 특정 조건을 만족하는 부분을 효율적으로 탐색하는 알고리즘이다. 이 두 알고리즘은 비슷하다.

투 포인터 알고리즘

• 투 포인터 알고리즘이란?
  • 배열이나 리스트에서 두 개의 포인터를 이용해 특정 조건을 만족하는 부분을 탐색하는 알고리즘이다.
  • 주로 정렬된 배열이나 리스트에서 사용되며, 선형 시간 복잡도 O(N)를 갖는 장점이 있다.
• 동작 방식
  • 시작 포인터와 끝 포인터를 배열의 양 끝으로 초기화 한다.
  • 시작 포인터와 끝 포인터를 이동하면서 조건을 만족하는 부분을 탐색한다.
  • 시작 포인터와 끝 포인터가 만나면 탐색을 종료한다.
• 사용 사례
  • 배열에서 두 수의 합이 특정 값이 되는 경우를 찾을 때
  • 배열에서 특정 조건을 만족하는 최단/최장 구간을 찾을 때

슬라이딩 윈도우 알고리즘

• 슬라이딩 윈도우 알고리즘이란?
  • 고정된 크기의 윈도우 배열이나 리스트에 적용하여 특정 조건을 만족하는 부분을 탐색하는 알고리즘이다.
  • 윈도우를 한 칸씩 이동시키면서 연산을 수행하므로, 상수 시간 복잡도 O(1) 를 갖는 장점이 있다.
• 동작 방식
  • 초기에 윈도우를 배열의 처음에 위치시킨다.
  • 윈도우를 한 칸씩 이동하면서 연산을 수행하고, 필요한 경우 윈도우 크기를 조정한다.
  • 윈도우를 끝까지 이동하면서 탐색을 종료한다.
• 사용 사례
  • 배열에서 연속된 부분 배열의 합이 특정 값이 되는 경우를 찾을 때
  • 문자열에서 최소/최대 윈도우를 찾거나 유효한 애너그램을 찾을 때

공통점

부분 구간 탐색: 투 포인터 알고리즘과 슬라이딩 윈도우 알고리즘은 모두 배열이나 리스트에서 특정한 조건을 만족하는 부분 구간을 탐색하는 데 사용된다.

차이점

투 포인터 알고리즘: 투 포인터 알고리즘은 배열 또는 리스트에서 두 개의 포인터를 이용하여 조건을 만족하는 부분을 탐색한다. 주로 정렬된 배열에서 사용되며, 시작 포인터와 끝 포인터를 이동하면서 조건을 만족하는 구간을 찾는다.

슬라이딩 윈도우 알고리즘: 슬라이딩 윈도우 알고리즘은 고정된 크기의 윈도우를 배열 또는 리스트에 적용하여 조건을 만족하는 부분을 탐색한다. 윈도우를 한 칸씩 이동하면서 연산을 수행하고, 필요에 따라 윈도우 크기를 조정한다.