.. _intro_to_algorithm: ****************************************** Introduction to algorithms ****************************************** 본 문서는 **Introduction to algorithms을** 읽고 본인이 생각하는 핵심내용 및 의견을 정리한 글입니다. 알고리즘이란 어떤 문제를 해결하는 계산과정을 뜻한다. **좀더 일반적인 정의로는 입력값이 주어졌을때 다른 값을 출력하는 잘 정의된 계산절차를 뜻한다.** 알고리즘은 타당한 알고리즘과 타당하지 않은 알고리즘으로 나뉠 수 있으며 상황에 맞게 활용되어야한다. 학부때 배우는 간단한 문제들 뿐만 아니라 커다란 문제를 해결하기 위해 여러가지 알고리즘이 개발되었고 발전하게 되었다. 몇몇 대표적인 문제를 해결하는 알고리즘을 다룸으로써 실생활의 문제를 해결할 수 있게 된다. 알려진 알고리즘으로 해결할 수 없는 문제를 만났을때는 직접 설계할 수 있는 능력이 필요하다. 따라서 설계 및 알고리즘을 분석하는 능력을 알아야 한다. 또한 자료구조를 배울 수 있다. 모든 알고리즘에 어울리는 단일 자료구조는 존재하지 않으므로 장점 및 한계를 배우는 것이 중요하다. **NP-완비가 흥미로운 이유는** 다음과 같다. 1) 최적해를 찾는 효율적인 알고리즘이 발견되지 않았지만 최적해가 존재하지 않는다는 것을 증명한 사람은 없다. 2) NP-완비 문제중 한 문제에 효율적 알고리즘이 존재하면 다른 모든 문제에 효율적 알고리즘이 존재한다는 사실이다. 3) NP-완비 문제 중 일부가 효율적 알고리즘이 존재하는 다른 문제와 일치하지 않지만 상당히 유사하다. 이는 문제를 조금만 바꿔도 효율적인 알고리즘을 찾을 수 있다는 것이다. NP-완비로 판단된다면 근사 알고리즘을 설계하는 편이 낫다. **주로 사용하는 용어들은** 다음과 같다. - 사례 : 알고리즘의 하나의 입력값. 단 입력의 제약조건을 만족해야함. - 타당한 알고리즘(correct algorithm) : 모든 사례에 대해 올바른 출력값을 만드는 알고리즘 - 타당하지 알고리즘 : 모든 사례에 올바른 출력값을 만들지 못하는 알고리즘 - 루프 불변성 : 알고리즘의 특성중 하나로 루프가 반복되도 참인 명제가 존재하는 성질 - 의사코드 : 알고리즘을 이해하기 쉽게 표현한 코드 - RAM(Random Access Model) : 순차적인 명령어를 처리할 수 있는 프로세서를 갖고 있으며 상수시간에 계산되는 단순한 연산만 제공하는 컴퓨터 - 최선의 경우 : 주어진 입력에 따라 빠른 시간에 끝내는 경우 - 최악의 경우 : 주어진 입력에 따라 가장 늦은 시간에 끝내는 경우, 모든 입력에 대한 상한선을 갖는다. - 평균의 경우 : 주어진 입력에 따라 평균시간에 끝내는 경우, 랜덤화된 알고리즘에서 구하기도 한다. 모든 입력이 같은 확률로 나타난다고 가정하는 경우이다. 프로그램이 실행되는 환경은 RAM환경으로 제한한다. RAM환경 만으로도 알고리즘을 분석하기 용이하다. 알고리즘의 성능은 수행시간 및 입력크기로 표현된다. 일반적으로 time = f(input)이다. **알고리즘을 분석하기 위해서는 알고리즘에 맞게 입력크기를 잘 정의해야한다.** 입력크기는 곱셈 문제의 경우 비트수가 될 수도 있고 삽입정렬의 경우 입력 배열의 크기 또는 입력의 정렬 상태가 될 수 있다. 수행시간은 상수시간 명령어가 몇번 실행되었는지로 표현된다. ====================== 삽입 정렬 ====================== 삽입정렬은 입력 배열에서 임의의 원소를 뽑아 출력 배열의 적절한 위치에 삽입하는 알고리즘이다. 바닥에 엎질러진 카드를 일자로 놓는 경우와 같다. ---------------- 루프 불변성 ---------------- 삽입정렬에서 **a[i]을 삽입할때 a[0...i-1]는 정렬되기 전 a[0...i-1] 원소로 구성되어 있으며 정렬되어 있는 것** 은 매순간의 반복에서 변하지 않는 성질이며 참인 명제이다. ---------------- 수행 시간 ---------------- 입력 크기 n에 대해서 입력 배열이 정렬되어 있을 때(최선의 경우)는 an + b의 시간이 걸리며 역으로 정렬되어 있을때(최악의 경우)에는 an^2 + bn + c 의 수행시간이 걸린다.