맨위에서 출발해서 아래로 내려가는데 한 루트의 합이 가장 큰 값을 출력
위 문제를 해결하기 위한 대표적인 알고리즘 세가지를 고려해 볼수 있다.
1.
모든 경우의 수를 다 해볼것인가? 브루트포스(DFS,BFS)
2.
최적의 해를 항상 그시기에 찾는다. 그리디 알고리즘
과거 선택에대한 고려가 전혀 없고 미래를 선택하는 부분도 전혀 고려를 하지 않고 현재기준으로 최적의 값만 선택한다.
3.
DP 이전단계에서 구했던 최적의 값과, 현재상황에서 구한 값을 비교하여 더 최적의 값을 찾는 알고리즘이다.
또 다른 예로 앞서 풀어봤던 문제중에 거스름돈 문제가 있다.
1260원을 만드는 경우 이것 또한 그리디 알고리즘의 하나로 볼수 있다.
3,4,5원의 동전을 가지고 15원을 만들어본다고 가정해보자.
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main()
{
int n = 28; //거스름돈
int change[4] = { 5, 4, 3 }; //거스름돈 종류
int count[4] = {}; //거스름돈 개수
for (int i = 0; i < 4; i++)
{
count[i] += n / change[i];
n %= change[i];
}
return 0;
}
Python
복사
위문제를 DP로 풀어보자
전형적이고 대표적인 기본 DP 문제이다. dp 테이블을 만들어서 문제를 해결하면 된다.
만들어야할 테이블의 크기를 정해준다. 금액보다 +1 한개 크게 만들어주면 된다.
3원의 동전만 가지고 15원의 거스름돈을 거슬러 줄수 있는 경우의수 테이블을 만들어보자
이번에는 3,4원의 동전을 가지고 만들수 잇는 경우의 수를 생각해보자
거스름돈이 4원이 만들어질때까지는 3원까지의 조합과 동일하다.
4원부터는 달라진다.
5원의 경우에는 3,4원으로 만들수 있는 경우의수가 없다.
그렇다면 3,4원으로 5원을 거슬러 줄 경우에는 4원을 내주고 1원을 거슬러줄 조합이 있을까 볼수있다.
노란색이 현재 동전을 추가하기전 해당 돈을 거슬러 줄 수 있는 경우의 수이고 초록색이 가지고있는 가장 큰 동전을 하나 먼저 거슬러주고 남은 돈을 거슬러 줄 수 있는지에 대한 정보다. 0+0은 0이기 때문에 (3, 4) 조합으론 5원을 거슬러줄 수 없다
6원의 경우 (현재 동전이 추가되기전 거슬러줄 수 있는 경우의수 1) + (4원 거슬러주고 남은 2 원 거슬러줄 수 있는 경우의수 0) = 1이 된다.
7원의 경우 (현재 동전이 추가되기전 거슬러줄 수 있는 경우의수 0) + (4원 거슬러주고 남은 3 원 거슬러줄 수 있는 경우의수 1) = 1이 된다.
결과적으로 이것들은 패턴이 보이기 시작한다.
7원의 경우 (현재 동전이 추가되기전 거슬러줄 수 있는 경우의수 0) + (4원 거슬러주고 남은 3 원 거슬러줄 수 있는 경우의수 1) = 1이 된다.
dp[index] += dp[index - 현재 동전]
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main()
{
// 동전 집합과 목표 금액
vector<int> coins = {3,4,5};
int amount = 15;
// DP 테이블 초기화
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int coin : coins)
{
for (int i = coin; i <= amount; i++)
{
dp[i] += dp[i - coin];
}
}
// 결과 출력
if (dp[amount] == 0)
{
cout << "해당 금액을 만들 수 없습니다." << endl;
}
else
{
cout << amount << "원을 만들기 위한 최소 동전 개수: " << dp[amount] << endl;
}
return 0;
}
Python
복사
“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고,
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,
•
질문할 곳도 없고,
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.
문제는 ‘연습’이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.
실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
그래서, 얌얌코딩 코칭은 다릅니다.
그냥 가르치지 않습니다.
스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌,
스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
마침내 자신의 힘으로 코드를 끝까지 작성하는 경험
지금 필요한 건 더 많은 강의가 아닙니다.
코드를 스스로 완성해 나가는 훈련,
그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기 또는 카카오톡 상담방: 얌얌코딩 상담방