2️⃣ 개발 지식 B+/코딩 테스트10 코테 시간초과 분석 방법 코딩테스트에 관심있다면, 시간 복잡도 Big-O에 대해 한번쯤은 들어봤을 것이다. 필자 또한 리스트 탐색은 O(n), 정렬이 된 경우 이분탐색 시 O(log(n))까지 최적화 가능하다는 것은 학습했다. 하지만 문제를 보고 어쩔 때 최적화가 필요할지 판단이 서지 않았었다. 그냥 시간을 줄일 수록 좋은거 아닌가? 라고 막연히 생각했다. 이때 백준 정렬 1~3 문제 간의 비교를 통해 왜 어느 문제는 O(N^2) 으로 통과가 되고, 다른 문제는 O(n*log(n))까지 최적화가 필요한지 알아보겠다. 같은 정렬 문제가 아니다. 다음은 정렬과 관련된 3문제를 캡쳐했다. 박스 표시한 곳을 보면 각기 다른 시간/메모리 제한 그리고 입력개수(N)이 다름을 확인할 수 있다. 정렬 관련 로직은 다양하고 각 상황에 맞는 정.. 2024. 8. 14. 이전 1 2 다음
