99클럽 코테 스터디 28일차 TIL 투 포인터

투 포인터 two pointer

2개의 포인터로 알고리즘의 시간 복잡도를 최적화하는데 쓰이는 개념입니다.

 

• 투 포인터
  • 1~N 범위의 자연수에서 연속된 자연수의 합이 N 이 되는 가짓수를 찾는 예제에서 투포인터를 활용해 보겠습니다.

투 포인터

• • N을 5라고 가정합니다.
  • 처음에 start_index와 end_index의 값을 맨 앞에 설정합니다. (start = 1, end = 1)
  • sum = start_index ~ end_index까지의 합이라고 정의할 수 있습니다.
  • 현재 sum = 1 이므로 N인 5보다 작습니다.
  • sum < N 일 경우는, end_index를 오른쪽으로 한 칸 이동합니다.  (start = 1, end = 2)
  • 이는, 연속된 자연수의 범위를 한 칸 더 확장한다는 의미입니다.
  • sum = 3 (1+2) 이므로 N인 5보다 작습니다.
  • end_index를 오른쪽으로 한 칸 이동합니다.  (start = 1, end = 3)
  • sum = 6 (1+2+3) 이므로 N인 6보다 큽니다.
  • sum > N 일 경우는, start_index를 오른쪽으로 한 칸 이동합니다.  (start = 2, end = 3)
  • 이는, 연속된 자연수의 범위에서 왼쪽 한 칸을 축소한다는 의미입니다.
  • sum = 5 (2+3) 이므로 N과 같습니다.
  • sum == N 이면 count를 1 증가시킵니다.
  • end_index != N 일 때까지 투 포인터 과정을 반복합니다.

 

• 투 포인터 이동 원칙

// sum < N
end_index++;
sum = sum + end_index;

// sum > N
sum = sum - start_index;
start_index++;

// sum == N
end_index++;
sum = sum + end_index;
count++;

728x90

느낀 점

• 시간 복잡도를 줄이기 위한 투 포인터 개념을 항상 기억하고 있어야겠다.

다음에 학습할 것

• 슬라이딩 윈도우

반응형

---

투 포인터를 사용하여 시간 복잡도를 최적화하자!