전체보기96 Dynamic Programming Design Pattern (동적 계획법) 분할 정복(DC로 줄이겠음)에 이어서 이번에는 Dynamic Programming(동적 계획법, DP로 줄이겠음)이라는 디자인 패턴에 대해 알아보자. Introduction to Dynamic Programming 제목에 DP에 대한 해석을 '프로그래밍'이 아닌 '계획'으로 했다. 즉 DP의 Programming은 컴퓨터 프로그래밍이 아닌 계획을 의미한다. 원래 DP는 다단계의 의사결정을 최적화하기 위한 방법이었는데, 현재는 최적화 기법의 특정 유형으로 제한되는 일반적인 알고리즘 설계 기법이다. 말이 좀 어려운것 같다. 다르게 설명하자면 DP는 중복되거나 종속적인 하위 문제로 문제를 해결하기 위한 기술이다. 일반적으로, recurrence relation에서 하위 문제가 발생한다. 이 방법은 중복되는 하.. 2021. 10. 13. Divide and Conquer design pattern(분할정복) 이전에는 알고리즘의 효율성을 판단하는 방법을 살펴봤었다. 이제 처음에 언급했듯이 하나의 디자인 패턴을 이용하여 몇가지 문제를 해결해보고 이를 분석해보자. Introduction to Divide-and-Conquer divide&conquer. 한글로 해석하면 나눠서 정복하는 것이다. 즉 input으로 주어진 instance가 너무 거대할 때, 이를 두개 이상의 작은 부분으로 나누어 이것들을 하나씩 해결해나가는 것이다. 작은 부분들을 해결한 결과물을 합치게되면 원래 해결하고자 했던 문제를 해결할 수 있게 되는 것이다. 만약 나눠진 문제가 해결하기에 여전히 큰 문제라면, 이를 해결할 수 있을 때까지 더 작은 조각으로 나눌 수 있다. 이러한 divide&conquer 접근은 original problem의 .. 2021. 10. 4. Assemblers (1) SIC/XE에 관해 이전까지 알아보았다. 알아봤듯이 컴퓨터는 기계어(0과 1로만 구성된) 명령을 들으면 그것을 수행한다. 하지만 우리는 c나 python같은 언어로 코드를 작성하여 프로그램을 만든다. 그러므로 당연히 이러한 코드를 기계어로 변환하는 과정이 필요한 것이다. 그러한 역할을 하는 프로그램 중 이번에는 Assember(어셈블러)에 대해 알아볼 것이다. Translating and Starting a Program 컴퓨터가 처음 나왔을 때는 프로그래머들은 기계어로 컴퓨터를 제어했다(처음에는 그 이외의 방법은 존재하지 않았으니깐). 하지만 위에서 설명했듯이 기계어는 기계가 이해하기에는 매우 좋지만 사람이 이해하기는 너무나도 어렵다. 때문에 지금은 프로그램을 프로그래밍 언어로 작성하고 이것을 기계어로.. 2021. 9. 28. Algorithm Efficiency(알고리즘 효율성) 저번 포스팅에서 알고리즘을 평가할 때 'Efficiency'라는 항목이 있었다. 이번에는 이것에 대해 자세히 알아볼 것이다. Basic concepts Algorithm Efficiency Efficiency는 두가지로 나눌 수 있다. Time Efficiency(Time complexity): 얼마나 빠르게 알고리즘이 동작하는가? Space Efficiency(Space complexity): 알고리즘이 동작하는데 필요로하는 메모리 단위의 양 우리는 알고리즘의 시간/공간 효율성을 파악하기 위해 general analytical framework를 따를 것이다. 그 전에 몇가지 질문에 대한 답을 확인해보자. How to express the efficiency of an algorithm? 우선, 알고리.. 2021. 9. 18. 이전 1 ··· 17 18 19 20 21 22 23 24 다음
