알고리즘 기초 (3) 썸네일형 리스트형 분할 상환 분석 (Amortized Analysis) 이번 포스트에서는 분할 상환 분석(amortized analysis)에 대해서 알아보도록 하겠습니다. 자료 구조나 알고리즘 수업을 들으셨다면 분명 한 번쯤은 들어 보신 개념일 것입니다. 개인적으로는 자료 구조 수업 시간에 처음 분할 상환 분석에 대해서 배웠었는데요, 당시에는 잘 이해하지 못했던 기억이 있습니다. 아마도 많은 분들이 도대체 분할 상환 분석이 무엇이고, 이것이 어째서 중요한지에 대해 당시의 저처럼 이해하지 못하실 것으로 생각하는데요. 이 포스트를 통해서 그 이유를 알아 가셨으면 하는 바람입니다. 서론: 어느 회사의 커피 이 예제는 제가 대학생일 때 자료 구조 수업에서 교수님께서 분할 상환 분석을 설명하기 위하여 소개한 것입니다. 솔직히 처음 들을 당시에는 제대로 이해하지 못했습니다만, 지금 .. 탐욕 알고리즘 분석하기 (Correctness of Greedy Algorithms) 탐욕 알고리즘(greedy algorithm)은 매번 현재로써 최선인 선택을 "탐욕스럽게" 취하는 알고리즘 기법으로, 문제 해결 및 다양한 분야에서 활용되고 있습니다. 알고리즘의 동작이 매우 단순하기 때문에 상대적으로 간단히 구현할 수 있으며 매우 빠른 시간에 수행된다는 장점이 있죠. 하지만 반대로 탐욕 알고리즘이 최적해를 출력한다는 것을 보이는 것은 매우 어려운데요. 직관적으로는 매우 그럴 것 같지만 막상 그것을 증명하려고 하면 까다롭기 때문입니다. 이번 시간에는 분석하기 어려운 탐욕 알고리즘을 분석하는 일반적인 기법들을 몇 가지 소개해 보도록 하겠습니다. 구체적으로 Greedy stays ahead Certificate argument Exchange argument 를 다룰 예정입니다. 각 기법에 .. 코딩 초보에게 드리는 제언 요즘 코딩에 대한 관심이 많이 높아졌습니다. 일반인들을 대상으로 한 프로그래밍 강좌도 많이 생겼으며, 유튜브에서는 코딩 학원 광고를 심심치 않게 볼 수 있게 되었죠. 곧 있으면 초등학교나 중학교에서 코딩을 정규 과목으로 가르친다는 소식도 들었습니다. 대학교에서도 많은 것이 바뀌었습니다. 과거에는 공대생들만 코딩 수업을 들었다면, 요즘은 전교생이 필수 교양으로 코딩을 공부해야 하는 것으로 압니다. 컴퓨터과학 전공자의 전유물이던 코딩이 이제는 사람들이 보편적으로 갖추어야 하는 기본 소양이 되어가고 있습니다. 저는 이러한 일련의 변화가 매우 자연스러운 흐름이라고 생각합니다. 미래에는 지금보다 컴퓨터에 대한 의존도가 훨씬 높아질 것이고, 그 속에서 개인의 경쟁력은 컴퓨터를 자신의 분야에서 얼마큼 잘 활용할 줄 .. 이전 1 다음
