본문 바로가기

DP

[BOJ] 백준 2629번 양팔저울 (Java)
Dot Algo∙ DS/PS 2021. 5. 3. [BOJ] 백준 2629번 양팔저울 (Java) #2629 양팔저울 난이도 : 골드 2 유형 : DP / 배낭문제(조합최적화) 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net ▸ 문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다. 무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다. 구슬이 3g인 경우..
[알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 3. 9. [알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java) 동적계획법 Dynamic Programming 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로, 이름만 가지고는 무엇을 의미하는지 영 알 수 없기 때문에 가장 많은 오해를 불러 일으키는 주제이기도 하다. Dynamic? 동적? 기억하기? 자료구조의 동적할당(Dynamic Allocation)에서 '동적'은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 그러나, 알고리즘의 동적 계획법(Dynamic Programming)에서 '동적'은 별 뜻 없다 그냥 '기억하기'라고 생각하면 편하다. '프로그래밍'은 컴퓨터 프로그래밍이 아니라 테이블을 만든다는 뜻이다. 중복되는 부분 문제 피보나치 수열을 코딩하려고 한다. 점화식이 F(n) = F(n-..

티스토리툴바

티스토리툴바