[알고리즘] 투포인터

투포인터

💡 언제 쓸까?

어떤 특정 조건을 만족하는 연속 구간을 구할 때(구간의 처음과 끝이 중요할 때)

• 완전탐색으로 풀면 시간초과 뜰 것 같은 경우, 투포인터로 좀 더 효율성을 높일 수 있지 않을까 생각해보자

💡 포인트

• 2개의 포인터(배열의 인덱스)를 사용 : start, end
• 조건에 맞춰 start++ / start--, end++ / end-- 해나간다.
  • 조건에 따라 포인터를 이동시키기 때문에 for문 보다는 while문 사용
  • while문의 수행 조건에 start <= end / start < end 포함
    • end가 배열의 맨앞에서 시작하는 경우, end < 배열길이도 추가
• start, end 모두 배열의 맨앞에서 시작하는 경우도 있고, start는 배열의 맨앞 + end는 배열의 맨 끝에서 시작하는 경우도 있다.(문제에 따라 다름)
• 문제 유형은 크게 2가지이다.
  • 대상이 되는 배열이 1개인 경우
    • 백준 1806 부분합
  • 대상이 되는 배열이 2개인 경우
    • 백준 1208 부분수열의 합2

💡 참고문제

2470 두 용액
1806 부분합