본문 바로가기

two pointer1

[개념 정리] 투 포인터 최근 알고리즘을 풀면서 시간 초과와 예외처리로 인해 상당히 애를 먹었던 문제가 있다. 해당 문제의 다른 풀이를 찾아보니 투 포인터 알고리즘을 통해 간단하게 구현할 수 있다는 점을 알았고 이에 대해 정리해보고자 한다. 투 포인터 알고리즘은 하나의 배열에서 두 개의 인덱스 포인터를 조작하는 알고리즘을 의미한다. 문제를 예시로 들어서 설명하면 다음과 같다. 백준 - 2467. 용액 이 문제에서 0과 가장 가까운 거리의 합을 가지는 두 원소를 구하는 방법은 먼저 O(N^2)의 시간복잡도를 가지는 방법이 존재한다. 하지만 문제처럼 N의 크기가 O(N^2)으로 해결할 수 없는 경우에 투 포인터 알고리즘을 사용하면 O(N)에 해당 값을 구할 수 있다. (이 문제는 정렬이 필요하기 때문에 전체 문제의 시간복잡도는 O(.. 2021. 4. 1.

이전 1 다음

티스토리툴바