반응형 CS/Datastructure & Algorithm30 [알고리즘] - 플로이드-와샬 알고리즘 그래프에서 정점끼리의 최단 경로를 구하는 방법은 여러가지가 있다. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 하나의 목적지로 가는 모든 정점까지의 최단 경로를 구하는 문제 모든 최단 경로를 구하는 문제 (플로이드-와샬) 플로이드-와샬(Floyd-Warshall Algorithm) 플로이드 와샬 알고리즘은 동적 계획법(DP)의 한예로, 로버트 플로이드가 1962년에 발표했다. 이 알고리즘의 삼중 for 반복문의 공식은 Peter Ingerman 이 설명했다. 변의 가중치가 음수 또는 양수인 (음수 사이클이 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면, 모든 정점 쌍간의 최단 경로의 길.. 2022. 7. 16. [알고리즘] - 카운팅 정렬(Counting Sort / 계수 정렬) 카운팅 정렬은 말 그대로 정렬을 위한 알고리즘입니다. 수 많은 알고리즘 중에도 시간 복잡도가 O(n) 으로 효율이 좋습니다. 보통 정렬 알고리즘 중에서 빠른 건, 흔히 알고 있는 퀵정렬, 힙정렬, 합병정렬 등이 있다는 걸 알고 계실겁니다. 이들의 평균 복잡도는 O(nlogn) 인 것에 비하면 카운팅 정렬이 성능이 좋다는 걸 알 수 있습니다. 사실 정렬은 데이터끼리 직접 비교하는 경우가 많습니다. 그렇기 때문에 데이터를 직접 비교한 정렬 알고리즘일 경우, O(nlogn) 을 갖는 시간 복잡도 보다 작아지는 건 어렵습니다. 카운팅 정렬은 어떻게 이를 극복한 것이고, 그럼에도 불구하고 퀵 정렬 같은 알고리즘을 더 많이 사용하는 이유는 무엇일까요? 아래 블로그에 카운팅 정렬하는 방법에 대해서 잘 설명이 되어 있.. 2022. 6. 16. 분할 정복 분할 정복 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다. 대표적 예는 정렬 알고리즘 중에서 퀵, 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제가 대표적입니다. 분할정복법의 설계전략? 분할 : 문제 사례를 하나 이상의 작은 사례로 분할(Divide) 합니다. 정복 : 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 재귀를 사용합니다. 병합 : 필요하다면, 작은 사례에 대한 해답을 통한(Combine)하여 원래 사례의 해답을 구합니다. 분할정복법의 장단점? 장점 Top-down 재귀 방식으로 구현하기 때문에 코드가 직관적입니다. 문제를 나누어 해결한다는 특징 상 병렬적으로 문제를 해결 단점 재귀 함수 호출로 오버헤드가 발.. 2022. 6. 8. 투 포인터 (Two Pointer) 투포인터 정렬된 리스트를 두 개의 포인터를 가지고 순차적으로 접근하면서, 두 포인터 구간의 값이 타겟 값과 같을 때까지 포인터를 조작하는 기법을 말합니다. 투포인터 알고리즘에 대해서는 검색만 해도 어떻게 로직이 돌아가는 지 쉽게 이해할 수 있을 거 같아서 저는 두 개의 포인터를 함께 활용할 때 얻을 수 있는 이점이 무엇인 지에 대해서 글을 써볼까 했습니다. 사실 이점은 1차원 배열을 한 번의 루프로 문제의 원하는 결과를 얻을 수 있다는 점입니다. 코딩테스트 문제마다 다르겠지만, 저는 수들의 합2(2003) 문제를 가지고 비교를 해보았습니다. 결과는 사실 복잡도에서 큰 차이를 못느꼈습니다. 하지만, 새로운 알고리즘 유형이니 익힐 필요성은 있다고 생각했습니다. 그리고 투포인터 알고리즘은 구현 방식이 문제 별.. 2022. 6. 7. 이진탐색 == 이분탐색 (Binary Search) 이란? 이진탐색 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. (정렬된 배열, 리스트에 적합한) 배열의 중앙에 있는 값을 조사하여, 찾고자하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는 지를 알아내어 탐색의 범위를 반으로 줄입니다. 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있습니다. 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합합니다. 이진탐색의 시간 복잡도 한 번 확인할 때마다 확인하는 원소의 개수가 절반 씩 줄어든다는 점에서 시간 복잡도가 O(logN)입니다. 예시 1. 10억 명의 어떠한 이름이 저장되어있는 배열에서 이진 탐색을 이용해 특정한 이름을 찾는 경.. 2022. 6. 3. 최단거리 문제에 대한 고찰 최단 경로 문제는 가중치 없는 그래프에서는 보통 두 정점을 잇는 가장 적은 간선의 개수를 뜻합니다. 반대로 가중치가 있는 그래프에서는 두 정점을 잇는 간선들의 가중치의 합 중 최소 가중치 합을 의미합니다. 알고리즘 공부하고, 코딩테스트 문제를 접하다보면? 가중치 없는 그래프(unweighted graph)인 경우 BFS를 사용하고, 가중치가 0과 1이 존재할 때 역시 BFS를 사용한다고 생각합니다. 그리고 가중치가 여러 개가 존재한다면 다익스트라 알고리즘을 사용하라고 합니다. 이번 주제에선, 왜 최단거리에선 DFS를 사용하지 않고 BFS를 사용하는 지? 와 간선이 0과 1일 때는 다익스트라 알고리즘을 사용하기보단, 0-1 알고리즘을 사용하는 지? 에대한 설명을 드릴 생각입니다. 최단 경로를 탐색할 때 D.. 2022. 4. 25. 너비 우선 탐색(Breadth-First-Search) BFS 그래프 전체를 탐색하는 방법 중 하나로, 루트 노드 또는 다른 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점을부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 순회함으로 써 노드를 넓게(wide)하게 탐색을 합니다. 더 설명하자면, BFS는 해를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색(Uniformed search)입니다. 달리 말하자면, 목표에 대한 고려없이 목표가 발견될 때까지 전체 트리 또는 그래프를 전부 탐색하고, BFS는 휴리스틱을 사용하지 않습니다. (반대로 휴리스틱을 사용하는 알고리즘은 ex) Greedy best-first search 또는 A*) 👇 search 의 두 분류 더보기 Uniformed search .. 2022. 4. 24. 트리의 지름 구하기 [증명] 트리의 지름 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은, 먼 두 정점을 연결하는 경로를 의미합니다. 선형 시간안에 트리에서 지름을 구하는 방법은 아래 Flow를 기억해두시면 좋습니다. 트리에서 임의의 정점 x를 잡습니다. 정점 x에서 가장 먼 정점 y를 찾습니다. (dfs / bfs 사용) 정점 y에서 가장 먼 정점 z를 찾습니다. (dfs / bfs 재사용) 이렇게 위 flow 대로 생각하면, 트리의 지름은 정점 y와 정점 z를 연결하는 경로가 됩니다. 여기서 이렇게하면 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 일컫게 됩니다. 증명을 하자면, 트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정하겠습니다. 임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y.. 2022. 4. 22. 이전 1 2 3 4 다음 반응형
