알고리즘 설계기법

 

 

 

알고리즘이란?

알고리즘이란 문제를 해결하기 위해 수행해야 할 기능의 집합을 의미한다. 알고리즘과 데이터 구조를 결합해야 프로그램이 완성되는 것이다. 순서도(Flow Chart), 의사코드(Pseudo Code)를 통해 알고리즘을 설계하고 프로그래밍이 진행된다.

 

알고리즘은 입력값이 존재하지 않을 수 있다는게 특징이다. 하지만 출력은 반드시 1개 이상 존재해야 한다. 모든 기능은 명확한 의미와 완벽한 구성을 갖추고 있어야 한다. 모든 기능은 지정한 횟수만큼 반복된 뒤에 종료되어야 한다. 모든 기능은 실제로 연산이 가능한 로직이어야 한다.

 

알고리즘이 제대로 구성되었는지 확인하는 방법은 특정 입력에 대해서 기대 출력값이 동일한지 판단한다. 알고리즘의 표현이 간단하고 이해가 용이한지 판단한다. 입력 데이터에 비례해서 몇번의 명령을 실행해서 결과를 출력하는지 분석한다. 평균적인 명령 수행시간과 최악의 명령 수행시간의 차이를 분석한다. 백준 알고리즘의 경우 시간과 메모리 제한 까지 두고 있어서 난이도가 높다.

 

알고리즘을 표현하는 방법은 순서도와 의사코드로 작성이 가능하다. 순서도(Flow Chart)는 약속된 도형과 기호를 사용해서 알고리즘을 표현하는 방식이다. 표현방법이 쉽고, 공통된 형식으로 표현하기 때문에 서로 다른 프로그래밍 언어로 변환이 가능하다.

 

의사고드(Pseudo Code)는 일반적인 자연어 형식으로 코드를 흉내내어 알고리즘을 표현하는 방식이다. 특정 프로그래밍 언어의 문법에 따른 것이 아니기 떄문에 컴퓨터에서 실행이 불가능하다. 특정 언어로 프로그램이 하기 전, 알고리즘의 모델을 대략적으로 모델링하는 경우에 사용한다. 

 

// Pseudo Code

void insert(Vertex V, int X) {
    if (x < V에 저장되어 있는 수) {
        if (V가 왼쪽 자식이 있으면) {
            insert(V의 왼쪽 자식, X);
        } else {
            V의 왼쪽 자식을 새로 만들고, 그 곳에 X를 저장함
        }
    } else {
        if (V가 오른쪽 자식이 있으면) {
            insert(V의 오른쪽 자식, X);
        } else {
            V의 오른쪽 자식을 새로 만들고, 그 곳에 X를 저장함
        }
    }
}

 

 

알고리즘 설계기법

알고리즘의 틀은 크게 6가지 정도로 구분이 가능하다. 

1. 동적계획법(Dynamic Programming) : 어떤 문제를 해결하기 위해서 그 문제를 더 작은 문제의 연장선으로 생각하는 상향식 방버이다. 작은 문제의 풀이방법이 큰 문제의 풀이 방법으로 적용된다. 하위 문제가 기하급수적으로 증가하는 경우 유용하게 사용된다. 동적계획법의 대표적인 문제로는 최단경로문제, 행렬의 제곱문제가 있다. 동적계획법의 단점은 모든 상황을 가정해서 알고리즘을 설계해야 한다는 것이다.
2. 탐욕적 알고리즘(Greedy Alogorithm) : 동적계획법의 단점을 극복하기 위해 고안된 방법이다. 분기 마다 가장 최적의 풀이방법을 선택해서 전체 결과를 도출해내는 방식이다. 결과값이 반드시 최적해를 보장하지 않는다. 탐욕적 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들이다. 탐욕 알고리즘의 대표적인 문제들은 선택조건, 최적부분구분조건을 충족하는 경우다.
3. 재귀적 알고리즘(Recursive Algorithm) :  풀이 도중 가은 풀이를 다시 불러오는 과정을 반복하는 방식이다. 호출의 역순으로 결과값이 출력된다. 
4. 근사 알고리즘(Approximation Algorithm) : 최적화되는 답을 구할수는 없지만, 비교적 빠른 시간에 계산이 가능하도록 근사 해법을 수행하는 알고리즘이다. 대표적인 문제로 NP-완전 문제가 있다. 
5. 분할 정복법(Divide and Conquer) : 크고 방대한 문제를 효율적으로 풀 수 있는 단위로 작게 나누는 하향식(Top-Down) 알고리즘이다. 계산된 결과를 다시 합쳐서 큰 문제의 결과를 구해낸다.
6. 퇴각 검색법(BackTracking) : 분기 구조 탐색에서 탐색이 실패할 경우, 탐색이 성공했던 이전 분기로 되돌아 가는 구조를 말한다. 새로운 탐색이 가능한 분기까지 과정을 되돌려 진행되는 알고리즘이다. 대표적으로 깊이 우선 탐색 알고리즘(DFS)가 있다.