LCSLongest Common Subsequence는 최장 공통 부분 문자열로, Substring의 값을 구하는 것이 아니라연속되지 않은 부분 문자열 중 가장 긴 공통 문자열을 찾는 알고리즘이다. 반대로, Longest Common Substring은 비슷하지만 부분 문자열이 아닌, substring이 되는 문자열이다. 예를들어 ABCDEF, BCDFQQ라는 문자열이 주어지면Longest Common Subsequence는 BCDF가 되고Longest Common Substring은 BCD가 된다.  LCS의 길이를 구할 때는 DP(Dynamic Programming)를 통해 메모제이션으로 효율적인 문제 해결이 가능하다.   점화식char[] w1 = word1.toCharArray();char[] w..

문제 링크 Gold 4 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net https://mag1c.tistory.com/452 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, mag1c.tistory.com 풀이 방향..

다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, 음의 가중치(음의 값)가 없어야한다.음의 가중치가 존재하게 되면, 최소 비용의 음의 무한대값이 생성될 수 있으며 그리디 알고리즘을 적용할 수 없다. 인접 행렬로 표현된 그래프의 경우 O(n^2)의 복잡도를 가지며, 우선순위 큐를 사용하여 시간복잡도를 O(m logn)까지 낮출 수 있다.  매커니즘(1) 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다 (그리디)(2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 (DP)  예시https://mag1c.tistory.com/451 [백준 1916번..

문제 링크 Gold 5 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 첫 풀이 단순 BFS로 구해보려했던 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { private static int N; private st..

문제 링크 Silver 1 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 문제의 조건은 선택한 스티커의 상하좌우 스티커는 선택할 수 없다. 라고 하였다. 아래 문제 예시를 보자. 50 10 100 20 40 30 50 70 10 60 위의 예시에서, dp를 사용하여 최대값을 어떻게 구할 수 있을까 왼쪽부터 시작해서, 하나씩 선택해보았다. 50 10 30 50 50 10 30 50 첫 번째 idx의 값을 선택할 수 있다. 두 번..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12983?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 DP를 사용하여 Bottom Up으로 풀이했고, 문제 예시에서의 banana로 예를 들어보자. b ba ban bana banan banana dp배열의 각 idx는 위의 값들을 만족하는 최소값들로 채워나갔다. strs의 원소에서, t의 인덱스마다 같은 substring이 있는지 확인하였고, 같다면 dp배열에 입력해나갔다. //strs에서 선택한 문자열과 ..

Dynamic Programing복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키백과  Dynamic Programing은1. 하위 문제로 쪼개지며, 하위 문제의 정답으로 해당 문제의 정답을 구할 수 있을 때(Optimal Substructure)2. 하위 문제가 겹칠 때 (Overlapping Subproblem)사용할 수 있다. Top-Bottom방식과 Bottom-Up방식이 있는데이름에서 알 수 있다시피 위에서아래로, 아래에서 위로 가는 방식인 것 같다.Top-Bottom은 재귀를 통해 메인 문제에서 작은 문제들로 쪼개어가는 과정이고Bottom-U..