pinevienna blog

다이나믹 프로그래밍은 한마디로 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다 큰 문제를 작은 문제로 나눠서 계산하는데, 작은 문제의 결과를 메모리에 저장하여 다시 계산하지 않도록 한다 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다고 함 1) 최적 부분 구조 : 큰 문제를 작은 문제로 나누고, 작은 문제의 답을 모아서 큰 문제를 해결 2) 중복 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야할 때 가장 대표적인 예시로는 피보나치 수열이 있다 1 2 3 4 int fibo(int num){ if(n 2 > 1 10 > 9 > 3 > 1 두 가지 경우를 찾을 수 있다 수가 커졌을 때 이렇게 모든 경우를 찾으려면 답도 없다 이딴식으로는 제공된 시간 0.15초 안에 답을..

단어 수학 문제는 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 문제 너무 오랜만에 하려니까 살짝 당황스러웠던 문제 침착하게 키보드 줘패면서 풀어보니 생각보다 어렵지 않다 풀이 1. 단어가 입력됐을 때 각 알파벳의 비중(?)이 얼마나 큰지 구한다 2. 정렬한다 3. 차례대로 9~1까지 곱해서 더한다 예를 들어 GCF, ACDEB가 입력됐다면 아래와 같이 풀 수 있다 1, 2번 과정 A = 10000 C = 1000 + 10 D = 100 G = 100 E = 10 B = 1 F = 1 3번 과정 A = 1000..

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 문제 좀 어어...? 하다가도 예제를 보면 이해가 간다 이걸 어떻게 잘 설명하지.. 3, 8, 4는 12의 1/4, 2/3, 1/3 이다 첫 번째 링을 한 바퀴 돌렸을 때, 나머지 링이 몇 바퀴 돌아가는지 출력하는 것이므로 과반수 형태가 됐다 (다 첫 번째 링보다 작기 때문에) 1/4인지 2/3인지 뭔지 구할 때 자연스럽게 최대공약수를 구하게 된다 2/3.. 8로 나누어 떨어지지 않으니 각각 4로 나누어서 계산했을 것이다 코드도 똑같이 짜주면 된다 과반수 형태냐 아니냐는 고민할 필요가 없다 분자자리는 첫 번째 링의 반지름/첫 번째 링과 현재 링의 최대공약수 분모자리는 현재 링의 반지름/첫 번째 링과 현..

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다 (?) 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 문제 결과부터 말하자면 N개의 입력값의 차잇값들 중에서 최대공약수를 구하고 그 최대공약수의 약수들을 구해 출력하면 된다 그럼 왜 이런 결론이 나왔느냐..? 수학적으로 접근해서 구해야 한다 1. M으로 나누었을 때 나머지가 같다고 했으니 예시로 주어진 6, 34, 38은 이렇게 표현할 수 있다 ㄱ. 6 = M*몫1+나머지 ㄴ. 34 = M*몫2+나머지 ㄷ. 38 = M*몫3+나머지 2. 위 식에서 나머지 부분을 없애기 위해 ㄴ-ㄱ, ㄷ-ㄴ를 해보자..

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 문제 호제법을 쓰면 된다 호제야.. (백준 2609 최대공약수와 최소공배수, 1934 최소공배수 C++) 백준 2609 최대공약수와 최소공배수를 풀었다 아 뭐야 완전 쉽네~하고 그냥 뒤로 갈라는데 갑자기 싸했다 나는.. 이걸 뭔가 비효율적으로 풀 것만 같은 느낌? 그래서 그냥 바로 솔루션을 찾아봤다 pinevienna.tistory.com 123456789101112131415161718#include using namespace std; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);} int main(void) { int t, n, m; cin >> t; whil..