CS/자료구조&알고리즘

벨만-포드(Bellman-Ford) 알고리즘 1. 그래프에서 최단 경로를 찾는 알고리즘 중 하나 2. 간선비용이 양수,음수에서 모두 정상 동작함.: 간선 비용은 시간,거리,요금을 나타내서 양수가 일반적임.: 그러나 간선 비용이 음수인 경우에도 정상 동작함 (다익스크라는 음수인 간선에선 동작하지X) 3. 음수 사이클: 음수 사이클이 있는 경우 거리를 무한히 줄이게되서, 최단 경로를 정의할 수 없음. (최단거리가 존재X)구현 코드function bellmanFord(graph, start, end) { const numOfNodes = graph.length; // 10 const distance = Array(numOfNodes).fill(Infinity); // [0, 8, 2, 4, 9, 10, 1..

✅ 이진 탐색 트리란이진 탐색 개념으 트리 구조에 적용한 것 ✅ 활용- (균형잡힌 트리인 경우) 효율적인 '검색'을 위해- 데이터 '삽입', '삭제'가 빈번할 경우- 우선순위가 필요한 작업 (최소값,최대값 빠르게 탐색)-  데이터베이스 인덱싱, 정렬, 검색 엔진, 네트워크 라우팅(라우팅 테이블 관리시) 등 ✅ 시간복잡도O(log n) : 모든 노드를 탐색하지 않고, 트리의 높이만큼 탐색하게 된다. (왼쪽, 오른쪽 트리의 높이가 비슷할 경우)O(n) : 그러나 트리가 한쪽으로 치우쳐 세로로 늘어진 경우 성능 저하  ✅ 특징1. 각 노드의 왼쪽 가지의 값들은 본인보다 작다: 10을 예로들면, 10 아래의 3,8은 10보다 작다 2. 각 노드의 오른쪽 가지 값들은 본인보다 크다.: 16을 예로들면, 23,..