ORTHODOX

안녕하세요 오늘은 동적 계획법 문제를 풀어볼 것입니다. 전략: 1. P(n)의 값을 n+1번째 원소로 하는 배열을 선언해주고, P(n) 함수를 선언해준다. 2. P(n) = P(n-2) + P(n-3)임을 이용하여 P(n)함수를 정의해준다. 코드: #include using namespace std; long long int arr[101] = {0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, }; long long int P(int n){ if(arr[n]){ return arr[n]; } else{ arr[n] = P(n-2) + P(n-3); return arr[n]; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); i..

안녕하세요 오늘은 다이나믹 프로그래밍 및 브루트 포스를 이용한 문제를 풀어보도록 하겠습니다. 전략: 1. 범위가 50000까지이니까 길이 50001짜리 배열을 만들어서 동적 계획법을 이용할 준비를 한다. sq라는 함수를 이용하여 재귀를 구현할거다. 2. 만약 arr[a]가 존재를 하면, arr[a]를 return해줍니다. 그것이 아니면 arr[a]의 값을 집어넣어줘야하는데, 만약 a의 제곱근을 제곱한 값이 a와 같다면 arr[a]에 1을 대입해주고, 1을 반환해준다. 3. 그렇지 않다면 count라는 변수를 만들어서 1(arr[i*i]) + sq(a-temp)를 대입해준다. 그리고 min와 비교하여 더 작은 값을 min에 대입해준다. for문이 끝났을 때 min값을 arr[a]에 대입해준다. 코드: #i..

안녕하세요 오늘은 동적계획법을 이용한 피보나치 수열 문제를 풀어보겠습니다. 전략: 1. long long int타입으로 v라는 array를 생성해줍니다. 2. long long int타입으로 return하는 fibo라는 함수를 선언해주고, 0이면 0을, 1이면 1을 반환해줍니다. 3. 만약 v[n]이 비어있다면 v[n]은 fibo(n-1) + fibo(n-2)로 넣어주고, 차있다면 v[n]을 반환해줍니다. 코드: #include using namespace std; long long int v[100]; long long int fibo(int n){ if(n==0){ return 0; } else if(n==1){ return 1; } if(!v[n]){ v[n] = fibo(n-1) + fibo(n-..

안녕하세요 오늘은 동적 계획법(다이나믹 프로그래밍)을 이용한 문제를 풀어보겠습니다. 역시 동적계획법 문제는 점화식이 많은 것 같습니다. 이 문제는 w(a, b, c)인 변수가 3개가 필요한 함수이므로 피보나치 풀이와는 다르게 '3'차원 배열을 만들어서 풀겠습니다. 전략: 1. 3차원 배열 arr를 각각 101의 크기로 선언한다.(주어진 범위가 -50~50이기 때문) 2. int w(int a, int b, int c) 함수를 선언한다. 이 함수는 처음 하는 행동이 x = a+50, y = b+ 50, z = c+50을 해준 다음, 만약 arr[x][y][z]가 있으면 계산 할 필요 없이 바로 return해준다. 이부분이 동적 계획법이라고 할 수 있는 부분일 것이다. 3.그 외에는 문제에서 주어진 함수와 ..

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 문제를 풀어보겠습니다. 1 11 00 100, 111, 001, 1001, 1111, 0011, 0000, 1100 10011, 11111, 00111, 00001, 11001, 10000, 11100, 00100 f(n) = {f(n-1) + "1"} + {f(n-2) + "00"} 메모장에 끄적이면서 생각했습니다. f(n)의 경우는 f(n-1) 뒤에 "1"을 붙인 경우와, f(n-2) 뒤에 "00"을 붙인 경우를 합한것입니다. 따라서 개수는 f(n) = f(n-1) + f(n-2)입니다 이것을 구현하겠습니다 주의해야할 점: v.at(n)이 int의 범위를 넘어가지 않도록 v.at(i)을 설정해줄때부터 15746을 계속 나눈 나머지를 대입합니다. 코드: #..

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 문제를 풀겠습니다. 피보나치 수열은 워낙 유명해서 다들 아시죠? F(n) = F(n-1) + F(n-2) 이 문제를 두가지 방법으로 풀었습니다 첫번째는 피보나치 함수를 만들어서 재귀로 호출해주는 방법입니다 코드는 다음과 같습니다. #include using namespace std; int fibonacci(int n){ if(n==0) return 0; if(n==1) return 1; return fibonacci(n-1) + fibonacci(n-2); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a; cin>>a; coutn; n++; v.at(1) = 0; v.at(2) =..

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 알고리즘 문제를 풀어보겠습니다. 경험상, 일반적인 다이나믹 프로그래밍 문제는 점화식이 많은 것 같습니다. 위 문제도 똑같습니다. 잘 생각하면 f(n-3)인 식뒤에 +3, f(n-2)인 식 뒤에 +2, f(n-1)인 식 뒤에 +1을 하면 f(n)을 만드는 식의 모든 경우의 수인것을 알 수 있습니다. f(n)중에 마지막이 +1로 끝나는 모든 경우의 수는 f(n-1) + 1, +2로 끝나는 모든 경우의 수는 f(n-2) + 2, +3으로 끝나는 모든 경우의 수는 f(n-3) + 3입니다 따라서 f(n) = f(n-1) + f(n-2) + f(n-3)임을 구했습니다. 그냥 재귀 호출로 하면 시간이 오래걸리므로 벡터를 하나 만들어서 호출할떄 마다 그 값을 벡터에 저장..

알고리즘 분류: 다이나믹 프로그래밍 코드: #include #include #include using namespace std; int main(){ int a; cin>>a; vector v(1000001); for(int i= 2; i