기록의 힘

이분탐색이란? 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 반드시 정렬된 리스트에서 사용해야함! 자료가 무작위로 있다면 어느 특정 방향(앞 또는 뒤)으로 간다고 해서 해당 자료가 중간 부분보다 작거나 크다는 보장이 없음. 구현 과정 리스트 오름차순으로 정렬 찾고자 하는 범위의 최솟값(left) / 최댓값(right) / 리스트의 중간 값(mid) 선택, 찾고자 하는 값 X와 비교 X가 mid보다 작으면 mid보다 작은 값들을 대상으로 다시 탐색 (mid = X - 1) X가 mid보다 크면 mid보다 큰 값들을 대상으로 다시 탐색 (mid = X + 1) 해당 X값을 찾을 때까지 반복 단, left가 right보다 커지면 반복 중단 구현 코드 int[] array = {10, 23, ..

플로이드 와샬 알고리즘이란 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘 즉, 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶을 때 쓰는 알고리즘 다익스트라 알고리즘과 달리 음의 가중치를 가진 간선이 있을 수 있음 '거쳐가는 정점 기준으로 최단 거리를 구하는 것' ( 다익스트라: 가장 적은 비용을 가진 정점 기준) 자료구조 및 시간 복잡도 모든 정점에 대한 경로를 계산하므로 2차원 배열 사용 시간 복잡도: O(n^3) d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; } } } } 제일 바깥쪽: 거쳐가는 정점 두 번째: 출발하는 정점 세 번째: 도착하는 정점 선행 과정 2차원 배열에 두 정점간 비용 초기화 (연결되어있지 않다면 무한대로 초..

다익스트라 알고리즘이란 특정한 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 문제의 방법 음의 간선이 있을 경우 사용할 수 없음 다익스트라 원리 특정한 하나의 정점을 잡고, 그 정점과 이웃한 정점들의 비용을 각각 확인 그 중 가장 적은 비용이 드는 정점 기준으로 다시 한번 확인 (Why ? 직접 이웃한 정점으로 가는 것보다 이웃한 정점을 거쳐서 가는 것이 더 적은 비용이 들수도 있기 때문) 과정 출발 노드 설정 출발 노드 기준, 각 노드의 최소 비용 저장 방문하지 않은 노드 중에서 가장 비용이 적게 드는 노드 선택 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소비용 갱신 다익스트라 알고리즘 기본로직 시작점의 최단거리를 0, 나머지 정점의 최단거리는 INF (무한대. 즉, 가질 수 없는..

Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프 최소 연결 = 간선의 수가 가장 적음 정점이 n개 일 때, 그래프의 최소 간선 수 = n-1, n-1개의 간선으로 연결되어 있으면 트리형태가 되고 이게 스패닝 트리 즉 , 그래프 일부 간선을 선택해서 만든 트리 모든 정점들이 연결 되어 있어야함 사이클을 포함해서는 안됨 MST (Minimum Spanning Tree) Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 간선의 가중치의 합이 최소여야함 n개의 정점을 가지는 그래프에서 반드시 n-1개만의 간선을 사용해야함 사이클에 포함되어서는 안됨 MST 구현 방법 1. Kruskal 알고리즘 탐욕적인 방법 (Greedy method)를 이..

DFS와 BFS의 목적 - 임의의 시작점에서 시작해서 모든 정점을 한번씩 방문하는 것 - 경로 찾는 문제에서 활용 DFS - Depth First Search (깊이 우선 탐색) - 스택을 이용해서 갈 수있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아가서 갈 수 있는 길을 탐색 - 재귀 호출을 이용해서 구현할 수 있다 dfs(x) : x에 방문 - 모든 경로를 방문해야 할 경우 사용에 적합 - 시간복잡도 : 인접 행렬 -> O(v^2) : 한 정점당 v번 탐색, 모든 정점 한번씩 방문해야하므로 v * O(v) 인접 리스트 -> O(V+E) : 다 끝났을 시점에는 모든 정점을 한번씩 방문하고, 모든 간선을 한번씩 검사하게 되므로 BFS - 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두..