728x90 dp1 다이나믹 프로그래밍(Dynamic Programming) 안녕하세요. 옆집 컴공생입니다. 오늘은 다이나믹 프로그래밍에 대해 배워 보겠습니다. DP 라고도 부르죠. 다이나믹 프로그램은 알고리즘 문제를 푸는 큰 축인데요. 꼭 익혀놓아야 하는 부분입니다. 컴퓨터적인 사고력을 물어보기에 적합하기 때문에 자주 출제되기 때문이라고 합니다. ▶다이나믹 프로그래밍이란 '하나의 문제는 단 한번만 풀도록 하는 알고리즘' 입니다. 한번 푼걸 다시 여러번 푸는건 비효율적이겠죠? 이런 알고리즘을 개선시키는 방안입니다. ▷분할 정복 기법(Divide and Conquer)은 동일한 문제를 다시 푼다는 단점을 가지고 있습니다.(정렬과 같은 경우 다시 푸는 경우가 없습니다. 퀵정렬과 병합정렬이 빠른 이유입니다.) 예를 들어 피보나치 수열을 심각한 비효율성을 낳는데요. 피보나치 수열은 특정.. 2020. 6. 7. 이전 1 다음 728x90
