알고리즘/백준 알고리즘
[BOJ] 11444 피보나치 수 6
문제 링크 www.acmicpc.net/problem/11444 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제는 일반적인 재귀함수로 풀면 시간 초과를 받고, 메모이제이션을 적용하려 해도 메모리 제한에 걸리게 된다. 이 문제는 피보나치 수를 행렬로 생각하고, 행렬의 거듭제곱을 이용해서 풀어야 한다. 현재 피보나치 수와 이전 수를 각각 1행, 2행에 배치한 2X1 행렬을 생각해보자. 이 다음 피보나치 수를 구하려면 두 수를 더한 수를 첫 번째 행에, 기존에 첫 번째 행에 있던 현재 피보나치 수는 두 번째 행으로 옮겨줘야 한다. 이런 동작은 아래와 같은 행렬 곱셉으로 간단하게 수행할 수 있다. 현재 피보나치 수가 1, 이전 피보나치 수가 1이라고 했을 때, 행렬 [[1 1], [1 0]]을 곱해주..
[BOJ] 15998 카카오머니
문제 링크 www.acmicpc.net/problem/15998 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제를 풀기 위해서는 각각의 출금 금액을 기록해두고, 이 금액들의 최대공약수를 구해야한다. 유클리드 호제법을 사용하면 빠른 시간안에 최대공약수를 구할 수 있다. ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } 입/출금액은 최대 10^18원 까지 가능하므로 long long형을 사용했다. 출금 금액에서 구한 최대공약수를 뺐을 때도 필요한 금액을 낼 수 있다면, 필요 이상으로 인출을 한 것이므로 이 경우 답이 존재하지 않는다. 이러한 경우가 발생하지 않는다면 구한 최대공약수가 답이 된다. 또한 출금을 아예 하지 않았다면 ..
[BOJ] 15997 승부 예측
문제 링크 www.acmicpc.net/problem/15997 모든 알고리즘 문제는 C++로 구현되어 있습니다. 오늘은 2018년 카카오 코드 페스티벌에서 출제된 문제를 풀어봤다. 문제를 처음 봤을 때는 어떻게 풀어야 할지 감이 잘 잡히지 않았지만 리그에 참여하는 국가와 경기 수가 4, 6이라는 작은 수로 정해져 있어 모든 경기 결과를 완전탐색하면 문제를 해결할 수 있을 것이라 생각했다. 문제에서 주어진 각 경기에 대한 정보는 구조체를 이용하기로 하고 아래와 같은 구조체를 생성했다. typedef struct game { int x, y; double win, draw, lose; }Game; x와 y는 참가하는 국가를 입력 순으로 번호를 매겨서 저장하기로 했으며, win, draw, lose에는 각각..