[백준] 1181번 단어 정렬 (O(nlogn) 정렬 알고리즘, strcmp)

개념

정렬 알고리즘 중, 시간 복잡도가 O(n^2) 인 알고리즘만 사용해왔는데, 이 문제에서는 이런 알고리즘을 사용할 경우 시간 초과가 뜬다. 이를 해결하기 위해서는 O(nlogn) 정렬 알고리즘을 사용해야 한다는 것을 알게 되었다.

시간 복잡도가 O(n^2) 인 알고리즘은 n개의 원소를 바로 옆에 있는 원소와 비교해야 하기 때문에 n(n-1), 즉 O(n^2) 가 된다. 그렇다면 바로 옆 원소에 비교하는 방법을 안쓰면 된다! 

O(nlogn) 정렬 알고리즘에 해당하는 분할 정복에 대해 알아보았다.

 

참고 - https://velog.io/@chappi/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-2%EC%9D%BC%EC%B0%A8-Onlogn-%EC%A0%95%EB%A0%AC-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%ACmerge-sort

알고리즘 2일차 - O(nlogn) 정렬 , 병합 정렬(merge sort)

분할 정복이란, 주어진 수열을 분할한 뒤 정복(원하는 순서로 바꿔서 배열) 하는 것이다.

우선 수열이 더 나눠지지 않을 때까지 나눈 뒤 (분할)

이것을 원하는 순서로 배열한다. (정복)