효율성 테스트에서 낙제라면 고려해볼 방법

정확도 테스트에서는 맞는데 효율성 테스트에서 실패한다면 시간 복잡도를 줄여야 합니다.

트리나 그래프의 문제를 제외하면 대부분의 문제는 시간 복잡도 O(N^2)으로 풀 것입니다.

 

하지만 효율성이 좋지 못하다는 것은 O(N) 알고리즘이 존재할 가능성이 있다는 것입니다.

O(N^2) => O(N) 바꾸는 알고리즘

• 스택
• 해시
• 그리디
• 투 포인터

모든 문제에 이 알고리즘들이 적용되지는 않겠지만 배열을 사용하는 문제라면 이 세 알고리즘들로 시간 복잡도를 줄일 수 있을 지도 모릅니다.