동적프로그래밍 (Dynamic Programming)에 대하여

❓ 동적 프로그래밍이란 동적 프로그래밍(이하 DP)는 컴퓨터 프로그래밍이 아니라 테이블을 만드는 것이다. 또한 전혀 다이나믹하지 않아 기억하기 프로그래밍이라고도 불린다. 반복적으로 계산되는 것들을 저장해두었다가 사용하는 메모이제이션 방법이 DP의 한 방법이다. 알고리즘을 짤 때 Divide and Conquer 방법을 많이 사용하는데 이 때 한 문제를 여러 개의 작은 문제로 나누어 풀게되어 ...

dynamic programmingDP동적프로그래밍알고리즘algorithmlogicDP

프로그래머스 - 정수 삼각형(java)

🔺문제 동적계획법(Dynamic Programming) 카테고리의 level3 문제다. 🔺동적프로그래밍 처음엔 동적프로그래밍이 뭔지 공부도 안하고 모든 경우의 수를 재귀로 풀려고 했다. 역시나 효율성 제로ㅎ 동적프로그래밍이 무엇인지 찾아보니.. < 동적프로그래밍 > 큰 문제를 작은 문제로 분할하여 해결하는 알고리즘이다. 작은 문제는 반복되지 않고 풀때마다 항상 값이 같다. 작은 문제의 답을 ...

dynamic programming정수삼각형프로그래머스자바Java동적프로그래밍코딩테스트동적계획법Java

Programmers - 피보나치수

Memoization(메모이제이션: 동일한 연산을 반복할 때 값을 저장) 처음에 피보나치란 단어를 보자마자 아래와 같이 코드를 바로 작성해서 제출을 했었다. 위에 작성한 함수의 시간복잡도를 생각해보면 O(2^n) O(2n)으로 굉장히 비효율적이다. 2. Memoization(메모이제이션: 동일한 연산을 반복할 때 값을 저장) 그래서 다음으로 시도를 해본 것은 Memoization이다. 재귀호...

level2동적프로그래밍피보나치level2

[boj] 1912. 연속합 (node.js)

문제 요약 연속합의 최댓값을 구하라. 풀이 n의 최댓값이 100,000 이므로 시간 제한 내에 풀이하기 위해서는 O(N)의 풀이가 필요하다. 일차원 배열 dp값을 채운 후 최댓값을 출력한다. 점화식 dp[i] = Math.max(dp[i-1]+arr[i], dp[i]) 일차원 배열을 돌며, Math.max로 기존 값 또는 누적 값과의 합 중 더 큰 값을 배열에 저장한다. 연속합이 기존 값보다...

동적프로그래밍알고리즘동적프로그래밍