Manta Ray's

플로이드-와샬 알고리즘 모든 정점 사이의 최단 거리를 찾는 알고리즘. 그래프를 인접행렬로 표현한다. 정점마다 경로 가중치를 기록한 인접행렬을 탐색하여 최단경로를 찾는 방식이다. 슈도코드 ① 인접행렬 A 생성 ② for ( k to 정점갯수) { for ( i to 정점갯수) { for ( j to 정점갯수) { //현재 경로 값과 정점 K를 거쳐가는 경로 값을 비교하여 더 작은 값을 저장 if (A ( i , j ) > A ( i , k ) + A( k , j ) ) { A ( i , j ) = A ( i , k ) + A( k , j ); } } } } 시간복잡도 ① 정점 K를 거쳐가는 경로를 탐색 ② ①을 수행할 때마다 경로 가중치를 기록한 인접행렬 V²을 탐색 O(V³) 구현 JAVA package..

벨만-포드 알고리즘 음수 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘. 벨만-포드 알고리즘에서 최단 경로는 출발점으로부터 도달가능하며 음의 값을 가지는 순환이 없는 경우를 의미함. 그래프에 있는 모든 정점을 한번씩 탐색함. 슈도코드 BELLMANFORD(그래프, 가중치, 시작점) 시작점 초기화 최단경로의 비용을 MAX으로 초기화 ① 모든 경우의 수 for ( 그래프의 모든 정점을 탐색) { for ( 그래프의 모든 엣지를 탐색){ if( U를 거쳐서 V로 가는 비용 < 현재 V의 최단 비용 ){ V로 가는 비용

다익스트라 알고리즘 시작점에서 도착점을 가는 최단경로를 찾는 알고리즘. 가중치 그래프 탐색에 사용됨. 슈도코드 DIJKSTRA(그래프, 가중치, 시작점) 시작점 초기화 최단경로의 비용을 MAX으로 초기화 Queue

깊이 우선 탐색 시작 노드와 직접 연관된 하위 노드 끝까지 모두 탐색한 후 다음 하위 노드를 탐색하는 방법 일단 경로 하나의 모든 층을 탐색한 후 그 다음 경로의 모든 층을 탐색하는 방법 재귀나 스택을 이용해 구현 백트래킹 문제의 해답을 찾지 못했을 때 이전 단계로 돌아가는 것 자식노드에서 값을 찾지 못했을 때 부모노드로 돌아가는 것 슈도코드 DFS(그래프, 시작 정점) { 시작점 방문여부 = true for ( 시작점과 연결된 정점 탐색 ){ if (탐색 정점의 방문여부 == false){ 탐색 정점의 방문여부 = true DFS(그래프, 탐색 정점) //재귀 } } } 시간복잡도 초기화 시간 : Ο(노드갯수) 그래프 탐색 시간 : Ο(노드갯수 + 간선갯수) 정점은 최대 1번 탐색한다. 간선은 최대 2..

너비 우선 탐색 시작점에서 도달 가능한 모든 간선을 탐색하여 찾는 과정 탐색을 하면서 시작점으로부터 거리를 계산한다. 탐색을 하면서 직전 정점의 위치를 저장한다. (거쳐온 정점을 기록한다.) 탐색을 하면서 정점의 상태를 변환한다. 초기화 : not discovered = white 발견한 정점 : discovered = gray 완료된(방문한) 정점 : finished = black 슈도코드 1. 주어진 모든 Graph를 초기화 * 정점의 상태 : 초기화(white) * 시작점으로부터의 거리 : ∞ * 바로 직전의 정점 : 초기화(NULL) 2. 시작 위치 저장 * 시작 정점의 상태 : 발견(gray) * 시작점으로부터의 거리 : 0 * 바로 직전의 정점 : NULL * Queue에 방문한 경로에 현재위..

그래프의 표현 노드와 간선으로만 이루어진 데이터 구조. 리스트 저장공간 : 노드의 갯수 + 간선의 갯수(양방향이면 X2) 행렬 저장공간 : 노드의 갯수² 가중치 그래프의 표현 간선에 가중치가 표현된 그래프 리스트 가중치 값을 추가하여 기록한다. 행렬 가중치를 행렬 값에 넣어준다. 리스트와 형렬 비교 저장공간 값이 성기면 리스트가 유리함. 값이 촘초하면 행렬이 유리함. 간선을 찾는데 걸리는 시간 리스트 : O(노드갯수) 행렬 : O(1) 모든 간선을 찾거나 방문하는데 걸리는 시간 리스트 : O(노드갯수+간선갯수) 행렬 : O(노드갯수²) 출처 컴퓨터 알고리즘 기초 13강 그래프의 표현, T아카데미

힙의 형태 완전 이진 트리 : 각 노드의 자식 수가 2 이하이며, Root 노드부터 Leaf 노드까지 빠짐없이 채워져있는 트리 최대힙 Max-Heap 부모 노드 > 자식 노드 Root 노트의 값이 가장 크다. 최소힙 Min-Heap 부모 노드 < 자식 노드 Root 노드의 값이 가장 작다. 힙 배열 저장 방식 Root 노드는 배열의 첫 번째에 저장 각 노드들은 레벨 별로 저장 부모 : 현재위치 / 2 왼쪽 자식 : 현재위치*2 오른쪽 자식 : 현재위치 *2+1 힙의 높이 O(logN) 힙 특성관리 Max-Heapify 노드가 입력으로 주어졌을 때 max-heap 특성이 유지되도록 바꾸는 연산 입력값이 흘러내리게 함. 수행시간 : O(logN) 힙 구조 만들기 입력받은 트리에 Max-Heapify를 반복 ..

병합정렬 데이터를 반으로 나누어 정렬을 수행하는 알고리즘. 분할 정복 알고리즘. 수행방식 ① 배열을 숫자 1개만 남을 때까지 반복해서 1/2로 나눈다. ② 두 배열씩 결합하며 작은 숫자에서 큰 숫자로 정렬한다. ③ 결합을 반복하며 배열의 크기를 늘려나간다. 시간복잡도 O(nlogn) 구현(JAVA) public class MergeSort { static int[] arr; static int[] tmp; public void mergeSort(int start, int end) { if(start

삽입 정렬 Key 값과 정렬된 리스트가 주어졌을때, Key값을 정렬된 리스트의 알맞은 위치에 삽입 Key 값을 하나씩 추가하면서 정렬. ① i 위치의 값을 0~(i-1) 위치까지의 값과 비교하여 i위치의 값이 들어갈 위치를 찾음. ② i 위치의 값을 찾은 자리에 삽입 시간복잡도 최선의 경우 : 0 ~ i-1 배열이 이미 정렬된 경우 > 비교를 1번만 하면 됨 => n-1 최악의 경우 : 0 ~ i-1 배열이 반대로 정렬된 경우 > 모든 배열 값과 다 비교해야 함. => n(n-1)/2 O(n²) 구현 (JAVA) public int[] sort(int[] arr) { //배열을 리스트로 변경 List list = Arrays.stream(arr).boxed().collect(Collectors.toLis..

선택정렬의 종류 ① 최소값 선택 정렬 (오름차순) ② 최대값 선택 정렬 (내림차순) 최소값 선택 정렬 (오름차순) 정렬되지 않은 숫자 중에 가장 작은 숫자를 선택한다. 선택한 가장 작은 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다. 모든 숫자를 옮길 때까지 반복한다. 최대값 선택 정렬 (내림차순) 정렬되지 않은 숫자 중에 가장 큰 숫자를 선택한다. 선택한 가장 작은 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다. 모든 숫자를 옮길 때까지 반복한다. 시간복잡도 n개가 있을 때 가장 큰/작은 수를 구하기 위해서 n-1 번의 비교가 일어남. => n(n-1) / 2 O(n²) 구현 (JAVA) public int[] solution(int n, int[] arr) { for(in..