-
[알고리즘] Two-Pointers Algorithm (투 포인터 알고리즘)알고리즘 2024. 6. 15. 11:43
정의- 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 가면서 원하는 값을 찾을때 까지 탐색하는 알고리즘
- 배열이나 리스트에 순차적으로 접근해야 할 때 두개의 포인트의 위치를 기록하면서 처리한다
- 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)의 시간복잡도로 단축 시킬 수 있다
- 이분탐색 알고리즘과 유사한 방식이다
동작 방식
- 왼쪽 left, 오른쪽 right 또는 start, end 이런 식으로 포인트의 변수 이름을 지정한다
- 조건은 항상 두 포인터의 관계는 left <= end 여야 한다
1. 초기화
두개의 포인터를 초기화 한다, 이 포인터들은 배열의 시작과 끝 또는 특정 위치에서 시작할 수 있다
2. 반복 처리
반복문을 사용하여 두 포인터가 특정 조건을 만족할 때까지 이동한다 여기에서 포이넡의 이동 방향은 문제에 따라 다를 수 있다
3. 조건 체크
포인터가 가리키고 있는 요소를 비교하거나 합산하여 조건을 확인하고 만족한다면 필요한 작업을 수행하고 포인터를 이동시킨다
4. 포인터 이동
조건에 따라 적절히 이동시킨다
5. 종료 조건
포인터가 서로 교차하거나 더 이상 조건을 만족하지 않을때 반복문을 종료한다
이분탐색 vs 투 포인터 알고리즘
차이점
사용조건
- 이분탐색 : 정렬된 배열
- 투포인터 : 정렬 여부 상관 없음
목적
- 이분 탐색 : 특정 값의 존재 여부 및 위치 찾기
- 투 포인터 : 구간 내 조건 만족하는 요소 찾기
시간 복잡도
- 이분 탐색 : O(log n)
- 투 포인터 : O(n)
알고리즘 방식
- 이분 탐색 : 반복적으로 배열을 반으로 나눔
- 투 포인터 : 두개의 포인터로 배열을 순회
적용예시
- 이분 탐색 : 값 검색, 특정 값 위치 찾기
- 투 포인터 : 두 수의 합, 부분 배열 합
이분탐색 관련 글
https://hyeonni.tistory.com/20
투 포인터 문제
https://hyeonni.tistory.com/75
'알고리즘' 카테고리의 다른 글
[알고리즘] 이분 탐색 / 이진 탐색 Java (0) 2024.04.22