BuildConfig (1) 썸네일형 리스트형 [TIL] 24.03.07 알고리즘, 사이드 프로젝트 1. 알고리즘 문제 해결 가운데를 말해요(백준 1655): 발상해내는데 꽤 걸린 문제다. 매번 정렬을 하면서 풀자니 O(n^2 log n)으로 시간 초과가 날 것이다. 일반적인 정렬 알고리즘이 아닌 Radix Sort나 Counting Sort를 써도 원소를 입력받을 때마다 반복한다면 O(n^2)을 넘기 때문에, 이 또한 불가능하다. 전체 동작 시간이 O(n log n) 선에서 끝나야 했다. 그래서 매번 리스트에 대해 이진 탐색으로 들어갈 자리를 찾아 삽입하고, 중앙값을 출력하게 해 볼까도 생각했다. 하지만 배열 기반 리스트라면 삽입 과정에서 O(n)이 걸리고, 연결 리스트라면 이진 탐색이 힘들어 보였다. 어쨌든 입력은 n번을 받아야하고, 결국 입력을 받으면서 매번 O(log n)의 연산을 통해 중앙값을.. 이전 1 다음
