2021. 2. 25. 12:48ㆍ카테고리 없음
* 아래의 글은 모두 관계 중심의 사고법 - 쉽게 배우는 알고리즘 (문병로 지음, 한빛아카데미)에 기록된 내용을 정리한 것이다.
이번 학기 컴퓨터공학부 문병로 교수님의 알고리즘 수업을 수강하게 되었다. 교수님의 수업이 무척 기대가 되어, 관련 서적을 찾는 과정에서 다음의 책을 발견하였고, 이를 정리해보려 한다. 사전에 교수님께서 쓰신 책을 간략하게나마 정리하기 위해 글을 남긴다.
먼저 책에서 표기해 놓은 학습 순서도를 참고하여 간단한 내용을 적고자 한다.
1. 알고리즘이란 -> 알고리즘 설계와 분석의 기초 -> 점화식과 알고리즘 복잡도 분석 -> 정렬/ 선택 알고리즘 / 검색트리
그리디 알고리즘이 가장 궁금하긴 하지만, 책에서 적힌 순서도에 따르면 위의 내용들의 학습이 선행되어야 하기 때문에 잠시 보류하겠다.
먼저 알고리즘이란 1) 문제 해결 과정을 묘사하는 것, 2) 생각하는 방법을 훈련하는 것, 3) 자료 구조의 확장으로 정의된다. 너무 설렌다
즉, 효율적인, '입력 -> 어떠한 과정 -> 출력'의 단계를 정확하게 명시하여 주는 것.
알고리즘의 설계와 분석은 체계적으로 생각하는 훈련을 하기에 더없이 좋은 도구다. 이 과정세어 체계적으로 사고를 할 수 있는 빌딩 블록을 구축하게 되어 향후 컴퓨터나 관련 분야의 연구자 또는 개발자로서 지적인 기반을 쌓을 수 있을 것이다.
다양한 문제를 위한 알고리즘을 공부하고 성공적인 설계와 분석의 경험이 누적되면 지적인 추상화의 레벨이 높아져 문제를 간명하게 볼 수 있는 눈이 생기고, 문제의 핵심과 해결 방안에 고도의 직관을 갖게 된다.
지적 추상화란 여러 계층의 개념들이 누적되어 이들과 새로운 요소를 결합해 점점 고도의 개념을 쌓아나가는 것이다.
추상화의 레벨이 높다는 것은 연구나 개발에서 정신적인 여유를 갖는데 매우 중요한 요소다.
-> for 루프의 총 반복 횟수가 수행 시간을 좌우한다. 따라서 for 루프의 총 반복횟수는 n^2에 비례한다. 알고리즘의 총 수행시간은 n^2에 비례한다. (but, 자기호출이 일어나는 경우 조금 달라진다.) 책에 표시된 예시에서는 factorial 함수가 재귀함수로 표현되었는데, 이 경우 본 함수가 총 몇 번 호출되는지가 시간을 좌우한다. 총 호출 횟수에 알고리즘 총 수행 시간이 비례함을 알 수 있다.
자기 호출은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식이다. 즉 수열의 점화식과 같이, 성격이 같지만 크기가 다른 문제 간의 관계를 파악하는 것이다.
수학적 귀납법이란 자신보다 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해서 자신에게도 결론이 옳음을 보이는 것이다. 아하 재귀 알고리즘이 자신보다 작은 문제를 자기호출하는 것은 수학적 귀납법에서 자신보다 작은 문제에 대해 결론이 옳음을 가정하는 것과 일치한다. 그 외) 크기가 다른 문제 간의 관계를 반영하는 것.
-> 드디어 예시가 나왔다, 자기호출과 관계 반영에 대한 예: 병합 정렬 (자기호출 알고리즘)
알고리즘으로 풀 수 있는 문제의 예시) 네비게이션 최단 경로 알고리즘, ATM 돈 채워 넣기 등. (순서 배열 등의 수학적 문제를 해결하는 모든 경우인 것 같다. )
점근적 표기의 세 가지 예시 -
드디어 점화식이다.
점화식과 점근적 표기법은 알고리즘의 수행 시간을 분석하는 핵심 도구다. 점근적 분석은 입력의 크기가 충분히 큰 경우에 대한 분석을 뜻한다. (입력의 크기가 작은 경우, 알고리즘의 효율성 차이가 그리 크지 않기 때문)
재귀 알고리즘은 수행 시간을 점화식으로 나타낼 수 있다. 알고리즘의 복잡도를 계산하는 방법: 반복 대치, 추정 후 증명, 마스터 정리
반복 대치 점화식: 더 작은 변수에 대한 점화식으로 대치하는 작업 반복 -> 경계조건에 이를 때까지 전개하는 방법.
추정 후 증명: 점화식의 점근적 복잡도를 추정한 후, 이를 수학적 귀납법의 원리를 이용하여 증명하는 방법.
마스터 정리: 특정 모양으로 표현되는 점화식의 복잡도를 복잡한 계산이나 증명 없이 바로 알 수 있는 방법.
점화식은 자기호출을 사용하는 함수의 복잡도를 구하는 데 유용하다.
어떠한 n이더라도, n과 2n 사이에 2의 멱수가 존재한다. (아, 진짜...로..? ㅎㅎ)
알고리즘의 복잡도 함수는 단조 증가 함수라고 가정....아하.... 여기부터 잘 이해가 가지 않기 시작한다.
이제 드디어 정렬... 사실 앞에서 스킵한 게 많다..ㅎ
정렬 -> 기본적인 정렬 알고리즘, 고급 정렬 알고리즘, 비교 정렬 시간의 하한, 특수 정렬 알고리즘.
기본 정렬 알고리즘을 이해하고, 정렬을 귀납적 관점에서 볼 수 있도록 하고, 각 정렬의 수행 시간을 분석할 수 있도록 하고, 비교 정렬의 한계를 이해, 선형 시간 정렬이 가능한 조건과 선형 시간 정렬 알고리즘을 이해한다.
정렬은 n개의 우너소를 순서대로 배열하는 것이다.
삽입 정렬은 시간이 드는 비효율적인 정렬 알고리즘군에 속하지만 배열이 거의 정렬되어 있는 상태로 입력되는 경우 가장 매력적인 알고리즘이 된다.
병합 정렬 알고리즘은 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 계속 반으로 쪼개서.. 병합 정렬은 자신에 비해 크기가 반인 문제 두 개를 푼 다음, 이들을 병합하는 일을 재귀적으로 반복한다.
퀵 정렬, 힙 정렬을 봐야 하는데 머리가 아프다..!
그 다음, 선택 알고리즘...