알고리즘
투 포인터
Themion
2022. 1. 22. 13:51
어떤 배열에서 합이 k인 성분 두 개를 찾을 때, 일반적으론 배열의 성분을 두 개씩 가능한 경우를 모두 고른 뒤 더해 합이 k가 되어야 하는지 확인해야 한다. 하지만 배열이 정렬되어 있다면, 배열의 왼쪽 끝과 오른쪽 끝 두 성분을 고른 뒤 합이 k보다 작다면 왼쪽 성분의 다음 성분을, k보다 크다면 오른쪽 성분의 다음 성분을 비교해 비교하는 횟수를 최소화할 수 있다.
https://www.acmicpc.net/problem/2467
2467번: 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -
www.acmicpc.net
https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net