관련 문제 BOJ 가장 긴 증가하는 부분 수열 4 가장 긴 증가하는 부분 수열 (LIS) 가장 긴 증가하는 부분 수열 : 수열의 원소를 순서대로 선택할 때 가장 긴 오름차순인 수열 코드로 구현하기 import java.io.*; import java.util.*; public class Main { static int N; static int[] A; static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); StringTokeni..
Problem Solving
이번 알고리즘 스터디에서 DP를 했는데.. 알고리즘 숙제를 하면서 느낀 점.. 나 혹시 탑다운 DP를 모르나..? 그래서 DP에 대해 다시 정리해보았다. (이전글 +a 해서 재업로드) Dynamic Programming 이란? DP의 핵심 컨셉은 한 번 같은 인자를 넣었을 때 동일한 결과가 나오는 경우 이 결과가 필요할 때마다 다시 연산하지 않고 저장해뒀다가 다시 사용한다. 즉, 한 번 푼 것은 다시 풀지 않는다. 재귀를 이용하여도 문제의 결과를 도출할 수 있다. 하지만 재귀는 다음과 같은 문제점이 있다. 반복적으로 동일한 데이터를 계산한다. 스택에 호출 경로 데이터를 계속 쌓아두어서 stack overflow가 발생할 수 있다. DP에서는 Memoization이라는 기법으로 연산한 결과를 저장하고 연산..
문제 https://www.acmicpc.net/problem/2206 풀이 풀이 ( 142020 KB, 784 ms) import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int[][] startmap, endmap; static int[] dr = {-1, 1, 0, 0}; static int[] dc = {0, 0, -1, 1}; static int n, m; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nex..
문제 https://www.acmicpc.net/problem/18352 풀이 풀이 ( 172212 KB, 2904 ms) import sys, heapq input = sys.stdin.readline def djk(start) : global dist, cities heap = [] heapq.heappush(heap, (0, start)) dist[start] = 0 while heap : curd, cur = heapq.heappop(heap) if dist[cur] cost : dist[i[0]] = c..
