yoo.dev

투포인터 알고리즘이란 주어진 배열에서 연속합을 이용한 문제일때 사용할 수 있는 알고리즘. 보통 연속합으로 가능한 경우의 수를 구하거나, 그 길이를 구하거나 할때 사용된다. (대표문제 참고) start, end라는 변수를 배열의 인덱스로 사용하며 sum(arr[start:end])을 구하는 방법이다. 처음에 start = end = 0으로 시작하고, start arr[start:end]) 예를들어 배열의 연속합이 S가 되는 경우의 수를 구하는 문제에서는 무한루프를 돌며 sum이 S보다 작은 경우: sum += arr[++end] sum이 S와 같거나 클 경우: sum -= arr[start++] 를 해준 후, 무한루프는 start == end == len(arr)이 되면 빠져나온다. 저장할때는 파이썬의 s..

문제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 2003번(yuuj.tistory.com/160)과 비슷하게 투포인터 알고리즘으로 풀면 되는데, 주의해야할 점은 1. 합이 S와 일치하는 경우가 아닌, S이상일 경우이라는점 2. 가능하지 않을 경우엔 0을 리턴해야한다는점이다. 문제 제대로 읽기 !!!!! import sys N, S = map(int, sys.stdin.readline().split(" ")) arr = list(map(int, sys.stdin.readline().sp..