문제풀다가 모든 점에 대한 최단경로를 구해야하는 문제를 풀다가 플로이드 와샬을 떠올랐지만 알고리즘을 까먹엇다. (대충 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..
가끔씩 삼성 A형 문제라던가 구현, 시뮬레이션 문제들 보면 배열을 자주 돌린다. (회전 회오리) 그래서 이번 기회에 기강을 다져보기로 했다. (그저 기록이지만) 코딩테스트 치기전에 한 번 보면 좋겠다 미래의 나 class Map { int[][] map; public Map(int[][] map) { this.map = map; } public void rotate() { // 90도 회전 int rows = map.length; int cols = map[0].length; int[][] newMap = new int[cols][rows]; for(int i = 0 ; i < rows ; i++) { for(int j = 0 ; j < cols ; j++) { newMap[j][rows - i - 1]..
프로그래머스 [가장 먼 노드] 문제를 풀면서 dfs로 해도 되겠지만, 많이 못 써봤던 다익스트라 알고리즘을 사용하면 어떨까 해서 사용해봤는데, 다익스트라 알고리즘에서도 힙 구조를 사용하면 더 효율적으로 사용할 수 있다는 내용이 있어서 한 번 써보았는데 괜찮아져서 TIL에 기록하고 싶다. 다익스트라 알고리즘? 다익스트라 알고리즘은 DP (그 D.P가 아니다) 을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 왜 다이나믹 프로그래밍의 종류이냐? 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징때문이다. 대부분 이차원 배열을 사용하여 선형 탐색을 하는데, 이렇게 작성하면 시간 복잡도가 O(N^2)으로 형성된다. 이를 개선하기 위해 우선 순위 큐의 힙 구조를 활용하여 시간..
