목록투 포인터 (6)

반갑습니다!

[알고리즘] 투 포인터

개념 잘 모르고 있다가 투포인터라는 알고리즘에 대해 듣게되어 공부할겸 포스팅을 작성한다. 일반적으로 연속된 수들의 합을 구할 때 자주 사용된다고 한다. 기본 원리는 두 개의 인덱스를 이용하여 두 인덱스의 범위를 조절하여 정답을 찾는 방식이다. 예시를 보며 이해해보자. 크기가 10인 자연수 배열이 있고, 연속된 숫자들의 합이 5가 되는 경우의 개수를 찾아야한다고 가정하자. 투포인터 알고리즘에서는 인덱스를 2개로 지정한다. s와 e라고 하자. 그리고 두개의 인덱스를 통한 범위는 [s, e)라고 가정할 것이다. 초기에는 s = 0, e = 0이고, [s, e) 범위 내의 숫자의 합은 0이므로 M보다 작다. 따라서 e의 값을 1 증가시킨다. 위 그림의 경우 [s, e) 범위 내 숫자의 합은 1이 되었지만 아직도..
CS 2020. 4. 17. 00:07
이전 Prev 1 2 Next 다음