다이나믹 프로그래밍 유형

동전

게임 DP

중간에 잘라서 하는거

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

비트마스크

댓글

댓글 쓰기

이 블로그의 인기 게시물

블로거에 마크다운으로 글 작성하기

http://dillinger.io/ 저기서 마크다운으로 작성한 다음에 HTML로 바꿔서 적으면 된다 테스트 : Untitled Document.md Hello World Hello world Hello world apple banana italic bold npm start show me the money black sheep wall function sayHello ( ) { console .log( 'hello world' ); } sayHello(); for ( int i = 0 ; i < n; ++i) { puts ( "Hello World" ); } <addr> 뭔가 애매하게 되는데 만족스럽다.
계속 읽기

BOJ 1006 - 습격자 초라기

문제 : https://www.acmicpc.net/problem/1006 DP[i][j] : i 번째 열, j타입일 때 남은 열을 적절히 놓아서 만들 수 있는 최소 침투 소대수라고 정의하고 다이나믹 프로그래밍으로 풀면 된다. 이 문제에서 까다로운 점은 구역이 원형으로 연결돼 있다는 점인데, 이는 처음과 끝에 이미 몇개의 소대를 보내 놨다고 생각 (이러면 선형구조로 생각할 수 있음) 하고, 그 경우에 대해 모두 돌려보면 된다. 길이 N에 처음과 끝을 가정하는 경우의 수는 상수번 이므로 O(N)에 풀린다. 코드 : http://ideone.com/XPpr2X 비슷한 문제 (이 문제를 푸는데 동원된 아이디어와 비슷한) : https://www.acmicpc.net/problem/9465 https://www.acmicpc.net/problem/2133 https://www.acmicpc.net/problem/2482 https://www.acmicpc.net/problem/4017
계속 읽기