알고리즘3 Divide and Conquer design pattern(분할정복) 이전에는 알고리즘의 효율성을 판단하는 방법을 살펴봤었다. 이제 처음에 언급했듯이 하나의 디자인 패턴을 이용하여 몇가지 문제를 해결해보고 이를 분석해보자. Introduction to Divide-and-Conquer divide&conquer. 한글로 해석하면 나눠서 정복하는 것이다. 즉 input으로 주어진 instance가 너무 거대할 때, 이를 두개 이상의 작은 부분으로 나누어 이것들을 하나씩 해결해나가는 것이다. 작은 부분들을 해결한 결과물을 합치게되면 원래 해결하고자 했던 문제를 해결할 수 있게 되는 것이다. 만약 나눠진 문제가 해결하기에 여전히 큰 문제라면, 이를 해결할 수 있을 때까지 더 작은 조각으로 나눌 수 있다. 이러한 divide&conquer 접근은 original problem의 .. 2021. 10. 4. 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. Introduction: 알고리즘에 대해 이번 학기에 알고리즘 과목을 수강하게 되었다. 취업할 때 코테같은걸 하려면 알고리즘을 알아야 한다고 하는데 '아직 2학년인데 이걸 들어도 되나?' 라는 생각을 지금도 가지고 있다. 하지만 전필이기도 하고 아직 뭘 들어야할지 몰라서 수강을 하게 되었다. 수업 소개를 들어보니 코테처럼 문제를 풀기위해 알고리즘을 배운다기 보다는 알고리즘 자체에 중점을 둔 것 같았다. 수업내용을 나름대로 정리해서 올리기로 마음먹었으니 한 번 시작해보도록 하자. (원어 강의이기도 하고 나도 영어표현에 익숙해져야 한다고 생각해서 영어를 자주 섞을 생각이다.) 이 카테코리의 게시글들은 아주대학교 Sinshaw Yenewondim Biadgie 교수님의 '알고리즘' 수업을 바탕으로 한다 웬만한 수업의 첫시간은 수업 주제에 대한 소개이.. 2021. 9. 6. 이전 1 다음
