LIS(최장 증가 부분 수열)N크기의 배열이 주어졌을때, 배열에서 일부 원소를 조합하여 만든 부분 수열 중, 오름차순의 조건을 만족하면서 길이가 최대인 부분 수열을 말한다. 아래처럼, {3, 6, 2, 1, 7, 8, 5, 4, 9}의 배열이 있다면, LIS는 {3, 6, 7, 8, 9} 이다  DPLIS 문제는 각 요소를 포함하는 증가하는 부분 수열의 최대 길이를 찾는 문제로 이를 효율적으로 해결하기 위해 동적 계획법을 사용한다.단일 배열 내에서, 이전 인덱스의 숫자와 비교하여 증가시켜주면 되기 때문에 DP로 문제를 해결할 수 있다.단일 배열이라는 점만 제외하면 LCS와 유사한 매커니즘이기에, 점화식도 비슷한 방법으로 구현할 수 있다.   [알고리즘] LCS (Longest Common Subseque..

문제 난이도GOLD III  문제 링크https://www.acmicpc.net/problem/1238   풀이 [알고리즘] 다익스트라(Dijkstra) 알고리즘다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로,mag1c.tistory.com 위의 다익스트라 알고리즘을 사용해서 구현한 문제이다.    문제 예시를 그림으로 표현해보았다.목적지로의 최단거리만 구하면 됐던 기본적인 다익스트라 알고리즘 구현 문제에서, 반대로 2에서 각 노드의 최단 경로를 한번 더 구해주기만 하면 된다. (A -> X, X -> A) private static int[] dijkstra..

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에서 선택한 문자열과 ..