[LG 유레카] 투포인터, 슬라이딩 윈도우

2주차 수업 - 1차원, 2차원 배열 핸들링,투포인터, 슬라이딩 윈도우 - 스택, 큐, 링크드 리스트 활용 - 정렬 알고리즘과 알고리즘별 비교 - 완전 탐색, 순열, 조합, 부분 집합 - 비선형자료구조의 특징, 트리 개념 및 용어 설명

투 포인터Two Pointer Algorithm

• 투 포인터Two Pointer Algorithm

  배열이나 리스트에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘이다.

  • 투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용

    ➡ 각각 탐색 범위의 시작과 끝은 가리킴

  • 동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른족 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가짐

  • 해당 알고리즘은 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용될 수 있다.

투 포인터 수행 단계

1. 배열 또는 리스트의 시작 위치에 첫 번째 포인터와 두 번째 포인터를 설정한다.
2. 두 포인터 사이의 구간을 조사하고 조건을 확인한다.
3. 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료한다.
4. 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동시킨다.
5. 다시 2번 단계로 돌아가 반복한다.

투 포인터 종류

고정 길이 슬라이딩 윈도우

고정된 길이의 윈도우를 사용하여 배열이나 리스트를 탐색한다.

• 윈도우의 크기를 일정하게 유지하면서 왼쪽 포인터와 오른쪽 포인터를 이동시키며 필요한 계산을 수행한다.
• 이 유형은 부분 배열의 합이나 평균을 계산하는 등의 문제에 사용될 수 있다.

가변 길이 슬라이딩 윈도우

가변 길이의 윈도우를 사용하여 배열이나 리스트를 탐색한다.

• 윈도우의 크기를 필요에 따라 변경하면서 왼쪽 포인터를 이동시키며 필요한 계산을 수행한다.
• 이 유형은 최소 길이 부분 배열이나 최대 길이 부분 배열을 찾는 등의 문제에 사용될 수 있다.

두 포인터의 합과 차

배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결한다.

• 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킨다. 이 유형은 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용될 수 있다.

슬라이딩 윈도우 알고리즘

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.

배열이나 리스트에서 요소의 일정범위의 값을 비교할 때 사용할 수 있다.

1차원 배열의 2회 이상 반복적으로 탐색해야 할 경우 O(n²)이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(n)으로 줄일 수 있는 장점이 있다.

[차나니의 개발일지]https://chanhan.tistory.com/entry/Algorithm-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-Window-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-Java

[문제1]

연속된 3개의 숫자를 더해 가장 합계가 큰 값은?

❗: 중복된 계산 값을 재활용하여 연산의 횟수를 줄이자