3/17
투 포인터(boj 2470 두용액) https://www.acmicpc.net/problem/2470 투포인터란? 1차원 배열이나 리스트에서 2개의포인터를 움직이며 이중 for문(O(N^2)으로 처리할 작업을 선형 시간(O(N))에 효율적으로 해결하는
투 포인터(boj 2470 두용액)
https://www.acmicpc.net/problem/2470
투포인터란?
1차원 배열이나 리스트에서 2개의포인터를 움직이며 이중 for문(O(N^2)으로 처리할 작업을 선형 시간(O(N))에 효율적으로 해결하는 알고리즘입니다.
주로 정렬된 배열에서 연속된 부분 배열의합, 특정 두 수의 합 등을 구할 때 유용하게 사용된다.
활용 예) 특정 합을 가지는 부분 연속 수열 찾기, 두 수의 합이 X가 되는 쌍 찾기
투포인터는 유동적인 구간 길이를 다룰때 주로 사용
슬라이딩 윈도우는 고정된 크기의 구간을 이동하며 처리하는데 특화