huiyu's blog

백준 기업투자 문제 : https://www.acmicpc.net/problem/2662 문제 요약- 일정금액을 기업들에게 돈을 투자해서 최대 이익을 얻고자한다.- 투자액이 정해져 있고 기업의 개수와 기업에 투자할 이익이 주어질 때, 가장 많은 이익을 얻을 수 있는 투자방식과 이익금을 구하기위의 경우 최대 이익을 얻는 경우는 B기업에만 4만원을 투자하는 경우 15만원입니다. 우선 문제의 기본 입력을 받고 필요한 함수를 구현합니다.123456789101112131415161718192021222324252627282930#include using namespace std; int arr[301][21];int DT[301][21]; int M, C; int MAX(int a, int b){ return (..

백준 9465번 스티커 문제 풀이 : https://www.acmicpc.net/problem/9465 문제요약 : - 2xn개의 스티커를 갖고있다. 각 스티커는 점수가 있다.- 스티커를 떼면 그 스티커와 변을 공유하는 스티커는 찢어져 사용할 수 없다(점수x)- 뗄 수 있는 스티커 점수의 최댓값을 구하시오. 우선 이런 유형의 문제는 완전탐색을 하여 구현을 해봅니다.. 그다음 DP를 적용.. 1. 완전탐색을 할 경우를 생각해봅니다. "-->" 오른쪽 방향으로 탐색을 했을 때, 스티커를 떼는 방법은 위를 떼는 방법, 그리고 아래를 떼는 방법 두가지가 존재합니다. 우선 공유하는 변의 스티커가 뜯어지는 경우를 무시하고 전체 경우를 구한다면, 아래와 같이 구현할 수 있습니다. 12345678int solve(in..

배낭문제(Knapsack Problem)란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다 배낭에 짐을 넣을 때,짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데, 쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem),쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부릅니다. 쪼갤 수 없는 0-1 Knapsack의 경우 동적계획법(Dynamic Programming)으로 풀 수 있습니다. -> 위키백과 냅색 문제는 아래 링크에서 풀어 볼 수 있습니다. ->0/1 Knapsack 문제 보러가..

Dynamic Programming(DP) , 동적 계획법 - 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 -> 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것 -> 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결 * 동적계획법은 계산 횟수를 줄일 수 있다. 특히 하위 문제의 수가 기하급수적으로 증가할 때 유용 위키 (https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95) *피보나치 수로 DP 기초 다지기 F(0) = 0 F(1) = 1 F(N) = F(N-1)+F(N-2) (N>=2) 0 ..