TIL : 23-06-04

오늘 한 일

---

• 투 포인터
• 코딩 도장 happy number

투 포인터

1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태

• 투 포인터 알고리즘(Two Pointers Algorithm) 또는 슬라이딩 윈도우(Sliding Window)라고도 부름

왜 사용할까?

• 알고리즘을 풀 때 완전탐색으로 해결하면 시간초과가 나는 문제가 존재함

• ex) n칸의 1차원 배열이 있을 때 부분 배열 중 그 원소의 합이 m이 되는 경우의 수를 구해야 한다면?

• 모든 경우의 수를 다 고려하면 시간복잡도는 O(n^2)이 됨

• 시간 초과의 우려가 있음

• 보통 위와 같은 경우에 사용하는 알고리즘

어떻게 사용할까?

1. 현재 부분 배열의 시작과 끝을 가리키는 포인터 변수 2개 선언 (보통 start, end로 선언)

2. start = end = 0으로 초기화, 이후 항상 start ≤ end를 만족해야 함

   start == end일 경우 크기가 0인(=아무것도 포함하지 않는) 부분 배열을 뜻함

3. 다음의 과정을 start < n일 동안 반복

   1. 만약 현재 부분합이 m 이상이거나, 이미 end == n이면 start++
   2. 그렇지 않다면 end++
   3. 현재 부분합이 m과 같으면 결과 ++

   → start와 end를 무조건 증가시키면서 도중의 부분배열의 합이 정확히 m이 되는 경우를 카운트함

출처 : CS스터디_짐깅