늘 겸손하게

wrote by : besforyou 문제 해설 n이 주어지고, 위 피보나치 함수를 실행했을때 0과 1이 반환되는 횟수를 출력하는 문제입니다. 단순히 위 함수를 실행해서 반환되는 0과 1의 횟수를 직접 구하는 알고리즘은 시간 초과가 뜹니다. 그래서 dp를 적용하여 문제를 해결해야합니다. 문제풀이 fibonacci(0)은 0을 1번, 1을 0번 반환하고 ---- (a) fibonacci(1)은 0을 0번, 1을 1번 반환합니다. ---- (b) fibonacci(2)는 fibonacci(1) + fibonacci(0)을 반환합니다. 그러므로 0을 1번, 1을 1번 반환합니다. ( a + b ) 위를 통해서, n이 주어졌을때 0과 1이 반환되는 횟수는 함수에 n-1이 주어졌을때 반환한 0과 1의 개수와 함수..

처음으로 한방에 풀어버린 dp 문제네요 문제 풀이 numRows의 범위가 1 이상 30 이하이므로 파스칼의 삼각형을 미리 만들어버리고 numRows값에 따라 알맞은 vector

DP 문제를 처음으로 스스로 풀었네요 문제 풀이 모든 경우를 다 구하려면 시간 초과가 나오므로 dynamic programming으로 풀어야 한다. 1. 합이 최대가 되는 경로에 있는 수의 합을 출력해야 하고, 위에서 아래로 내려갈 때 더 큰 숫자가 있는 방향으로 나아가야 하므로 두 개의 숫자를 비교한 후 더 값이 큰 숫자를 반환하는 함수를 만들어두자. 2. 삼각형의 맨 위에서 아래로 내려가는데, 더 큰 수가 있는 방향으로 내려가고 더 큰 수를 합하면서 맨 아래까지 내려가야 한다. -> 이 과정에서 지금까지 합한 값을 기록해야 하고 다음 값을 계산할 때 기록한 값을 사용한다. 3. edge case 주의 : 맨 오른쪽 정수는 바로 윗줄의 맨 오른쪽, 맨 왼쪽 정수는 바로 윗줄의 맨 왼쪽만 선택 가능하다...

출처 : https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 문제를 풀기 위해, 문제를 여러 개의 하위 문제 (subproblem)으로 나누어 푼 다음, 그것을 결합하여 최종 목적에 도달하는 것 하위 문제의 해결방법을 찾았는데 같은 하위 문제가 계속해서 나올 경우 계산 횟수를 줄일 수 있다. 출처 : https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182 이름은 다이내믹 프로그래밍이지만 전혀 다이나믹하지도 않고 프로그래밍이라기보다는 테이블을 만드는 기법입니다. 대표적인 동적 프로그래밍으로 ..