[알고스팟/ALGOSPOT] 10. PACKING 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 10번 문제는 PACKING이라는 문제입니다.!! 이 문제는 동적계획법 대표 문제입니다. 가방 문제라고도 불리구요! 문제 개요 입력에서 테스트 케이스가 주어집니다. 테스트 케이스당 물건의 개수 N과 가방의 용량 W가 주어집니다 그리고 N개의 줄에 걸쳐 물건의 이름과 부피, 절박도(가치)가 주어집니다.N개의 물건을 용량내로 최대한의 가치, 절박도로 채워야 하는 것이 목표입니다. 최대 가치와, 물건 개수, 물건의 이름들을 출력해야 합니다. (경로 추적이 필요합니다~) 문제 풀이 최대 가치만 구하라 하면 동적계획법만을 사용하면 되지만, 물건의 개수와 이름을 구해야하기 때문에 추가적으로 재귀함수를 이용하여 경로를 추적합니다. 동적 계획법 부분 점화.. 더보기 [알고스팟/ALGOSPOT] 9. JOSEPHUS 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 JOSEPHUS라는 문제로!! 원탁의 기사같은 연결리스트 문제입니다!! 문제 개요 입력에서 테스트 케이스가 주어지면 테스트 케이스마다 N명의 사람과 1번이 죽었을 때 그 사람으로 부 터 몇 번째인 사람이 죽을 K가 주어집니다. 1번부터 시작하여 차근차근 죽어가고 마지막으로 살아남는 2명의 사람을 출력하는 문제가 되겠습니다. 문제 풀이 N개의 입력을 받고 1번부터 N번까지 연결리스트를 구축을 합니다. 그러면 위치는 마지막 N번이 되어있습니다. pre를 N번, cur을 1번으로 하게끔 1~n을 동적할당 합니다. 여기서부터 pre의 next를 cur의 next로 바꾸어주어 1번을 지우고 pre는 그대로, cur은 다음으로 넘어갑니다. 총개.. 더보기 [알고스팟/ALGOSPOT] 8. CONCERT 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 동적계획법을 이용하여 해결하는 CONCERT라는 문제입니다. 문제 개요 먼저 입력에서 테스트 케이스가 주어지면 테스트 케이스 당 2줄씩 입력이 주어집니다. 첫 번째 줄에는 곡의 개수, 시작 볼륨, 최대 볼륨이 2번째 줄에는 곡의 개수만큼의 볼륨이 주어집니다. 여기서 각 볼륨을 키우든 줄이든 하여 볼륨이 0보다 작지 않고, VM보다 크지 않는 것들 중에서 가장 큰 값을 출력하라는 문제입니다. 문제 풀이 이 문제는 동적계획법을 어떻게 활용할까를 생각한다면 해법을 찾을 수 있다. 각 단계별로 볼륨을 만들 수 있는 것들을 모두 어떻게 저장을 할 것인가에 주목을 하여 생각을 해야 한다. 글씨가 읽기 힘드실텐데..ㅠㅠ 죄송합니당 먼저 입력을 받.. 더보기 이전 1 ··· 13 14 15 16 17 18 19 다음
