천천히 빛나는

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..

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

1. 개미 전사 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하는 문제이다. N=4일 때 식량을 선택할 수 있는 경우의 수는 8가지이다. 최적의 해는 7번째(3+5=8)가 된다. a_i를 i번째 식량창고까지의 최적의 해라고 정의하도록 하겠다. i번째 식량창고에 대해서 털지 안 털지의 여부를 결정하기 위해서는 2가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다. int n; int food[101]; int dp[101]; int main() { cin >> n; for (int i = 1; i > food[i]; } dp[1] = food[1]; dp[2] = max(food[1], food[2]); for (int i ..

참고 영상: https://www.youtube.com/watch?v=5Lu34WIx2Us 다이나믹 프로그래밍 (Dynamic Programming, 동적 계획법) 메모리를 적절히 사용하여 수행 시간 효율성을 향상시키는 방법 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 나중에 해당 결과가 필요할 때 기록된 결과를 그대로 사용한다. 다이나믹 프로그래밍의 구현은 탑다운(하향식)과 보텀업(상향식) 방식으로 구성된다. 다이나믹 프로그래밍을 사용하는 조건은 다음과 같다. 1. 최적 부분 구조 (Optimal Substrcture) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (Overlapping Subpr..

백트래킹 (Back-tracking) 정답을 찾는 도중에 막히면 더 이상 깊이 들어가지 않고 이전 단계로 돌아가서 정답을 찾는 방법 깊이 우선 탐색 DFS는 가능한 모든 경로를 탐색한다. 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이지 못한다. 백트래킹은 지금 경로가 정답이 아닐 것 같다면 이전 단계로 돌아가므로 DFS보다 효율적이다. 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 탐색하는 것이 백트래킹이다. 문제풀이에서는 모든 경우의 수를 탐색하는 과정에서 (DFS 등으로 구현) 조건문으로 절대 답이 될 수 없는 상황을 설정하고 그런 상황이 되었을 때는 탐색을 중지시킨 뒤 다시 이전 단계로 돌아가서 탐색하도록 구현할 수 있다. 백트래킹 예시 bool visited..

1. 음료수 얼려 먹기 connected component를 찾는 문제이다. 얼음을 얼릴 수 있는 공감이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 다음과 같이 3 x 3 크기의 얼음틀이 있다고 가정하면 위 그림과 같이 그래프로 만들 수 있다. 상, 하, 좌, 우로 연결되어 있는 노드들은 인접한 형태가 된다. 특정 지점에서 BFS 또는 DFS를 수행해서 이동 가능한 모든 경로에 대해서 다 방문처리를 진행하도록 처리할 수 있다. 1) BFS를 이용해서 구현 #include #include using namespace std; bool notAllowed[1001][1001]; int n, m; void bfs(int row, int col) { queue ..

https://shine-slowly.tistory.com/48 알고리즘 : DFS와 BFS (1) - DFS (C++로 구현) 참고 영상 : https://youtu.be/7C9RgOcvkvo?si=PuM-7RIBWbVPtYTw bfs와 dfs는 탐색 알고리즘이다. 내가 헷갈렸던 부분이 있는데 그래프를 인접 행렬, 인접 리스트로 표현할 수 있다고 배웠는데 bfs, dfs는 각각 큐랑 shine-slowly.tistory.com DFS에 관한 내용은 위 포스트에 있습니다. 참고 영상 : https://youtu.be/7C9RgOcvkvo?si=PuM-7RIBWbVPtYTw BFS (Breath-First Search, 너비우선탐색) 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐..