본문 바로가기

Algorithm23

[Algorithm] 그래프 유니온 파인드 (Union-Find) 유니온 파인드 여러 노드가 있을 떄 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘 -> 그래프 문제에서 부분 알고리즘으로 많이 사용된다. 유니온 파인드의 원리 1. 초기화 2. union 연산 수행 3. find 연산: 자신이 속한 집합의 대표 노드를 찾는 연산 이러한 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타난다. 경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형하여 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다. 참고 자료 https://www.inflearn.com/course/lecture?cou.. 2023. 4. 7.
[Algorithm] 그래프 기본 알고리즘 8-1 그래프의 표현 8-2 유니온 파인드 : 그래프의 사이클이 생성되는지 판별하는 알고리즘 8-3 위상 정렬 조건: 싸이클이 없어야 한다. 방향이 있는 그래프여야 한다. 노드를 정렬해주는 알고리즘 정렬 결과가 꼭 1개가 아니다. 위상 정렬을 이용한 예제. 1) 수강신청 수1->수2를 들어야 하는 방향성이 있어야 한다. 8-4 다익스트라 : 시작점이 있고 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘 but, 음수간선 X 8-5 벨만 포드 :시작점이 있고 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘 음수간선 O (있어도 된다) 8-6 플로이드 워셜 : 시작점이 없음 but , 시간복잡도가 안 좋음. -> 모든 도시간의 최단거리를 구해야 한다(도시 개수는 100개 이하) 시간.. 2023. 3. 31.
[Algorithm] 병합 정렬 (Merge Sort) 알고리즘 병합 정렬 분할 정복 (Divide and Conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합치는 알고리즘 시간복잡도 : O(nlogn) 핵심 이론 왜 시간복잡도가 O(nlogn)인가? 그림에서는 데이터의 개수가 8. 정렬 3번(log 8)만에 정렬된 데이터가 나옴 N번의 데이터 엑세스가 log n번 일어나기 때문에 시간복잡도가 O(nlogn)이다. 수행 방식 1. 그림에서 최초로는 8개의 그룹으로 나눈다. 2. 2개씩 그룹을 합치며 오름차순으로 정렬한다. -> (32,42), (24,60), (5,15), (45,90) 3. 2개씩 그룹을 합치며 다시 오름차순으로 정렬한다. -> (24,32,42,60) , (5,15,45,90) . . . 이런 식으로 병합 정렬 과정을 거친다... 2023. 3. 27.
[Algorithm] 퀵 정렬 (Quick Sort) 알고리즘 퀵 정렬 (Quick Sort) 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미친다. 분할 정복(Divide and Conquer)와 재귀 알고리즘을 이용한 정렬 알고리즘이다. 파이썬의 list.sort()함수처럼 기본으로 지원되는 내장 정렬 함수는 퀵 정렬을 기본으로 한다. 시간 복잡도: O(nlog(n)) 퀵 정렬 과정 1. 데이터를 분할하는 pivot을 설정한다. (그림의 경우 가장 오른쪽 끝을 pivot으로 설정). 2. pivot을 기준으로 다음 a~e과정을 거쳐 데이터를 2개의 집합으로 분리한다. 2-a. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으.. 2023. 3. 26.

티스토리툴바