시간초과를 획기적으로 줄이는 방법이 무엇일까?
조건에 따라 다르지만 이 개념은 O(n^a) 을 O(n^a/2) 로 줄이는데 의의가 있다.
두 포인터 관련 문제를 풀다가 도저히 이해가 안가는 문제를 발견했다.
첫 번째로 드는 생각은 O(n^4) 말고 답이 없었다. 이유인 즉슨 하나하나 골라야만 합이 맞는지 알 수 있다는 점.
하지만 여기의 알고리즘 분류가 중간에서 만나기 였고 이 개념을 모르면 풀 수 없다는 생각이 들었다.
내가 본 강의
https://dasu.tistory.com/35
https://www.youtube.com/watch?v=57SUNQL4JFA
이 문제가 왜 O(n^2) 인 것인가? 그것은 문제의 정답이 합이 0이되는 각 원소를 추출하는 것이 아니라 0이되면 경우의 수만 찾는 것이다.
모든 원소를 찾아야한다면 O(n^4) 밖에 답이 없겠지만 이 문제에서는 다르다.
총 4개의 배열을 2로 나눈 2개의 배열로 만드는 과정은 O(2*n^2) 이다.
A와 B 배열을 이중for문으로 다 더해 나온 수를 X라는 배열에 넣으면 되기 때문이다.(C와 D 배열도 동일하기에 2를 곱한다.)
여기서 시간초과는 확실히 줄어듦을 알 수 잇었다.
X와 Y에서 합이 0이 되는 과정은 이분탐색을 써야 했지만 worstCase가 O(n^2)임이 자명하기에 이 문제를 풀 수 있었다.
나름 신박한 개념이라서 복습 겸 글을 올려보았다.
YOLO