투포인터 알고리즘(Two Pointers Algorithm)
투포인터 알고리즘은 1차원 배열에서 각자 다른 원소를 가르키는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 알고리즘 문제를 풀다가 완전 탐색으로 해결하다가 시간 초과가 발생하는 경우에 사용할 수 있다.
문제는 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립할 경우 사용할 수 있는 알고리즘은 다음과 같다.
- 포인터 2개를 준비. 이를 left, right라고 함.
- 처음에는 left = right = 0. 항상 left <= right 을 만족
- 두 개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할을 함
left = right 일 경우. 즉, 크기가 0인 아무것도 포함하지 않는 부분 배열일 때, 아래의 과정을 left < N 인 동안 반복
- 현재 부분합이 M 이상이거나 이미 right = N이면 left++
- 그렇지 않다면 right++
- 현재 부분합이 M과 같다면 count++
쉽게 이해하자면, right와 left를 무조건 증가시키는 방향으로만 변화시켜가면서, 도중에 부분 배열의 합이 정확히 M이 되는 경우를 세는 것이다.
아래는 예시 코드
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr) {
let answer = (lt = sum = 0);
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
if (sum === m) answer++;
while (sum > m) {
sum -= arr[lt++];
if (sum === m) answer++;
}
}
return answer;
}
let a = [1, 3, 1, 2, 3];
console.log(solution(5, a));
</script>
</body>
</html>
- 추천 문제(백준)
- 2003: 수들의 합
- 1644: 소수의 연속합
- 1806: 부분합
- 2230: 수 고르기
슬라이딩 윈도우(Sliding Window)
그리고 이와 비슷한 슬라이딩 윈도우(Sliding Window) 유형도 존재한다. 이는 마치 창문을 한 쪽으로 밀면서 문제를 푸는 것과 유사해서 붙여진 이름인데, 이는 투 포인터처럼 구간을 훑으면서 지나간다는 공통점이 있으나 슬라이딩 윈도우는 어느 순간에도 그 구간의 넓이가 동일하다는 차이점이 있다.
슬라이딩 윈도우 알고리즘은 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다. 예를 들어 정수로 이루어진 배열에서 길이가 3인 서브배열의 합계가 가장 큰 서브배열은 무엇인가? 같은 문제에서 사용될 수 있다.
이는 단순하게 for 루프로 모든 배열 요소를 특정 길이만큼 순회하며 합계를 구해 최대 값을 구할 수도 있지만 더 효율적으로 코드를 작성하려면 슬라이딩 윈도우를 사용하는 것이 좋다.
우선 기존 단순한 방식에서 서브 배열의 요소를 순회하다 보면 중복되는 요소들이 존재한다. 위의 이미지 처럼 범위가 5인 서브배열을 탐색하는 경우, 0~4 범위의 서브 배열과 1~5 서브배열은 공통적으로 1~4 범위가 중복된다. 이 때, 중복되는 요소들을 재사용하는 방법이 슬라이딩 윈도우 알고리즘의 핵심이다.
ex) k=3인 경우
먼저 0~2 범위의 합을 sum과 answer에 저장을 한 후, sum에 arr의 k번째 요소에서 arr의 0번째 인덱스를 빼준 값을 더해주는 식으로 풀 수 있다.
(아래 코드는 자바스크립트로 짜 본 예시, 요즘 JS 공부를 열심히 하고 있기 때문에..!)
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(k, arr) {
let answer,
sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
answer = sum;
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
answer = Math.max(answer, sum);
}
return answer;
}
let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));
</script>
</body>
</html>'Algorithm > Data Structure, Algorithm' 카테고리의 다른 글
| [자료구조][JS] 삽입 정렬(Insertion Sort) (0) | 2021.10.01 |
|---|---|
| [자료구조][JS] 선택 정렬(Selection Sort) (0) | 2021.08.29 |
| [자료구조][JS] 스택, 큐 - push(), pop(), shift() (0) | 2021.08.22 |
| [알고리즘][JS] 해쉬 알고리즘 - JS ES6 Map() (0) | 2021.08.08 |
| [알고리즘] 완전탐색(Brute-Force) (0) | 2021.06.07 |