다이나믹 프로그래밍 유형

동전

게임 DP

중간에 잘라서 하는거

트리 DP (시간복잡도 계산에 주의)
LIS

비트마스크

댓글

댓글 쓰기

이 블로그의 인기 게시물

파이썬 재귀 최대깊이 지정 sys.setrecursionlimit( limit )

https://docs.python.org/2/library/sys.html#sys.setrecursionlimit https://www.acmicpc.net/problem/1012 파이썬 써본지 얼마 안되서 DFS를 구현하는 문제를 풀었는데 알고리즘상에 문제가 없어보이는데 자꾸 오답이 나왔다. 무슨 문젠가 몇시간 동안 고민했는데 이유는 재귀깊이 한계치가 작아서였다. import sys sys.setrecursionlimit(10**6) 을 추가해줬더니 정답처리 됐다. import sys sys.setrecursionlimit( 10 * * 6 ) bat = [] dx = [ 0 , 1 , 0 , - 1 ] dy = [ 1 , 0 , - 1 , 0 ] M = N = K = 0 def dfs ( x , y ): bat[x][y] = 0 for k in range ( 4 ): i = x + dx[k] j = y + dy[k] if (i >= M or i < 0 or j >= N or j < 0 ): continue if (bat[i][j] == 1 ): dfs(i,j) return for t in range ( input ()): (M,N,K) = map ( int , raw_input ().split()) cnt = 0 bat = [[ 0 for j in range (N + 1 )] for i in range (M + 1 )] for i in range (K): (a,b) = map ( int , raw_input ().split()) bat[a][b] = 1 for i in range (M): for j in range (N): if...
계속 읽기

BOJ 2401 - 최대 문자열 붙여넣기

문제 :  https://www.acmicpc.net/problem/2401 각각의 짧은 문자열들이 긴 문자열에서 어디에 등장하는지만 알 수 있다면, 이 문제는 전형적인 다이나믹 프로그래밍 문제가 된다. 그러니깐 KMP를 돌리면서 테이블을 채우면 된다. 시간 복잡도는 긴 문자열 길이 $S$, 짧은 문자열 길이 $T$, 짧은 문자열의 수 $N$이라 할때 $O(N * (S + T))$가 된다. 코드 :  http://ideone.com/zloOUb
계속 읽기