본문 바로가기

분류 전체보기

14. 다익스트라 알고리즘 알고리즘 공부 2019. 10. 3. 다익스트라 알고리즘 (데이크스트라) 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 (single source shortest path problem) 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 방향 그래프, 무방향 그래프 모두 상관없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다. 에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은의 시간 복잡도를 가졌다. 이후 우선순위 큐(힙 트리)등을 이용한 더욱 개선된 알고리즘이 나오며, 의 시간복잡도를 가지게 되었다.의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데의..
13. 카운팅 정렬(A.K.A 계수 정렬) 알고리즘 공부 2019. 9. 29. 카운팅 정렬 시간 복잡도는 O(n+k) (k는 데이터의 최댓값을 의미한다.) 카운팅 정렬은 가장 큰 데이터에 따라 효율이 좌지우지된다. 쉽게 설명하자면 특정 데이터의 개수(1이 두 개 있다면 2)를 데이터의 값에 대응하는 위치에 저장한 뒤, 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 만든 뒤, 거기서 데이터가 들어가야 할 위치를 찾아내는 정렬 알고리즘이다. 이 경우에 데이터의 최댓값을 k라 두면, 시간 복잡도는 O(n+k). 하지만, 만약 k가 억 단위를 넘어간다면? n이 아무리 작아도 동작시간이 크다. 반대로 k가 매우 작다면, 오히려 선형시간의 효과를 볼 수 있다. 즉, k가 작다는 조건이라면 매우 효율적인 정렬. 또한 카운팅 정렬은 배열을 사용하는 특성상, 정수라는 전제를 깔고 한다. 카운팅..
12. 기수 정렬 (A.K.A Radix sort) 알고리즘 공부 2019. 9. 29. 기수 정렬 출처: https://youtu.be/LyRWppObda4 기수 정렬 알고리즘 중 LSD를 시각화한 것. 시간 복잡도는 (k는 데이터의 자릿수를 의미한다.) 데이터끼리 직접적인 비교를 하여 정렬하는 알고리즘의 경우 시간복잡도는보다 작아질 수 없다. 기수 정렬은 자릿수가 있는 데이터(정수, 문자열 등)에서만 수행이 가능하며, 데이터끼리의 직접적인 비교 없이 정렬을 수행한다. 비교를 이용한 정렬이 아니기 때문에 k가 상수일 경우 시간복잡도가으로, 퀵정렬보다 빠른 시간복잡도가 나오는 것이 가능하다. 다만 이 알고리즘은 자릿수가 적은 4바이트 정수 등에서나 제대로 된 성능을 발휘할 수 있으며, 자릿수가 무제한에 가까운 문자열 정렬 등에 사용할 경우 오히려 퀵정렬보다 느릴 수 있고, 부동 소수점의 경우..
11. 쉘 정렬 알고리즘 공부 2019. 9. 29. 쉘정렬 삽입 정렬이 거의 정렬된 배열에서 최적의 성능을 내는 것에서 착안한 정렬 방법이다. 삽입 정렬을 띄엄띄엄한 간격으로 먼저 수행하고, 그 간격을 점차 좁혀나가면서 최종적으로는 거의 정렬된 배열을 삽입 정렬로 마무리하게 된다. 지저분해 보이지만 삽입 정렬의 특성을 잘 이용한 정렬로, 실제 성능은 힙 정렬 등에 버금갈 정도로 빠르다. 이 정렬 알고리즘의 핵심은 어떤 간격으로 정렬을 수행해 나갈 것이냐는 것인데, 간격에 따라 시간 복잡도도 제각각이다. 간격을 잘 선택하는 경우 까지도 가능하다고 하는데 일반적인 데이터 크기에 모두 적용할 수 있는 것은 아니다. 알고리즘 자체가 시간 복잡도가 명확하지 않고 퀵 정렬이나 병합 정렬에 비해 크게 나을 것이 없기에 일반적으로 쓰는 알고리즘은 아니다. 셸 정렬이란 ..
10. 병합 정렬(A.K.A merge sort) 알고리즘 공부 2019. 9. 28. 병합 정렬 개발자는 존 폰 노이만, 원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합해 나간다. 병합된 부분 안은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있다. 대표적인 분할 정복 알고리즘으로 존 폰 노이만의 천재성을 엿볼 수 있는 알고리즘이다. 성능은 아래의 퀵 정렬보다 전반적으로 뒤떨어지고, 데이터 크기만한 메모리가 더 필요하지만 최대의 장점은 데이터의 상태에 별 영향을 받지 않는다는 점'이다. 힙이나 퀵의 경우에는 배열 A[25]=100, A[33]=100인 정수형 배열을 정렬한다고 할 때, 33번째에 있던 100이 25번째에 있던 100보다 앞으로 오는 경우가 생길 수 있다. 그에 반해서 병합정렬은 정렬되어 있는 두 배..
9. 힙 정렬 알고리즘 공부 2019. 9. 27. 힙 트리란? 영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 완전 이진 트리의 형태를 띄고, 부모의 값은 항상 자식(들)의 값보다 크거나(Max heap), 작아야(Min heap)하는 규칙이 있다. 따라서 루트 노드에는 항상 데이터들 중 가장 큰 값(혹 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹 최솟값)을 O(1)안에 찾을 수 있다. 단순히 최댓값(최솟값)을 O(1)안에 찾기 위해서라면 "항상 완전 이진 트리의 형태여야 한다"는 조건을 만족시킬 필요는 없다. 완전 이진 트리를 사용하는 이유는 삽입/삭제의 속도 때문이다. 물론 '힙 트리'는 정의상 완전 이진 트리를 사용한다. 달리 다른 구조를 사용한다 해도 전혀 얻을게 없는 최적의 구조이기 때문이다..
8. 퀵정렬 알고리즘 공부 2019. 9. 27. 퀵정렬 찰스 앤터니 리처드 호어가 1959년에 개발한 알고리즘이다. 퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이다. C, C++, PHP, 자바 등 거의 모든 언어에서 제공하는 정렬 함수에서 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다. 방식은 적절한 원소 하나를 기준(피봇, pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 피봇을 옮겨 피봇보다 작은 것, 큰 것으로 나눈뒤 나누어진 각각에서 다시 피봇을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다. 이렇게 피봇을 잡고 이보다 작은 원소들을 왼쪽으로, 보다 큰 원소들을 오른쪽으로 나누는걸 partition step이라 한다. 퀵 정렬에도 이..
7. 삽입 정렬 알고리즘 공부 2019. 9. 25. 삽입 정렬 (Insertion Sort) 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식으로 사용하는 대표적인 알고리즘이다. k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식으로, 평균적으론 중 빠른 편이나 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크며, 앞의 예시처럼 작은 값이 뒤쪽에 몰려있으면 (내림차순의 경우 큰 값이 뒤쪽에 몰려있으면) 최악이다. 다만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입, 제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다. 그밖에도 배열이 작을 경우에 역시 상당히 효율적이다. 일반적으로 빠르다고 알려진 알고리즘들도 배열이 작을 경우에는 대..

티스토리툴바