본문 바로가기

전체 글153

동적 설계법 - 값을 기억해서 재활용한다. -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.
CentOS 실행&중지 스크립트 Java jar 실행 스크립트 만들기 리눅스 환경에서 일을 하다 보면 jar 파일을 실행시키고 정지 시키는 일을 해야 할 때가 있는대 스크립트로 만들면 편하다. startup.sh #!/bin/bash echo "start!!" nohup java -jar myJavaApp.jar & nohup : nohup.out 파일에 로그가 쌓인다.마지막에 있는 & 표시는 백그라운드로 실행되라는 의미이다. shutdown.sh #!/bin/bash # Getting the PID of the process PID='myJavaApp' echo $PID kill kill -9 $(ps -ef | grep $PID | grep -v grep | awk '{ print $2 }') echo succeed 현재 만들어진 .. 2016. 10. 11.
제비 뽑기-알고리즘 해결. 알고리즘-이진탐색 제비 뽑기 어느 날 친구가 봉지를 들고 와 당신에게 게임을 제안했습니다. 봉지에는 숫자가 쓰여 있는 n장의 종이가 들어 있습니다. 당신은 봉지에서 종이를 한 장 뽑고, 숫자를 확인한 후 다시 봉지에 넣는 동작을 4번 반복하여, 그 숫자의 합이 m이면 당신의 승리, 그렇지 않으면 친구가 승리하게 됩니다. 당신은 이 게임을 몇 번이나 해 보았지만 한번도 이기지 못했습니다. 화가 난 당신은 봉지를 찢어 보든 종이를 꺼낸 후 정말 이길 수 없었는지를 조사했습니다. 종이에 쓰여 있는 숫자가 k1, k2, … , kn 일 경우 합이 m 이 되는 경우가 있는 지를 조사하고, 방법이 있다면 Yes, 없다면 No 를 출력하는 프로그래밍을 장성하세요. 요약n개의 숫자가 적힌 종이가 주머니에 들어 있고, .. 2016. 10. 6.

티스토리툴바