[ 알고리즘 ] 투 포인터 (Two Pointer)
투 포인터란?두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 투 포인터의 특징 1. 투 포인터 알고리즘은 선형시간 복잡도[ O(n) ]를 가지므로 효율적. 2. 한 번의 반복으로 모든 요소를 처리하기에 효율적. 활용 예시주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값(target)을 갖는지 확인하는 문제 문제 : 갯수가 5개인 배열에서 구간합이 5인 구간을 찾기시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.현재 부분 합이 A과 같다면 카운트한다.현재 부분 합이 A보다 작다면 end를 1 증가시킨다.현재 부분 합이 A보다 크거나 같다면 start를 1 증가시킨다.모든 경우를 확인할 때까지 2-4번 과정을 반복한다. 1. 5개의 배열 2. s..
코딩테스트/[ 알고리즘 ]
2024. 3. 10. 15:48
