728x90 Dynamic Programming2 다이나믹 프로그래밍(Dynamic Programming) 안녕하세요. 옆집 컴공생입니다. 오늘은 다이나믹 프로그래밍에 대해 배워 보겠습니다. DP 라고도 부르죠. 다이나믹 프로그램은 알고리즘 문제를 푸는 큰 축인데요. 꼭 익혀놓아야 하는 부분입니다. 컴퓨터적인 사고력을 물어보기에 적합하기 때문에 자주 출제되기 때문이라고 합니다. ▶다이나믹 프로그래밍이란 '하나의 문제는 단 한번만 풀도록 하는 알고리즘' 입니다. 한번 푼걸 다시 여러번 푸는건 비효율적이겠죠? 이런 알고리즘을 개선시키는 방안입니다. ▷분할 정복 기법(Divide and Conquer)은 동일한 문제를 다시 푼다는 단점을 가지고 있습니다.(정렬과 같은 경우 다시 푸는 경우가 없습니다. 퀵정렬과 병합정렬이 빠른 이유입니다.) 예를 들어 피보나치 수열을 심각한 비효율성을 낳는데요. 피보나치 수열은 특정.. 2020. 6. 7. 탐욕 알고리즘(Greedy Algorithm) 안녕하세요. 부산 공수니 입니다. 오늘은 탐욕 알고리즘에 대해 알아보겠습니다. Dynamic Programming과 Divide and Conquer 과 더불어 중요하다고 판단이 되는 알고리즘입니다. 단어의 부정적인 부분 때문에 탐욕 알고리즘을 안 좋다고 생각할 수도 있지만 사실 탐욕 알고리즘이 효율적이고 간단한 경우도 많습니다. : 미리 정한 기준에 따라 가장 좋아보이는 답을 선택 ! 이는 동적 프로그래밍과 더불어 최적화 문제를 푸는데 사용됩니다. 상대적으로 탐욕 알고리즘이 설계하기 더 쉽습니다. 물론 이게 최적화된 알고리즘인지에 대한 증명이 반드시 필요합니다 .동적 프로그래밍은 재귀 관계식을 세워서 입력사례를 더 작은 입력사례로 분할하짐나 탐욕 알고리즘은 입력사례를 분할하지 않습니다. 그저 더 좋아보.. 2020. 5. 21. 이전 1 다음 728x90
