[LG 유레카] 투포인터, 슬라이딩 윈도우
2주차 수업 - 1차원, 2차원 배열 핸들링,투포인터, 슬라이딩 윈도우 - 스택, 큐, 링크드 리스트 활용 - 정렬 알고리즘과 알고리즘별 비교 - 완전 탐색, 순열, 조합, 부분 집합 - 비선형자료구조의 특징, 트리 개념 및 용어 설명
투 포인터Two Pointer Algorithm
-
투 포인터Two Pointer Algorithm
배열이나 리스트에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘이다.
-
투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용
➡ 각각 탐색 범위의 시작과 끝은 가리킴
-
동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른족 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가짐
-
해당 알고리즘은 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용될 수 있다.
-
투 포인터 수행 단계
- 배열 또는 리스트의 시작 위치에 첫 번째 포인터와 두 번째 포인터를 설정한다.
- 두 포인터 사이의 구간을 조사하고 조건을 확인한다.
- 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료한다.
- 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동시킨다.
- 다시 2번 단계로 돌아가 반복한다.
투 포인터 종류
고정 길이 슬라이딩 윈도우
고정된 길이의 윈도우를 사용하여 배열이나 리스트를 탐색한다.
- 윈도우의 크기를 일정하게 유지하면서 왼쪽 포인터와 오른쪽 포인터를 이동시키며 필요한 계산을 수행한다.
- 이 유형은 부분 배열의 합이나 평균을 계산하는 등의 문제에 사용될 수 있다.
가변 길이 슬라이딩 윈도우
가변 길이의 윈도우를 사용하여 배열이나 리스트를 탐색한다.
- 윈도우의 크기를 필요에 따라 변경하면서 왼쪽 포인터를 이동시키며 필요한 계산을 수행한다.
- 이 유형은 최소 길이 부분 배열이나 최대 길이 부분 배열을 찾는 등의 문제에 사용될 수 있다.
두 포인터의 합과 차
배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결한다.
- 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킨다. 이 유형은 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용될 수 있다.
슬라이딩 윈도우 알고리즘
고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.
배열이나 리스트에서 요소의 일정범위의 값을 비교할 때 사용할 수 있다.
1차원 배열의 2회 이상 반복적으로 탐색해야 할 경우 O(n2)이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(n)으로 줄일 수 있는 장점이 있다.
[문제1]
연속된 3개의 숫자를 더해 가장 합계가 큰 값은?
❗: 중복된 계산 값을 재활용하여 연산의 횟수를 줄이자
댓글남기기