투포인터1 [알고리즘] 이분 탐색, 투 포인터 알고리즘 & 백준(두 수의 합, 두 용액) 이분탐색에 문제를 풀다가 두 용액이라는 문제가 나왔고, start, end, mid를 놓고 계속 풀었기 때문에 mid값을 어떻게 설정해야하는지에 대한 어려움이 있었다. 두 용액 문제의 알고리즘 분류를 보니 두 포인터(- 투 포인터)가 있어서 이를 활용해야함을 알았다. 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 투 포인터 알고리즘이란? 포인터가 C언어에서의 포인터가 아니다. 정말 말그대로 가리키는 두 개의 포인터라고 생각하면 된다. 이름처럼 양 끝을 각각 포인터로 설정한 다음, 포인터의 위치를 안쪽으로 옮기며 주어진 연산을 반복해 최적값을 찾아내는 방식이다. 투포인터 알고리즘의 장점은 리스.. 2022. 10. 6. 이전 1 다음