Manta Ray's

문제 : https://leetcode.com/problems/network-delay-time/ Network Delay Time - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 : 다익스트라 알고리즘 사용 2021.09.19 - [알고리즘/알고리즘] - 다익스트라 알고리즘 Dijkstra's algorithm 구현 JAVA class Solution { public int networkDelayTime(int[][] times, int n, int k..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 : ① DFS를 이용핸 도달할 수 있는 모든 경로를 탐색. ② 탐색 한 경로의 최소값을 출력 2021.09.19 - [알고리즘/알고리즘] - 깊이 우선 탐색 Depth-first search 깊이 우선 탐색 Depth-first search 깊이 우선 탐색 시작 노드와 직접 연관된 하위 노드 끝까지 모두 ..

문제 : https://leetcode.com/problems/height-checker/ Height Checker - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 : 선형시간 정렬 (계수정렬) 2021.10.05 - [알고리즘/알고리즘] - 선형시간 정렬 선형시간 정렬 계수정렬(Counting Sort) 1. 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. 가장 작은 원소와 가장 큰 원소를 구한다. 가장 작은 원소부터 가장 큰 원소까지의 실제..

문제 : https://www.acmicpc.net/problem/1927 관련 알고리즘 : 힙 정렬 2021.09.21 - [알고리즘/알고리즘] - 힙 정렬 Heap Sort 답안/풀이 JAVA ArrayList 혹은 LinkedList로 풀면 시간초과 발생 import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.ut..

힙의 형태 완전 이진 트리 : 각 노드의 자식 수가 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과 위치를 바꾼다. 퀵 정렬의 수도코드 시간복잡도 Balanced Partitioning : 파티셔닝의 크기가 n/2로 줄어드는 경우 => 높이 logN * 각 층별 N번의 연산을 수행 => O(NlogN) UnBalanced Partitioning : 파티셔닝의 크기가 1과 n-1개로 줄어드는 경우 => 높이 N-1 * 각 층별 N-1번의 연산을 수행 => O(N²) * Unbalanced Partitioning(최악의 경우)를 피하기 위해 파티셔닝의 크기를 랜덤하게 가져가는 Randomized QuickSort가 등장함. 구현 JAVA package algorithm; impor..

탐욕 알고리즘 현재 상황에서 가장 좋아보이는 답을 선택하는 방법. 상황마다 최적을 선택하면 전체 결과값도 최적이 될것이라는 가정을 전제로 함. ① 각 단계에 도달할 때 마다, 최적의 결과를 도출한다. ② 결과를 저장한다. ③ 이미 저장한 결과는 다시 판단하지 않는다. 탐욕 알고리즘이 적용된 알고리즘들 선택정렬 Selection Sort 배낭문제 Knapsack Problem 단일 출발지 최단 경로 문제 Single-Source Shortest Path Proble, 최소 신장 트리 Minimum Spanning Tree 프림 최소 신장 트리 알고리즘 Prim's Minimum Spanning Tree Algorithm 쿠스칼 최소 신장 트리 알고리즘 Kruskal's Minimum Spanning Tre..

플로이드-와샬 알고리즘 모든 정점 사이의 최단 거리를 찾는 알고리즘. 그래프를 인접행렬로 표현한다. 정점마다 경로 가중치를 기록한 인접행렬을 탐색하여 최단경로를 찾는 방식이다. 슈도코드 ① 인접행렬 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로 가는 비용

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