목록투포인터문제 (1)

DevBoi

4. 알고리즘 정리 [투 포인터]

투 포인터의 대표 적인 예제는 아래와 같다. 리스트 A가 있고, 타겟값 S가 있다. 이 리스트에서 두수의 합이 타겟값 S가 되는 걸 찾는다고 가정하면? 리스트 1개씩 비교해 가면서 체크를 할수있겠지만. 리스트의 크기에 따라, 시간 복잡도는 정비례하게된다. 그러면 이럴 경우에는 ? 리스트를 정렬하고 투포인터 알고리즘을 사용하면 된다. 사용 방법은 아래 순서와 같다. 1. 리스트를 오름차순으로 정렬한다. 2. 포인터 left는 리스트의 시작점을 포인터 right는 리스트의 끝점을 가리킨다. 3. left 와 right가 만날때까지 다음을 반복한다. 3-1. left + right 의 합이 타겟 값과 같으면 출력, 3-2. left + right 가 타겟 값보다 작으면 left 1증가 3-3 left + ri..
Algorithm/[Etc] 2021. 7. 28. 17:54
이전 Prev 1 Next 다음