알고리즘/Two Pointer 썸네일형 리스트형 [Binary Search && Two pointer]BJ_3151, 합이 0 [문제의 접근] 수학 논리적으로 생각해 보았을 때, 위의 문제는 문제의 복잡도가 $O(n^3)$ 인 문제로 N이 충분히 작다면 Bruteforce로 풀리는 문제라고 생각해 볼 수 있다. 그런데 N이 10000 으로 주어졌기 때문에 Bruteforce는 불가능하다. 그렇다면 $O(n^2 log(n)$ 이나 $O(n^2)$의 접근법을 생각해 보아야 한다. 전자의 경우는 시간 초과가 날 것 같은 우려가 있지만, 제한 시간이 4초 이기 때문에 가능성이 있어 보인다. 방법론은 Lower_bound 와 Upper bound를 이용해서 푸는 방법이다. 후자의 경우는 Two-pointer를 이용하면 될 것 같다. 세 수의 합이 0이 되는 조건을 찾는 문제인데, 합은 숫자의 크기에 의존하고 수의 크기는 정렬이 가능하므로.. 더보기 [Two-Pointer] BJ_2230, 수 고르기 [문제의 접근] 두 수를 선택하고, 두수의 차이가 M이상이면서 가장 작은 차이를 구해야 한다. 어떻게 접근해야 할까? Bruteforce로 접근하면 가장 쉽게 접근법을 생각할 수 있다. 즉 모든 경우의 수를 비교해 보는 것이다. N개의 수 중에서 2개의 수를 임의로 선택해야 하기 때문에, $O(N^2)$ 시간 복잡도가 나온다. For 문을 계층적으로 2번 돌린다고 생각하면 쉽다. 첫번째 수를 정하고 N-1개 비교, 2번째 수를 정하고 N-2개 비교,.... 현재 N이 1,000이하라면 충분하겠지만, 주어진 값은 N이 100,000 으로 주어져 있다. 연산량은 $10^{10}$으로 대략적인 1초의 연산량 $10^8$을 초과하므로 시간초과다. 그럼 어떻게? $O(n\log_{2}{n})$의 접근이나, $O(.. 더보기 이전 1 다음
