BOJ 문제풀이 109

백준 1904 c++ 풀이

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 문제를 풀어보겠습니다. 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을 계속 나눈 나머지를 대입합니다. 코드: #..

BOJ 문제풀이 2021.07.30

백준 10870번 c++ 풀이

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 문제를 풀겠습니다. 피보나치 수열은 워낙 유명해서 다들 아시죠? 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) =..

BOJ 문제풀이 2021.07.30

백준 9095번 c++ 풀이

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 알고리즘 문제를 풀어보겠습니다. 경험상, 일반적인 다이나믹 프로그래밍 문제는 점화식이 많은 것 같습니다. 위 문제도 똑같습니다. 잘 생각하면 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)임을 구했습니다. 그냥 재귀 호출로 하면 시간이 오래걸리므로 벡터를 하나 만들어서 호출할떄 마다 그 값을 벡터에 저장..

BOJ 문제풀이 2021.07.30

백준 2003번 c++ 풀이

안녕하세요 오늘은 구간합 문제를 풀어보겠습니다. 해결전략: 우선은 '투포인터' 알고리즘을 이용할 겁니다 화살표는 왼쪽부터 l, r 화살표입니다 밑에 코드와 그림을 대조해 보시길 바랍니다. 코드분류: 투포인터 코드: #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int M, N; cin>> M>>N; vector v(M); for(int i= 0; i> v.at(i); } int l = 0, r = 0,sum = 0, count = 0; while(1){ if(sum >= N){ sum-=v.at(l); l++; } else if(r>=M){ br..

BOJ 문제풀이 2021.07.29