본문 바로가기

자바(Java)/알고리즘-프로그래밍 콘테스트 챌린징4

동적 설계법 - 값을 기억해서 재활용한다. -2 메모화 테이블 동적 설계법 - 값을 기억해서 재활용한다. 메모화 테이블 이전 글에서 메모화 테이블을 보고 왔다.메모화 테이블은 간단하게 말해 이전 값을 기억해서 불필요한 연산을 줄이는 것이다. 하지만 이것을 잘만 이용한다면 동일한 문제에 대해서 더욱더 간결하게 해결 할 수 있다. int[] w = {2, 1, 3, 4};int[] v = {3, 2, 4, 9}; mt[i][j]i : 아이템의 인덱스j : 무게의 총합. 메모화 테이블 mt[i][j] 는 함수 recursive 의 정의보다 i 번째 이후의 무게의 총합이 j 이하가 되도록 고른 경우의 가격 총합이 최대치가 되게 하고 있다.이를 수식으로 보면mt[i+1][j]=mt[i][j] | (j 2016. 10. 11.
동적 설계법 - 값을 기억해서 재활용한다. -1 동적 설계법(DP : Dynamic Programming)이란 알고리즘 설계 기법의 하나로서 프로그래밍 콘테스트에서 매우 자주 출제됩니다. 탐색 메모화 및 동적 설계법 베낭문제(Knapsack problem)무게와 가격이 각각 wi, vi인 n개의 물건이 있습니다. 무게의 총합이 W를 초과하지 않도록 물건을 선택했을 때 가각 총합의 최대치를 구하세요.예)입력n = 4(w, v) = {(2, 3), (1, 2),(3, 4), (4, 9)}W = 7 출력 14 ( 4, 0, 2 번 물건을 고른다) 이것은 배낭 문제라고 불리는 유명한 문제입니다. 이 문제는 어떻게 접근하면 좋을까요? 우선 일반적인 방법으로 생각해보면 (넣는다/안 넣는다) 이 두 가지 상태로 분기하면서 탐색하는 방법을 생각할 수 있습니다. 코드.. 2016. 10. 11.
제비 뽑기-알고리즘 해결. 알고리즘-이진탐색 제비 뽑기 어느 날 친구가 봉지를 들고 와 당신에게 게임을 제안했습니다. 봉지에는 숫자가 쓰여 있는 n장의 종이가 들어 있습니다. 당신은 봉지에서 종이를 한 장 뽑고, 숫자를 확인한 후 다시 봉지에 넣는 동작을 4번 반복하여, 그 숫자의 합이 m이면 당신의 승리, 그렇지 않으면 친구가 승리하게 됩니다. 당신은 이 게임을 몇 번이나 해 보았지만 한번도 이기지 못했습니다. 화가 난 당신은 봉지를 찢어 보든 종이를 꺼낸 후 정말 이길 수 없었는지를 조사했습니다. 종이에 쓰여 있는 숫자가 k1, k2, … , kn 일 경우 합이 m 이 되는 경우가 있는 지를 조사하고, 방법이 있다면 Yes, 없다면 No 를 출력하는 프로그래밍을 장성하세요. 요약n개의 숫자가 적힌 종이가 주머니에 들어 있고, .. 2016. 10. 6.
알고리즘 책 “프로그래밍 콘테스트 챌린징” 책에 있는 예제를 기반으로 하여 알고리즘에 대해 정리를 하려고 한다.책에 있는 예제가 c++ 코드로 되어 있는 부분을 java 언어로 변경하여 포스팅 할 것이다. 포스팅 주기는 아마 들쑥날쑥 하겠지만… 계속해서 해 보려한다. -------------2016.10.11 - 추가좋은 책인 것은 확실하나 오타와 그림이 잘못된 경우가 있다.간혹 중요한 부분에서 오타와 잘못된 그림이 이해를 힘들게 한다.이 곳에 공부한 것을 정리해서 올릴 때는 그림을 수정하고 오타를 수정해서 올리고 있으므로 이 블로그에서 보시는 분은 믿고 보셔도 됩니다. 2016. 10. 6.

티스토리툴바