Math

프로그래머스 연속된 부분 수열의 합 문제 바로가기 Bruteforce Simple is best라는 생각에 바로 bruteforce로 풀어보았다. 결과는… 시간초과 시간 복잡도가 $ O(n^{2}) $ 이기에 n이 조금만 커져도 기하급수적으로 증가한다. #include <string> #include <vector> #include <numeric> using namespace std; vector<int> solution(vector<int> sequence, int k) { vector<int> setting(k, 1); vector<int> answer; for (int start=0; start<sequence.size(); start++){ vector<int> temp; int i=start; while (reduce(temp.begin(), temp.end()) < k){ temp.push_back(sequence[i]); if (reduce(temp.begin(), temp.end()) == k){ if (setting.size() > temp.size()){ setting = temp; answer = {start, i}; } } i++; } } return answer; } 테스트 1~5 통과 테스트 6 이후 → 시간 초과 Two Pointer 어떻게하면 불필요한 연산을 줄일 수 있을까 고민했다. 사실 스스로 그 답을 찾아내진 못했고, Two Pointer이라는 힌트를 얻었다. Two Pointer는 starting 위치에 따라서 연산을 새로 시작하지 않고 기존의 계산 결과를 활용한다. 따라서 bruteforce에 비해서 현격히 적은 시간을 소요로 한다. 시간 복잡도: $ O(n) $ ...