천천히 빛나는

LCS (Longest Common Subsequence)문자열 x, y가 있을 때 x와 y에서 공통으로 나타나는 부분 문자 수열 중 최대 길이를 갖는 문자 수열예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다 재귀적으로 정의c(i, j) : 수열 xi와 yj의 LCS의 길이 기저조건 (종료조건)i =0 또는 j = 0이면 c(i, j) = 0이 된다재귀조건xi = yj이면 c(i, j) = c(i-1, j-1) + 1xi != yj이면 c(i,j) = max(c(i, j-1), c(i-1, j))int lcs (String x, String y){ int m = x.length(); int n = y.length(); if(m == 0 || n == 0){ re..

본 포스팅에서는 [Z, 드래곤커브, 외판원순회, 월드컵, 야구공, 빵집]을 다룹니다. 1074. (실버 1) Z import java.io.*; import java.util.*; public class Main { static int N, r, c, sz, ans; static int map[][]; static boolean success; static void makeZ(int x, int y, int size) { if (size == 1) return; if (x (size / 2) - 1) { // 오..

본 포스팅에서는 [이차원 배열과 연산, 요세푸스 문제, 안전영역, 배열돌리기3, 신기한 소수]을 다룹니다. 17140. (골드4) 이차원 배열과 연산 import java.io.*; import java.util.*; public class Main { static int r, c, k; static int map[][]; static int time; static int freq[]; static ArrayList list = new ArrayList(); static int maxRow, maxCol; static int tempMaxRow, tempmaxCol; static class Pair { int freq; int val; Pair(int freq, int val) { this.freq = ..

위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같이 나열하는 것을 위상 정렬이라고 한다. 위상정렬을 알기 전 다뤄야 하는 용어에 진입차수와 진출차수가 존재한다. 진입차수 (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..