문제 해결 과정

1. 문제의 이해

• 입력의 범위를 정확히 해야 함.
• 올바른 알고리즘은 대부분의 입력이 아니라 모든 유효한 입력에 대해 정확한 해답을 구할 수 있어야 함.

2. 개발 방향 결정과 알고리즘의 설계

1. 계산 장치의 특성

• 순서적 알고리즘 (일반적으로 많이 사용 됨.)
• 병렬적 알고리즘

2. 최적해와 근사해

• 정확한 값을 구하는 최적해
• 근사(Approximation)값을 구하는 근사해

3. 알고리즘 설계 기법

• 억지(Brute-force) 기법과 완전 탐색(Exhaustive Search)
• 문제의 정의를 가장 직접 사용하는 방법
• 원하는 답을 구할 때까지 모든 가능한 경우를 테스트한다.
 
• 축소 정복(Decrease and Conqier)
• 주어진 문제를 하나의 좀 더 작은 문제로 축소하여 해결하는 방법
 
• 분할 정복(Divide and Conquer)
• 주어진 문제를 여러개의 더 작은 문제로 반복적으로 분할하여 해결 가능한 충분히 작은 문제로 만든 다음 해결하고 결과를 다시 병합하는 방법
 
• 공간을 이용해 시간을 버는 전략
• 추가적인 공간을 사용하여 처리시간을 줄이는 전략
 
• 동적 계획법(Divide and Conquer)
• 원래의 문제를 더 작은 문제로 나누는 면에서 분할 정복과 유사하지만, 작은 문제를 먼저 해결하고 결과를 '저장'하여 다음에 더 큰 문제를 해결 할 때 사용한다는 것이 분할 정복과 가장 큰 차이이다.
 
• 탐욕적(Greedy) 기법
• 모든 경우를 고려해 보고 가장 좋은 답을 찾는 것이 아니라 결정을 해야 할 때마다 그 순간에 최적이라고 생각되는 답을 선택하는 방법.
 
• 백트래킹과 분기 한정 기법
• 상태공간트리에서 해를 단계적으로 찾아가는 과정에서 현재의 해가 최종 해가 될 수 없다고 판단되면 더 이상 탐색하지 않고 되돌아가서(Backtracking) 다른 후보해를 탐색하는 방법
• 더 많은 가지치기(Pruning)을 통한 탐색 효율을 높이기 위해 분기 한정 기법을 추가로 사용할 수 있다.

3. 알고리즘의 정확성

• 알고리즘이 주어진 문제의 모든 유효한 입력에 대해 유한한 시간 안에 정확한 해를 구한다는 것을 보이는 것
• 실험적 분석(Experimental Analysis, Testing)
• 다양한 입력을 이용해 알고리즘을 테스트하여 타당성을 보이는 방법.
• 간단하지만 모든 가능한 입력 사례들을 포함하기 어렵고, 충분한 테스트가 어느 정도인지를 알 수 없다는 문제가 있음.
• 알고리즘이 틀렸다는 것을 보여주기 위해서는 한 가지 입력 사례만으로 충분함.
 
• 증명적인 분석(Formal Analysis, Proving)
• 수학적인 방법으로 알고리즘의 타당성을 증명하는 방법
• 수학적 귀납법(Mathematical Induction) 등이 자주 사용되는데, 경우에 따라 증명이 매우 어려울 수도 있음.

4. 알고리즘 분석

• 시간 효율성
• 가장 중요하게 생각되는 요소
• 빨리 결과를 낼 수록 시간효율성이 높음.
• 실제 실행 시간을 측정하는 방법과 이론적으로 복잡도를 분석하는 방법이 있음.
 
• 공간 효율성
• 컴퓨터 메모리를 얼마나 사용하는지는 나타냄.
• 더 적은 메모리를 사용할 수록 공간효율성이 높음.
• 시간효율성보다 상대적으로 덜 중요하게 여겨지는 편이라 시간효율성을 높이기 위해 공간효율성을 희생하는 전략도 있음.
 
• 코드 효율성
• 알고리즘을 기술한 코드가 얼마나 이해하기 쉬운가를 나타냄.
 
 

5. 알고리즘 구현

• 특정 프로그래밍 언어로 구현하는 과정.
• 실행 효율을 높이기 위해선 C와 같은 컴파일(Compile)언어로 구현.
• 빠른 구현과 알고리즘의 동작 확인 등을 위해서는 Phthon과 같은 인터프리터(Interperter)언어로 구현.