이전에 시간 복잡도 O(N^2)인 정렬 알고리즘들에 대해 포스팅했었는데요. 오늘은 시간 복잡도가 O(NlogN)인 정렬 알고리즘에 대해 알아보려 합니다! 시간복잡도가 O(NlogN)인 대표적인 정렬에는 퀵 정렬, 합병 정렬, 힙 정렬이 있습니다. 1. 퀵 정렬 분할 정복(divide and conquer)기법을 사용한 정렬로, 평균적으로 아주 빠른 성능을 갖는 알고리즘입니다. 정렬 방법 1. 주어진 리스트에서 하나의 원소를 고른다. (피벗) 2. 피벗을 기준으로 두 개의 파티션으로 분할한다. 파티션 1: 피벗보다 작은 원소, 파티션 2: 피벗보다 큰 원소 3. 분할된 파티션에 대해서도 리스트의 크기가 0 혹은 1이 될 때까지 1,2 과정을 반복한다. 소스코드(파이썬) def quick_sort(a: li..
안녕하세요 ㅎㅎ 오늘은 알고리즘 문제풀이 시 가장 많이 사용하는 리스트(list), 집합(set), 딕셔너리(dictionary) 메서드의 시간 복잡도를 정리해보려 합니다. 본격적인 시작전에 왜 여러 자료형들의 메서드에 대한 시간 복잡도를 알아야 하는지 짚고 넘어갑시다! 보통 알고리즘 문제 풀때 리스트로 큐를 구현하시는 분들이 많으실 텐데요. 여기 큐를 pop하는 반복문을 돌려서 풀어야 하는 문제가 있다고 가정해 봅시다. 만약 리스로 큐를 구현했다면 다음과 같이 나타낼 수 있는데요. 리스트의 경우 마지막 원소를 pop하는 연산의 시간 복잡도는 O(1)이지만, 그 외의 원소를 pop할 경우 원소를 한 칸씩 당기기 때문에 시간 복잡도는 O(N)이 되게 됩니다. 결국 반복문과 중첩되니 전체적인 시간 복잡도는 ..
보통 코딩 테스트를 볼 때, 조금 난이도가 있는 문제는 알고리즘의 정확성 테스트뿐만이 아니라 효율성 테스트를 함께 검토하게 됩니다. 즉 알고리즘을 잘 구현해서 정답을 잘 맞춰도 효율이 좋지 못하면.. 효율성 테스트를 통과하지 못하게 되는데요. 이럴 경우, 정확성 부분에만 부분점수를 받을수도, 아예 점수를 받지 못할 수도 있습니다. 이 효율성테스트라는 것이 시간 복잡도를 의미합니다. 결국 이 알고리즘이 얼마나 문제를 빨리 풀어낼 수 있는지 체크하는 것이라 할 수 있습니다. 저 같은경우, 딱 문제를 보고 직관적으로 생각나는 방법으로 풀면 무조건 시간 복잡도가 O(n^2)이 나오더라구여 ㅜㅜㅜ 보통 효율성 테스트를 통과하기 위해서는 시간복잡도가 O(nlogn)이 되어야 하는 것 같습니다. 알고리즘을 처음 공부..