Two Pointer

 

❒ Description

---

Trapping Rain water 문제를 풀면서 사용한 Two-Pointer 알고리즘에 대한 정리

 

 

 

 

❒ Two Pointer

---

1. Two Pointer 알고리즘이란?

주로 정렬된 배열에서 두 개의 Pointer를 사용하여 특정 조건을 만족할 때 까지 탐색하는 알고리즘이다.

해당 알고리즘의 동작원리는 다음과 같다.

1. 초기화
   • 배열의 시작점 또는 특정 위치에 두개의 포인터를 배치. (일반적으로 시작과 끝에 배치)
2. 조건 검색 및 이동
   • 각 포인터가 가리키는 요소를 검사하여 조건을 만족하는지 확인한다.
   • 조건을 만족하지 않으면 포인터를 이동시킨다.
3. 종료 조건
   • 포인터가 배열의 끝에 도달하고나, 두 pointer가 교차할 때 반복을 종료한다.
   • 이때 원하는 결과를 얻었는지 확인한다.

 

2. 언제 사용하면 좋을까?

주로 정렬된 배열이나 리스트와 같은 선형 자료구조를 다루는 문제에서 효과적이다.

• 부분 배열의 합이나 평균 계산을 요구하는 문제
• 두 수의 합을 요구하는 문제
• 두 정렬된 배열에서 공통 요소를 찾는 문제
• 배열 내 특정 조건을 만족하는 구간 찾기 (Sliding Window Technique)
• 회문 검사 (Palindrome Check)
• K번째 작은 수 찾기
• 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합하는 문제
• 모든 0을 배열의 끝으로 이동하는 문제

 

3. 시간 복잡도

정렬된 배열 및 리스트에서는 O(n)의 시간 복잡도를 갖는다.

하지만 정렬이 되지 않은 경우에는 평균적으로 O(nlogn)의 시간 복잡도를 갖는다.

 

 

 

❒ 해결 가능 문제

---

• [LeetCode#42] Trapping rain water
• [LeetCode#15] 3Sum

 

 

 

 

 

---