solving/C, C++
[백준] 1181번 단어 정렬 (O(nlogn) 정렬 알고리즘, strcmp)
Seohyeong Lee
2022. 8. 29. 23:25
개념
정렬 알고리즘 중, 시간 복잡도가 O(n^2) 인 알고리즘만 사용해왔는데, 이 문제에서는 이런 알고리즘을 사용할 경우 시간 초과가 뜬다. 이를 해결하기 위해서는 O(nlogn) 정렬 알고리즘을 사용해야 한다는 것을 알게 되었다.
시간 복잡도가 O(n^2) 인 알고리즘은 n개의 원소를 바로 옆에 있는 원소와 비교해야 하기 때문에 n(n-1), 즉 O(n^2) 가 된다. 그렇다면 바로 옆 원소에 비교하는 방법을 안쓰면 된다!
O(nlogn) 정렬 알고리즘에 해당하는 분할 정복에 대해 알아보았다.
알고리즘 2일차 - O(nlogn) 정렬 , 병합 정렬(merge sort)
지난 시간에 배웠던 정렬 알고리즘들은 O(n^2) 시간인 반해, 앞으로 소개할 정렬 알고리즘은 O(nlogn)이다.참고로 O(nlogn)과 O(n^2)이 별로 차이가 안나보여도 엄청난 차이가 있다.직접 종이를 가져와
velog.io
분할 정복이란, 주어진 수열을 분할한 뒤 정복(원하는 순서로 바꿔서 배열) 하는 것이다.
우선 수열이 더 나눠지지 않을 때까지 나눈 뒤 (분할)
이것을 원하는 순서로 배열한다. (정복)