koucop의 개발탐방기 koucop의 개발탐방기

이번에는 백준 알고리즘의 1806번 문제, "부분합"을 풀어보도록 하자 일단 이번 문제에서 입력은 수열의 길이 N 과 연속된 수들의 합의 판단기준이 될 S 가 주어지고, 두번째 줄에는 해당 수열이 주어진다. 출력으로는 부분합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 출력하면 된다. 문제 설명 자체는 간단하지만, 과정이 살짝 복잡해 보인다. 이번 문제에서 사용되는 알고리즘은 투포인터이다. 투포인터 알고리즘이란, 두개의 포인터를 두고 그 포인터들을 이동 시키면서 답을 구해나가는 과정이다. 밑에 그림을 보면서 이해해 보도록 하자. 일단, 예제에서 주어진 것과 같이 N = 10 S = 15 수열 : 5 1 3 5 10 7 4 9 2 8 이 있을때, 처음위치(0)인 부분에 두개의 포인터를 놔둔다.(sum..