728x90 C++33 Greedy algorithm (탐욕 알고리즘) // Greedy algorithm What is Greedy algorithm? 답을 하나씩 골라가는데, 미리 정해놓은 기준에 따라 매번 가장 좋아 보이는 답을 선택하는 것이다. 하지만 을 이용하여 설계를 한다면 항상 최적의 해는 보장할 수 없다. Example 의 예시로 가장 많이 보여지는 것들 중 하나인 "거스름돈 문제"를 예시로 들어보자. "거스름돈 문제"란, 임의의 액수만큼 거스름돈을 주어야 하는데 최소한의 개수의 동전을 사용하여 주어야 할 때 해당되는 동전들을 고르는 문제이다. 예를 들어 만약 거스름돈으로 520원을 주어야 한다. 이때 520원을 줄 수 있는 방법은 다양하다. 하지만 상식적으로 10원짜리 동전 52개로 거슬러주는 것보단 500원짜리 동전 1개와 10원짜리 동전 2개로 거슬러주는.. 2020. 11. 10. 백준 No.1149 [RGB거리] // Baekjoon Online Judge No.1149 [RGB거리] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include using namespace std; int N; int price[1001][4]; int minSum[1001][4]; int main() { cin >> N; for (int i = 1; i price[i][j]; } } minSum[1][1] = price[1][1]; minSum[1][2] = price[1][2]; minSum[1][3] = price[1][3]; for (int i = 2; i 2020. 11. 10. 백준 No.1904 [01타일] // Baekjoon Online Judge No.1904 [01 타일] How to solve 복잡할 것 같아 보이지만 N에 1, 2, 3 ... 8 까지만 대입 해보아도 결국 피보나치수열을 이룬다는 것을 알 수 있다. 하지만 이 문제에서 고려해야하는 점이 두 가지 있다. 1. 피보나치 수열을 구하는 함수를 구현할 때 1,000,000번째 항까지 구해야 하므로 Time out 이 생기지 않을 방법으로 함수를 구현하여야 한다. 2. 아무리 unsigned long long 자료형을 가진다고 해도 1,000,000번째 피보나치수는 overflow를 발생시킨다. "1. 피보나치 수열을 구하는 함수를 구현할 때 1,000,000번째 항까지 구해야 하므로 Time out 이 생기지 않을 방법으로 함수를 구현하여.. 2020. 11. 6. 이전 1 2 3 다음 728x90
