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