Kwin's Development Diary.

최장 공통부분 수열과 최장 공통부분 문자열의 차이점 12346789 ▶ 134679 Longest Common Subsequence(수열) 13465798 346 Longest Common Substring(문자열) 최장 공통부분 수열(Longest Common Subsequence) : 부분 수열이 서로 붙어있을 필요 없이 앞뒤 순서만 따져 길이가 최대가 되는 부분 수열을 찾는 알고리즘 // LCS 수열 최대 길이 구하기 if(str1.charAt(i) == str2.charAt(j)) LCS[i][j] = LCS[i-1][j-1] + 1; else LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]); Java 코드 // LCS 수열 길이 구하기 for(int i=1; i

위상 정렬 알고리즘 (Topological Sort Algorithm) : 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 정렬하는 알고리즘 위상 정렬 알고리즘 ① 진입 차수가 0인 정점들 모두 enQueue ② 큐에서 deQueue 해서 반환받은 정점 출력 ③ 출력한 정점에서 뻗어나가는 간선이 도착하는 정점의 진입 차수 -1 ④ 진입 차수를 -1 해준 정점의 진입 차수가 0이 되면 enQueue ⑤ 큐가 Empty상태가 될 때까지 ② ~ ④과정 반복 더보기 결괏값 >>> V0 - V1 - V2 - V3 - V4 - V5 - V6 의사 코드(Pseudo Code) Topological() Q ← createQueue(); for(Vi ← 0; Vi

벨만-포드 알고리즘(Bellman-Ford Algorithm) : 음수인 가중치가 포함되어 있는 그래프에서 최단 거리를 구하는 알고리즘 음수 간선이 존재하지 않는다면 [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바를 사용하여 문제를 해결하는 것이 실행 시간이 더 빠르다. 특징 ① 음수인 사이클을 찾을 수 있다 ② 매번 모든 간선을 확인하기에 연산 시간이 느리다 알고리즘 ① 출발 노드 설정 ② 최단 거리를 저장할 배열을 초기화 ③ 전체 간선을 하나씩 확인 ④ 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 ⑤ 모든 노드에 연결되어 있는 모든 간선을 확인할 때까지 ③ ~ ④반복수행 ⑤-1 이때, 마지막 반복에서 최단 거리 테이블이 갱신된다면..

0-1 너비 우선 탐색 (0-1 Breath First Search, 0-1 BFS) : 가중치가 0과 1만 존재하는 그래프에서 최단 경로를 찾는 알고리즘 [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바를 사용하여 풀 수도 있는 문제이지만, 가중치가 0과 1만 존재하는 그래프라면 0-1 BFS 알고리즘이 보다 효율적으로 문제풀이가 가능하다. 특징 ① 큐(Queue) 대신 덱(Deque)을 사용 ② 가중치가 0과 1만 존재할 때 사용 알고리즘 1. 덱(Deque)의 front에서 이동할 다음 경로를 꺼낸다. 2. 현재 위치에서 연결된 다음 경로를 탐색한다. 3. if(출발 지점부터 현재 위치까지 누적된 가중치 + 다음 경로와 연결된 간선의 가중치 < 다음 경로까지..

0-1 배낭 문제 (Knapsack Problem) : 담을 수 있는 무게의 최댓값이 정해진 배낭에 일정한 가치와 무게가 정해져 있는 짐들을 골라 배낭에 담기는 최대의 가치를 구하는 문제 특징 ① 동적 계획법(다이나믹 프로그래밍, DP : Dynamic Programming)으로 해결할 수 있다. ② 다른 버전으로는 물건을 쪼갤 수 있는 Fraction Knapsack Problem이 있다. 알고리즘 ① 물건의 정보를 표에 저장해둔다 ② DP배열을 만든다 (열은 물건 0~i번까지 넣을 수 있음을 의미하고 행은 0~n까지 넣을 수 있음을 의미한다) - i, j에서 i번째 물건까지 중에 배낭에 넣을 수 있는지 없는지 판단하여 최적의 방법을 저장한다. ㄴ 넣는 것이 최적 = [i - 1][j - i번째 물건 ..

다익스트라 알고리즘(Dijkstra Algorithm) : 음의 가중치가 없는 가중 그래프에서의 최단 경로를 구하는 알고리즘 특징 ① 그래프에서 음의 가중치가 없어야 한다. ( ↔ 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)) 알고리즘 ① V1부터 Vn까지 연결된 간선 인접 행렬 또는 인접 리스트에 저장 ② V1부터 방문하여 V1에서 갈 수 있는 정점에 대해 최소 거리 갱신 및 다음 방문 예정지로 저장 V1 V2 V3 V4 V5 V1 0 1 2 5 INF V2 1 0 2 3 INF V3 2 2 0 INF 4 V4 5 3 INF 0 1 V5 INF INF 4 1 0 더보기 V1 V2 V3 V4 V5 V1 0 1 3 5 INF V1 V2 V3 V4 V5 V1 0 1 3 5 → 4 ..

플로이드-와샬(Floyd-Warshall Algorithm) = 플로이드 알고리즘, 로이-와샬 알고리즘, 로이-플로이드 알고리즘, WFI 알고리즘 : 음의 사이클이 없는 가중 그래프에서 최단 경로를 찾는 알고리즘이다 특징 ① 음의 간선이 있는 가중 그래프에서 사용 가능 (≠ 다익스트라 알고리즘(Dijkstra Algorithm)) 알고리즘 ① V1부터 Vn까지 연결된 간선 인접 행렬에 저장 ② 경유하는 정점으로 V1~Vn을 설정 (k) ③ 시작 정점(i)을 V1~Vn, 도착정점(j)을 V1~Vn으로 하는 경우 모두 탐색 이때, 의 값이 + 보다 1. 작거나 같으면 그냥 넘어감 2. 크면 값 대체 더보기 Before graph V1 V2 V3 V4 After graph V1 V2 V3 V4 V1 0 INF..

너비 우선 탐색(Breath First Search, BFS) : 하나의 정점으로부터 시작하여 인접한 정점들을 우선으로 탐색하여 최종적으로 모든 정점을 탐색하는 방법 특징 ① 목표 지점까지 최단 길이(경로)를 보장한다. ② 경로가 길수록 인접한 정점이 많이 생겨나므로(저장되므로) 저장 공간이 많이 필요하다. ③ 선입선출(FIFO, First In First Out) 구조이다. BFS 알고리즘 ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue ③ 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해 큐에서 deQueue 하여 구한 정점에서 ②반복 ④ 큐가 공백이 될 때까지 ②~③반복 더보기..

깊이 우선 탐색(Depth First Search, DFS) : 하나의 정점으로부터 시작하여 깊은 곳 우선으로 탐색하여 최종적으로 연결된 모든 정점을 탐색하는 방법 특징 ① 경로상의 노드들만 기억하면 되므로 차지하는 저장 공간이 적다. ② 같은 레벨의 경로보다 더 깊은 레벨을 우선으로 탐색한다. ③ 재귀적으로 동작하며, 후입 선출(LIFO, Last In First Out) 구조이다. 알고리즘 ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점 중 1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행 2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정점을 스택을 pop 하여 받은 정점 v로 하여 다시..

색인 순차 검색(Index Sequential Search) - 정렬되어 있는 자료에 대한 *인덱스 테이블(Index Table)을 추가로 사용하여 탐색 효율을 높인 검색 방법 * 인덱스 테이블 : 배열에 정렬되어 있는 자료 중 일정한 간격으로 떨어져 있는 원소들을 저장한 테이블 ㄴ 자료가 저장되어 있는 배열의 크기가 n이고 인텍스 테이블의 크기가 m일 때, 배열에서 n/m간격으로 떨어져 있는 원소와 그의 인덱스를 인덱스 테이블에 저장 검색 방법 - indexTable[i].key ≤ key ≤ indexTable [i+1].key를 만족하는 i를 찾아 배열의 어느 범위에 있는지 알아낸 후 해당 범위에 대해서만 순차 검색 수행 Ex) 리스트 = {1, 3, 10, 23, 29, 33, 45, 50} 1 ..