OILAT

수강한 강의 Chapter 20 그래프 고급 탐색 알고리즘 - 프림 알고리즘 3, 4 학습 후기 이전 강의에 이어 이번에도 프림 알고리즘 강의지만 전보다 향상된 프림 알고리즘이다. 원래는 20일 차에서 기본 프림 알고리즘과 개선된 프림 알고리즘을 동시에 올릴까도 생각했지만 생각보다 이해하는데 시간이 걸려서 오늘 개선된 프림 알고리즘에 대해 적어본다. 개선된 프림 알고리즘 간선이 아닌 정점을 중심으로 우선순위 큐를 적용하여 계산하는 알고리즘으로 다익스트라 알고리즘 구현한 방식과 비슷하다고 볼 수 있다. 다익스트라 알고리즘에서 처음 정점의 가중치 값을 0 나머지 정점까지 가는 길의 가중치를 무한대로 놓고 처음 정점과 이어진 정점의 가중치를 따라가며 저장된 정점까지의 가중치 값을 업데이트했듯이 개선된 프림 알..

수강한 강의 Chapter 20 그래프 고급 탐색 알고리즘 - 프림 알고리즘 학습 후기 그래프 고급 탐색 알고리즘 강의의 난이도가 상당하다. 최단 경로 알고리즘의 이해, 최소 신장 트리, 크루스칼 알고리즘, 이번 강의의 프림 알고리즘까지 강의를 보면 좀 알 거 같은데 돌아서면 또 까먹는 거 같은 알고리즘들이다. 여러 번 강의를 반복해서 듣고 자바로 직접 구현해보며 완전히 이해할 때까지 익히는 게 중요한 것 같다. 프림 알고리즘 최소 신장 트리를 구하는 알고리즘 중 하나이며, 시작 정점을 정하고 시작 정점에 인접한 간선 중 최소 가중치를 가지는 간선으로 연결된 정점을 선택하고 다시 최소 가중치로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 구함 크루스칼 알고리즘과 프림 알고리즘 비교 공통점: 탐욕 알..

수강한 강의 Chapter 20 그래프 고급 탐색 알고리즘 - 최소 신장 트리의 이해와 크루스칼 알고리즘 학습 후기 신장 트리(Spanning Tree)는 모든 노드들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. n개의 노드로 이루어진 그래프는 n-1개의 간선으로 연결된다. 최소 신장 트리(Minimum Spanning Tree, MST) 최소 신장 트리는 Spanning Tree 중 1. 사용된 간선의 가중치 합이 최소이고 2. n개의 노드를 가지는 그래프에서 간선이 n-1개이고 3. 사이클이 포함되지 않은 트리이다. 크루스칼 알고리즘(Kruskal Algorithm) 그래프에서 최소 신장 트리(MST)를 찾는 알고리즘으로 탐욕 알고리즘에 기초하여 각 단계에서 사이클을 이루지 않는 최소 비용의 ..

수강한 강의 Chapter 20 그래프 고급 탐색 알고리즘 - 최단 경로 알고리즘 이해 학습 후기 최단 경로 알고리즘.. 강의를 다 듣고 학습후기를 쓰는데 오늘 강의는 진짜 어려운 것 같다. 하지만 알고리즘 테스트를 통과하기 위해서는 꼭 이해하고 구현할 수 있도록 해야 하기 때문에 강의 들을걸 잘 정리하고 넘어가자 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제다. 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다. 최단 경로 문제 종류 1. 단일 출발 최단 경로 문제: 특정 노드 A에서 출발, 그래프 내 모든 다른 노드에 도착하는 가장 짧은 경로를 찾음. 2. 단일 도착 최단 경로 문제: 모든 노드에서 출발, 특정 노드 A로 도착하는 가장 짧은 경로를 찾..

수강한 강의 Chapter 19 탐욕 알고리즘 - 탐욕 알고리즘의 이해 학습 후기 탐욕 알고리즘(Greedy Algorithm) 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들로 최종해를 구했다고 해서 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제는 지역적으로 최적이면서 전역적으로도 최적인 문제이다. 필요한 조건 1. 탐욕스러운 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않는다. 2. 최적 부분 구조 조건: 문제에 대한 최적해가 부분 문제에 대해서도 역시 최..

수강한 강의 Chapter 18 그래프 기본 탐색 알고리즘 - 너비 우선 탐색(BFS) - 깊이 우선 탐색(DFS) 학습 후기 알고리즘 문제 중에서 가장 빈번하게 나오는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)에 대한 강의를 들었다. 알고리즘을 코드로 작성하기 전 강사님이 엑셀에서 BFS와 DFS가 어떻게 동작하는지 설명해주셨다. 일단 그래프는 HashMap과 ArrayList를 사용하여 전체 그래프를 표현하였다. 그리고 HashMap의 CRUD, Create(생성), Read(읽기), Update(수정), Delete(삭제)도 알려주셨다. 이 전체 그래프를 보면서 BFS를 어떻게 구현해 나가는지 설명해주셨다. 너비 우선 탐색(BFS) BFS는 자료구조 큐를 활용하여 해당 노드에 방문한 적이 ..

수강한 강의 Chapter 17 그래프 이해와 자료 구조 - 그래프 이해와 자료 구조 학습 후기 알고리즘에서 많이 쓰이는 그래프 기본 탐색 알고리즘 BFS, DFS를 배우기 전에 그래프의 이해 강의를 들었다. 강사님이 말씀하시길 그래프 알고리즘이 상당히 어렵다고 하시면서 강사님도 문제 해결을 위해 하루 이틀 고민해서 풀어보고 이해할 때까지 계속해서 보신다고 하셨다. 그만큼 어려운 강의라 나도 여러 번 보고 확실히 익혀야겠다. 그래프 이론 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구라고 위키피디아에 나와있다. https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0 그래프 이론 - 위..

수강한 강의 Chapter 16 순차 탐색 알고리즘 - 정렬 알고리즘 몸풀기: 순차 탐색 - 정렬 알고리즘 몸풀기: 이진 탐색 학습 후기 강사님이 중간에 쉬어가는 코너라고 말씀하시며 오늘 강의를 시작하셨다. 계속 어려운 알고리즘 강의만 하기보다 중간에 쉬어 가는 것도 좋은 거 같다. 순차 탐색(Sequential Search) 탐색은 여러 데이터 중에서 원하는 데이터를 찾는 것이다. 그중 순차 탐색 방법은 데이터가 담겨 있는 배열을 처음부터 끝까지 확인해서 찾는 방법이다. public int search(ArrayList list, Integer target) { for (int i = 0; i < list.size(); i++) { if (target.equals(list.get(i))) { retur..

수강한 강의 Chapter 15 고급 정렬 알고리즘 - 퀵 정렬 학습 후기 퀵 정렬 기준(pivot)을 정해서 기준보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 사용하여 왼쪽과 오른쪽을 동일 함수를 사용하는 재귀 용법으로 반복하여 정렬된 데이터를 리턴하는 알고리즘 https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 퀵 정렬 - 위키백과, 우리 모두의 백과사전 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에 ko.wikipedia.org 퀵 정렬은 매 단계에서 적어도 1개의 원소(piv..

수강한 강의 Chapter 15 고급 정렬 알고리즘 - 병합 정렬 학습 후기 병합 정렬 or 합병 정렬(merge sort) 비교 기반 정렬 알고리즘이며 분할 정복 알고리즘의 하나이다. 아래 위키피디아 이미지를 보며 합병 정렬이 어떻게 진행되는지 이해해본다. https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC 합병 정렬 - 위키백과, 우리 모두의 백과사전 합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945 ko.wikipedia.org 병합 정렬은 다음과 같이 작동한다...