3-SUM1 [1] 3-SUM algorithm 3-Sum algorithm은, 세 숫자의 합이 특정 조건을 만족하는 모든 경우의 수를 탐색하는 알고리즘이다. 2-Sum 알고리즘도 있다. 애는 Linear Time에 해결할 수 있고, 이는 Hash-table을 이용하여 문제를 해결한다. 2-Sum algorithm을 nlogn의 시간복잡도로 해결하는 방법으로 sliding-window 방식이 있는데, 3-Sum algorithm은 이 방식을 한번 더 감싼 것에 불과하다. 예시 문제를 보면서 이해해보자. 주어진 문제에선 용액의 특성값을 나타내는 N개의 정수가 순서대로 제공된다. 그 때, 세 특성값의 합이 0에 가장 가까운 조합을 찾는것이 목적이다. 그냥 단순히 Brute-force로 문제를 해결하게 되면, for문을 3개 돌려서 모든 조합에 대해서 정답.. 2020. 4. 11. 이전 1 다음
