• 2개의 포인터로 알고리즘의 시간 복잡도를 최적화함

[006] 연속된 자연수의 합 구하기

• https://www.acmicpc.net/problem/2018
• N의 최댓값이 매우 커서 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야함 → 투 포인터
• 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현
• 투 포인터 이동 원칙
  • sum > N: sum = sum - start_index; start_index++;
  • sum < N: end_index++; sum = sum + end_index;
  • sum == N: end_index++; sum = sum + end_index; count++;

[007] 주몽의 명령

• https://www.acmicpc.net/problem/1940
• 정렬하면 문제를 좀 더 쉽게 풀 수 있음
  • N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 문제 없음
• 투 포인터 이동 원칙
  • A[i] + A[j] > M: j--; // 번호의 합이 M보다 크므로 큰 번호 index를 내림
  • A[i] + A[j] < M: i++; // 번호의 합이 M보다 작으므로 작은 번호 index를 올림
  • A[i] + A[j] == M: i++; i--; count++; // 양쪽 포인터를 모두 이동시키고 count를 증가시킴

[008] ‘좋은 수’ 구하기

• https://www.acmicpc.net/problem/1253
• 좋은 수 하나를 찾는 알고리즘의 시간 복잡도가 최소 O(nlogn)이어야함
• 정렬(O(nlogn)), 투 포인터 알고리즘 사용(O(n))
• 투 포인터 이동 원칙
  • A[i] + A[j] > k: j--;
  • A[i] + A[j] < k: i++;
  • A[i] + A[j] = k: count++; 프로세스 종료