오늘은 BFS문제를 풀고난 후 회고이다.
금주에 코딩테스트를 봐야해서 처음부터 다시 풀면서 준비 중이다.
오랜만에 DFS, BFS 문제를 푸는 중 복잡도에 대해 생긴 의문점을 정리한다.
문제는 n개의 숫자의 부호만 바꿔서 특정 수를 만드는 것이고 같은 수라고 index가 다르면 다른 경우로 취급한다.
내 생각으로 풀다 다른 사람의 풀이를 보았는데 의문점이 생겼다.
정석풀이를 보면 n개의 숫자에서 부호만 바꾼 모든 경우를 구해 더해서 가능 할때마다 가능한 경우의 수++ 해준다.
여기서 들었던 의문점은 이러면 2^n개의 경우가 생긴다는 것이다.
분명 더 줄이는 방법이 존재할 것이라 생각해 처음부터 모두 구하는 것은 고려하지 않고 풀었는데 당황했다.
내가 생각한 풀이는
나와야하는 값 = sum(a,b,c...) - sum(a',b',c'...)
니까 다르게 생각하면
나와야하는 값 = sum(a,b,c,a',b',c'...) - 2 * sum(a',b',c'...)
즉
2 sum(a',b',c'...) = sum(a,b,c,a',b',c'...) - 나와야하는 값
이렇게 풀었다 즉 -부호로 바꾼다는 것은 모두 더한 값에서 2번 빼주는 것과 같으니까 n개의 숫자중에서 필터링을 먼저 걸칠 수 있겠다는 것이였다.
어떤수의 2배 > 모든 수를 더한 값 - 나와야하는 값 이라면 그 수 포함하는 경우의 수는 없으니까 그 수들을 미리빼면 시간복잡도를 줄일 수 있지 않을까 하는 것이다.
먼저 걸린시간을 직접 비교했다.
기존풀이
내풀이
전체적으로 약간 더 빠르긴 하다. 확실히 조건을 생각해서 미리 불가능 한 원소를 제거하는 습관을 중요한 것 같다.
