# 투포인터

adorno10

정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를 조작하는 기법을 말한다. 두 개의 포인터를 함께 활용할 때 얻을 수 있는 이점은 무엇일까? 투 포인터를 활용한 대표적인 예로 아래와 같은 문제가 있다

hyeon930

BOJ 1981 배열에서 이동투포인터 + BFS 문제다. 투포인터는 두 변수가 변화하면서 상관관계를 만들어낼 때 사용하면 되는 것 같다? 또 모든 문제가 그렇듯이 주어진 문제를 단순화해야한다. 단순화의 가장 쉬운 방법이 변수를 고정하는 것이다.완전탐색으로 풀기에는 너무

hyeon930

BOJ 2842 집배원 한상덕이 문제는 투포인터 + 그래프 탐색 문제다. 방문한 칸 중 가장 높은 곳과 가장 낮은 곳의 차이가 피로도라고 한다. 이 때 가장 높은 곳과 가장 낮은 곳을 정하고 탐색 가능 여부에 따라서 가장 높은 곳과 가장 낮은 곳을 조정해나가면 된다.투

hyeon930

BOJ 2143 두 배열의 합 문제풀이 주어진 A, B 배열에서 각각 합하여 나올 수 있는 모든 경우의 합을 리스트에 담는다. 첫 번째 리스트를 돌며 T - list[i] 가 두 번째 리스트에 있는지 확인한다. 어려운 문제였다... 모든 합의 경우를 가지고 있는 리

hyeon930

BOJ 1208 부분수열의 합2 문제풀이 일단 부분수열의 정의를 잘못알고 있어서 시간이 좀 걸렸다. 부분수열은 원래 수열의 일부 항을 원래 순서대로 나열한 것이다. 따라서 순서만 지킨다면 원래 수열에서 연속적으로 가져오지 않아도 된다.(나는 연속된 항만 가져와야한다고 생각했다...) BOJ 1182 부분수열의 합1 문제의 경우에 시간이 충분했다. 재귀함...

hyeon930

BOJ 2003 수들의 합2 문제풀이 짧은 시간 제한과 M의 엄청난 범위에 겁을 먹어서 고민을 많이 했지만 2중 반복문의 형태로 단순히 풀었더니 통과해버렸다. 하지만 이 문제는 알아보니 투 포인터를 사용하는 문제였다. 두 개의 포인터가 각자의 조건에 따라 움직이는 형태다. start는 합계가 M과 같거나 커질때 까지 계속 증가한다. end는 합계가 M과...