알고리즘 최강자 찾기

가장 강한 알고리즘을 찾아보자

알고리즘 문제를 풀다가 갑자기 궁금해져서 알고리즘 별로 시간복잡도와 공간복잡도 측면에서 가장 우수한 것이 무엇인지 찾아보았다 

역시 문제 상황마다 조건이 달라서 '모든 알고리즘 중 1등'이런 건 없었다 

물론, 시간복잡도가 가장 낮은 대표적인 상수시간알고리즘같은 건 논외로 했다(코딩테스트에 단독으로 안 나오니까) 

 

분야별로 살펴본 알고리즘 최강자 

정렬 알고리즘 

• 시간 복잡도 측면에서 퀵소트(QuickSort)가 평균적으로 가장 우수
• 최악의 경우에는 힙소트(HeapSort)가 우수
• 공간 복잡도 측면에서는 병합정렬(MergeSort)이 우수

그래프 알고리즘

• 최단경로를 찾는 문제에서는 다익스트라(Dijkstra) 알고리즘이 가장 효율적
• 최소 스패닝 트리(Minimum Spanning Tree)를 찾는 문제에서는 크루스칼(Kruskal) 알고리즘이 가장 효율적

문자열 알고리즘

• 문자열 매칭 문제에서는 KMP 알고리즘이 가장 효율적
• 문자열 정렬 문제에서는 사전순으로 정렬하는 라디크스(Radix) 정렬 알고리즘이 가장 효율적

동적 계획법 알고리즘

• 0/1 배낭 문제와 같은 조합 최적화 문제에서는 동적 계획법(Dynamic Programming) 알고리즘이 가장 효율적

그 외의 알고리즘

• 분할 정복(Divide and Conquer) 알고리즘은 병합정렬(MergeSort)과 같은 정렬 알고리즘에서 굿 
• 퀵소트(QuickSort)와 같은 알고리즘에서 평균적으로 빠른 실행 시간
• 이진 탐색(Binary Search) 알고리즘은 정렬된 배열에서 특정 값을 찾는 문제에서 최적의 알고리즘
• 해시 테이블(Hash Table)은 검색과 삽입 모두 O(1)의 상수 시간 복잡도를 가지기 때문에 많이 사용

뭔가 써놓고 보니 좀 뻔하고 기존에 알고 있는 내용이기는 한데 

각 알고리즘을 쓸 때 그 분야 최강자를 푸는 느낌일거같다