#1 알고리즘 Introduction
알고리즘에 대해 공부 및 정리를 하며 포스팅을 하려 합니다.
일반적으로 학부때 배우는 간단한 알고리즘이 아닌 Advanced한 부분에 대한 걸 다루려 하니 많은 관심 부탁드립니다.
기본적으로 Introduction to Algorithms 3rd edition을 참고하여 작성하게 될 것입니다.
정렬, Dynamic Programming, Greedy Algorithms등등 을 하고 NP-Complete까지 다뤄볼 작정입니다.
먼저 알고리즘에 대해 간단히 정의하고 알고리즘에 쓰이는 자료구조에 대해 설명하도록 하겠습니다.
컴퓨터 공학에서의 알고리즘이란?
"문제를 푸는 잘 정의된 과정"입니다.
어떤 미사여구나 수식어구도 필요없이 위 정의만으로도 컴팩트 하게 알고리즘을 정의 할 수 있습니다. 컴퓨터 공학전공이거나 컴퓨터 관련 일을 하시는분께 누군가 "알고리즘이 뭐야?" 라고 물어본다면 위 정의와 같이 간단하면서도 멋있게 대답할 수 있어야 겠습니다.
잘 정의된 과정이란?
"input을 output으로 바꾸는 과정"입니다.
역시 단순 명료합니다.
알고리즘의 퍼포먼스
우리는 컴퓨터 공학자이기 때문에 알고리즘의 효율성을 측정해야 합니다. 얼마나 빠르게 실행되느냐, 얼마나 많은 공간을 연산에 소비하느냐 두가지 척도로 측정합니다.
컴퓨터 공학에서 "문제를 푼다"라고 하는것은?
1. 문제를 정의하는 단계. input 과 output으로 정의한다.
2. 디자인 테크닉, 목적 등에 따른 전략의 수립( 시간과 공간의 제약을 고려)
3. input, output을 명세하고 step을 명세한다.
4. 성능분석(결과가 맞는지, 효율적인지, 최적인지)
알고리즘의 이론적 분석
알고리즘을 분석하는 방법에는 이론적 분석과 실험적 분석이 있습니다. 실험적분석이란 예를들어 "i7 6세대 CPU에서 알고리즘의 수행시간이 100ms이고 i3 4세대 CPU에서는 400ms가 나왔다 "라고 분석하는 것입니다. 이론적 분석은 기본적인 연산(Basic Operation)이 최악의 경우 얼마나 실행 되는가를 분석하는 것입니다. 실험적 분석은 실제적인 데이터를 얻을 수 있다는 장점이 있지만 디바이스마다, 소프트웨어마다, 연산유닛의 능력마다, 입력하는 데이터의 크기마다 다른 결과를 낸다는 단점이 있고 이론적 분석은 위 장단점과 정확히 반대의 장단점을 가지고 있습니다.
실제로 제품을 개발하거나 하는것이 아니라 알고리즘을 공부하는 학생이라면 당연히 이론적 분석을 통해 알고리즘을 분석해야겠죠?
Worst-Case Complexity
문제마다 문제를 해결하기위한 고유의 일의 양이 있습니다. 문제를 풀기 위한 시간이 1, 2, 3, 4로 나왔다면, 4의 시간을주면 어떤 문제든 풀 수 있겠죠? 그렇다면 문제를 풀기위한시간은 가장 빠른 시간인 1이 아니라 모든 문제를 풀 수 있는 4가 될것입니다. 가장 타이트한 대답이 바로 Worst-Case Complexity입니다.
Optimality
"알고리즘이 최적이다"라는것은 이론상으로는 더이상 빠르게 문제를 풀 수 없다는 뜻입니다. 알고리즘의 Optimal여부는 알고리즘의 Complexity와 문제의 Complexity(문제를 해결하기 위한 일의 양의 최소값)이 만나는 지점입니다. 문제를 해결하기위해 최소한 이정도 양의 일이 필요하다 라는것이 증명되어있으면 그것의 복잡도와 알고리즘의복잡도가 같을 때 알고리즘은 최적이 되겠죠.
Asymptotic Analyze(점근 분석)
일반적으로 알고리즘을 분석할때 O()(Big-oh)표기법을 사용합니다. input N에 대한 함수 g가 주어졌을때 증가율이 g보다 느린 함수의 집합을 O(g)라고 표기합니다. 언뜻 정의만 보면 어려울 수 있지만 간단한 예로 설명 할 수있습니다. 아래와 같은 코드가 주어졌을때 A와 B의 덧셈이라는 기본 연산을 n*n번 만큼 수행하므로 알고리즘의 복잡도는 O(n^2)입니다. n의 값이 증가할수록 증가하는 연산량이 2차함수의 증가량을 따르겠죠?
1 2 3 4 5 6 7 | for(int i = 0; i< n; i++) { for(int j = 0; j< n; j++) { C = A + B; } } | cs |
Data Structures.
자료구조란 데이터를 어떻게 저장하고 사용하는지에 대한 것입니다. 자료구조 자체가 알고리즘이 되는 경우도 있으며 대부분의 경우 알고리즘은 효율적인 자료구조를 통해 구현되는 경우가 많습니다. Stack, Queue, Tree, Dictionary, Binary Search Tree, Priority Queue등등 기본적인 자료구조는 인터넷에 자료가 많으니 잘 찾아보시면 되겠습니다.
간단한 알고리즘의 기초에 대해서 알아보았습니다. 다음은 Advanced Data Structures에 대해 알아보겠습니다.