천천히 빛나는

위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같이 나열하는 것을 위상 정렬이라고 한다. 위상정렬을 알기 전 다뤄야 하는 용어에 진입차수와 진출차수가 존재한다. 진입차수 (Indegree) 특정한 노드로 들어오는 간선의 개수 진출차수 (Outdegree) 특정한 노드에서 나가는 간선의 개수 동작 과정 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 넣는다 예시 진입차수가 0인 노드가 존재하기 위해서는 사이클이 없는 그래프가 필요하다 [초기단계] 진압차수가 0인 모든 노드를 큐에 넣는다. [1] 큐에서 노드 ..

전보 통로 = 방향성이 있는 간선 일정 시간 = 간선 가중치 핵심 아이디어 : 한 도시에서 다른 도시까지의 최단 거리 문제 N과 M의 범위가 충분히 크기 때문에 우선순위 큐를 활용한 다익스트라 알고리즘을 구현해야 한다. import java.util.*; class Node implements Comparable { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance..

플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다익스트라 알고리즘이란? https://shine-slowly.tistory.com/85 알고리즘 : 다익스트라(Dijkstra) 최단 경로 알고리즘 (Java로 구현) 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 최단 경로 알고리즘 중 다익스트라 알고리즘은 다음과 같은 특징을 가지고 있다. 특정한 노 shine-slowly.tistory.com 다익스트라 알고리즘과 다른게 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다...

다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 최단 경로 알고리즘 중 다익스트라 알고리즘은 다음과 같은 특징을 가지고 있다. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 사용할 수 있다 다익스트라 최단 경로 알고리즘은 그리디 알고리즘 중 하나이다. 매 상황에서 가장 비용이 적게 드는 노드를 선택하기 때문이다. 다음은 다익스트라 최단 경로 알고리즘의 동작 과정을 간단히 서술한 내용이다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 이 때, 다른 노드까지의 거리를 무한으로 설정하고 자기 자신까지의 거리는 0으로 설정한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은..

6. 교착 상태 위와 같이 두 개 이상의 프로세스가 서로 대기 중인 상황에서는 어떤 프로세스도 자원을 이용할 수 없게된다. 어떤 프로세스가 어떤 자원을 할당 받았는지 혹은 기다리고 있는지 아래와 같은 자원 할당 그래프로 파악할 수 있다. 프로세스는 원, 자원은 사각형 사용할 수 있는 자원의 개수는 자원 사격형 내 점으로 표현 할당받았으면 자원에서 프로세스 쪽으로 화살표로 표시 기다리고 있으면 프로세스에서 자원으로 화살표 교착 상태가 발생할 조건 상호 배제 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태 점유와 대기 자원을 할당받은 상태에서 다른 자원을 할당 받기를 기다리는 상태 비선점 어떤 프로세스도 다른 프로세의 자원을 강제로 빼앗지 못하는 상태 CPU 스케줄링할 때 비선점, 선점했..

본 포스팅에서는 [활주로, 홈 방법서비스, 등산로 조성, 벌꿀채취]를 다룹니다. 4014. (모의 SW) 활주로 import java.io.*; import java.util.*; public class Solution { // 활주로는 높이가 동일한 구간에서 건설 // 높이가 다른 경우 경사로를 설치 static int N, X; // 맵크기, 경사로 높이 static int map[][]; static boolean visited[][]; static int ans; static StringBuilder sb = new StringBuilder(); // 건설 static void construction() { visited = new boolean[N][N]; boolean success; // 가..

이번 포스팅에서는 [Ladder1, 달팽이 숫자, 파리퇴치]를 다룹니다 1210. Ladder1 import java.io.*; import java.util.*; public class Solution { static int[] dx = { 1, 0, 0 }; static int[] dy = { 0, -1, 1 }; static int[][] map = new int[100][100]; static boolean[][] visited; static class Pair { int first; int second; Pair(int first, int second) { this.first = first; this.second = second; } } static boolean ladder(int r, int..

Day 1에서는 [연구소, 연산자 끼워넣기, 감시, 스타트와 링크, 치킨배달, 톱니바퀴, 인구이동, 퇴사]를 다룹니다. 14502. (골드4) 연구소 import java.io.*; import java.util.*; class Pair{ int first; int second; public Pair(int first, int second) { this.first = first; this.second = second; } public int first() { return first; } public int second() { return second; } } public class Main { static int N, M; static int[][] map = new int[8][8]; static fi..