문제풀다가 모든 점에 대한 최단경로를 구해야하는 문제를 풀다가 플로이드 와샬을 떠올랐지만 알고리즘을 까먹엇다. (대충 3중 for문 이라는 것 정도..) 특징 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘. 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘. 3중 for 문 (제일 밖) 첫 번째 for 문: 거쳐가는 노드 두 번째 for 문 : 출발 노드 세 번째 for 문 : 도착 노드 검증 출발→거쳐 + 거쳐→도착 가 출발→도착 보다 더 짧으면? 출발→도착 갱신. Code for(int k = 0; k < number ; k++) { for(int i = 0; i < number ; i++) { for(int j ..
변별력 있는 탐색 문제에서 이진 탐색이 자주 출몰한다. 이진 탐색이란 우선! 정렬된 리스트에서 사용 가능하다. 탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색 한다. 3가지 변수가 사용됨 : 시작점, 끝점, 중간점 직접 구현 public class Solution { public int binarySearch(int[] arr, int target) { int first = 0; // 시작점 int last = arr.length - 1; // 끝점 int mid; // 중간점 while (first
Heap 우선 순위 큐를 하다가 Heap 구조를 사용한다는 것을 보았는데 Heap 자료구조란 무엇일까? 힙은 일종의 BinaryTree 이며 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조 가장 큰 / 작은 수 가져올때 시간 복잡도 : O(log N) 예: 최소 힙 구현 규칙이 있다. 루트는 가장 작은 값이여야 함. 자식은 자신보다 크기만 하면됨. 완전 이진 트리의 규칙을 그대로 적용 힙을 배열 형태로 구현 왼쪽 자식은 (자신의 인덱스 * 2) 오른쪽 자식은 (자신의 인덱스 * 2 + 1) 자신의 부모는 (자신의 인덱스 / 2) Heap 정의 public class Heap { public static final int MAX_N = 10001; public int[] ar..
