Major/Algorithms
-
[알고리즘] 힙 정렬 (Heap Sort)Major/Algorithms 2022. 6. 4. 20:56
이진 힙 (Binary Heap) : 힙 조건을 만족하는 완전 이진 트리 : 힙 조건 : 각 노드의 우선순위(priority)가 자식 노드의 우선 순위보다 높다 – 최대 힙(Maximum Heap): 가장 큰 값이 루트에 저장 – 최소 힙(minimum Heap): 가장 작은 값이 루트에 저장 ex) n개의 노드를 가진 힙 – 완전 이진 트리이므로, 힙의 높이가 log2n이며, 노드들을 빈 공간 없이 배열에 저장 힙의 노드 관계 힙에서 부모와 자식의 관계 – A[i]의 부모 = A[i/2] (단, i가 홀수이면 i/2에서 정수 부분만) – A[i]의 왼쪽 자식 = A[2i] – A[i]의 오른쪽 자식= A[2i+1] 힙 정렬 (Heap Sort) 루트에 가장 큰 수가 있는 최대 힙을 정렬한다고 하자 ..
-
[알고리즘] 쉘 정렬(Shell Sort) 알고리즘Major/Algorithms 2022. 6. 4. 18:36
버블정렬이나 삽입정렬은 이웃하는 원소의 자리바꿈이다 하지만 쉘 정렬은 그룹화를 시켜 정렬하는 방식으로, 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 이동시키고 앞부분의 큰 숫자는 뒷부분으로 이동시킨다 예를 들어 숫자가 이렇게 있다고 하자 이 배열을 간격 5로 그룹화를 하면 이렇게 그룹이 지어진다, 그럼 여기서 이제 그룹1 안에서 삽입정렬, 그룹2 안에서 삽입정렬을 해주면된다 그룹별 정렬을 하고 나면 이렇게 정렬이 되고, 5의 갭차이로 그룹을 나누었으니 다음에는 3의 갭차이로 그룹을 나누어 정렬한다 그리고 마지막에는 1의 갭차이로 그룹을 나누어 정렬한다 (그냥 삽입정렬과 동일) 알고리즘 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A 1. for each gap h = [ h0>h1>....
-
[이취코] Ch09-3. 최단경로 / 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)Major/Algorithms 2022. 5. 25. 11:05
플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) - 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우에 사용할 수 있는 알고리즘 - 2차원 리스트에 '최단 거리' 정보를 이용한다 - 다이나믹 프로그래밍 플로이드 워셜 알고리즘은 단계마다 해당 노드를 거쳐가는 경우를 고려해 최단경로를 비교한다 예시를 들어 말하자면 A, 1, B 노드가 있고 A에서 B까지 가는 최단 경로를 구한다고 할 때 노드 1을 거쳐가는 경우(A-1-B)와 A에서 B로 가는(A-B) 경로를 비교해 더 작은 것을 최단 경로로 선택하는 것이다 점화식으로 표현하자면, a에서 b까지 가는 경우의 최단 거리는 'a에서 바로 b로 가는 경우' 와 '노드 k를 거쳐 가는 경우' 중 작은 값이다 예시를 통해 구체적..
-
[이취코] ch06-4. 계수 정렬 (Count Sort)Major/Algorithms 2022. 5. 3. 11:54
계수 정렬 (Count Sort) : 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 계수 정렬은 다른 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 알고리즘)이 아니다 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다 예시를 통해서 알아보도록 하자 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 초기 데이터가 이렇게 있다고 해보자 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 담길 수 있는 리스트를 선언한다 여기서 가장 큰 데이터가 9 이고 가장 작은 데이터가 0 이므로 모두 담을 수 있는 크기가 10 인 리스트를 선언하면 된다 계수정렬에서 데이터의 값은 새로 선언한 리스트의 인..
-
-
[알고리즘] 최소신장트리, 프림(Prim) 알고리즘Major/Algorithms 2022. 4. 19. 21:39
신장 트리 신장트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다 이 때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다 따라서 이러한 그래프를 신장 트리라고 부르는 것이다 신장트리 예시는 다음과 같다 최소 신장 트리 우리는 다양한 문제 상황에서 가능한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 설치한다고 생각해보자 2개의 도시 A,B를 선택했을 때, 도시 A에서 B로 이동하는 경로가 반드시 존재해야한다 모든 도시를 연결할 때 최소한의 비용을 들이려면 어떻게 알고리즘을 이용해야할까? 예를 들어 왼쪽 그래프가 있다고 생각해보자 3..
-
[알고리즘] 최소신장트리, 크루스칼(Kruskal) 알고리즘Major/Algorithms 2022. 4. 19. 21:06
신장 트리 신장트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다 이 때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다 따라서 이러한 그래프를 신장 트리라고 부르는 것이다 신장트리 예시는 다음과 같다 최소 신장 트리 우리는 다양한 문제 상황에서 가능한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 설치한다고 생각해보자 2개의 도시 A,B를 선택했을 때, 도시 A에서 B로 이동하는 경로가 반드시 존재해야한다 모든 도시를 연결할 때 최소한의 비용을 들이려면 어떻게 알고리즘을 이용해야할까? 예를 들어 왼쪽 그래프가 있다고 생각해보자 3..
-
[알고리즘] 작업 스케줄링 (Job Scheduling) 문제Major/Algorithms 2022. 4. 18. 22:49
작업 스케줄링 (Job Scheduling) 문제 • 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 • 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다. ex) 발표= ‘작업’, 강의실= ‘기계’ 작업 스케줄링 문제에 주어진 문제 요소 • 작업의 수 > 입력의 크기이므로 알고리즘을 고안하기 위해 고려되어야 하는 직접적인 요소는 아니다. • 각 작업의 시작시간과 종료시간 • 작업의 길이 > 작업의 시작시간과 종료시간은 정해져 있으므로 작업의 길이도 주어진 것 시작시간, 종료시간, 작업 길이에 대한 그리디 알고리즘 • 빠른 시작시간 작업 우선 (Earliest start time first) 배정 • 빠른 종료시간 작업 우선 (Earliest finish time..