[컴퓨터과학개론] 알고리즘

알고리즘 개념

컴퓨터 과학

• 컴퓨터를 활용해서 주어진 문제를 해결하기 위한 학문
  
  

알고리즘

• 주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것
  
  1. 입출력 : 0개 이상의 외부 입력, 1개 이상의 출력
     
  2. 명확성 : 각 명령은 모호하지 않고 단순 명확해야 함
     
  3. 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료해야 함
     
  4. 유효성 : 모든 명령은 컴퓨터에서 실행 가능해야 함
     
     
• 문제 해결을 위한 레시피
  
  • 단계적인 조리 절차를 따르면 음식을 만들 수 있듯이, 주어진 문제도 단계적인 풀이 절차(=알고리즘)를 따르면 문제의 해를 구할 수 있음
    
    

자료구조와 알고리즘의 관계

• 자료구조
  
  • 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법
    
  • 배열, 연결 리스트, 스택, 큐, 트리, 그래프
    
    
• 효율적인 프로그램이랑 효율적인 자료구조 + 효율적인 알고리즘이 조화되어 이루어진 것
  
  

알고리즘 설계 기법

• 문제와 그에 따른 조건 등이 매우 다양
  
  • 일반적이고 범용의 설계 기법은 없음
    
    
• 대표적인 설계 기법
  
  • 분할 정복 방법
    
  • 동적 프로그래밍 방법
    
  • 욕심쟁이 방법
    
    

분할 정복 방법

• 순환적으로 문제를 푸는 방법
  
  • 문제의 입력을 더 이상 나눌 수 없을 때 까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 분할된 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법
    
    
• 특징
  
  • 분할된 작은 문제는 원래 문제와 동일
    
  • 단순히 입력 크기만 작아진 것
    
  • 분할된 작은 문제는 서로 독립적
    
    
• 각 순환 호출마다 세 단계의 처리 과정을 거침
  
  1. 분할 : 주어진 문제를 여러개의 작은 문제로 분할한다.
     
  2. 정복 : 작은 문제를 순환적으로 분할. 만약 작은 문제가 더 이상 분할되지 않을 정도로 크기가 충분히 작다면 순환호출 없이 작은 문제의 해를 구한다
     
  3. 결합 : 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다. (결합 단계계가 없는 문제도 존재)
     
     
• 퀵 정렬, 합병 정렬, 이진 탐색
  
  

동적 프로그래밍 방법

• 최적화 문제의 해를 구하기 위한 상향식 접근 방법
  
  • 문제의 크기가 작은 소문제에 대한 해를 구해서 테이블에 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만듦
    
    
• 모든 정점 간의 최단 경로를 구하는 플로이드
  
  

욕심쟁이 방법

• 해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 각 단계에서 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 얻을 수 있을 것이라고 희망하는 방법
  
  

• 희망 : 각 단계의 최적해를 통해 전체적인 최적해를 만들어내지 못할 수 있음
  
• 적용 범위는 제한적, 간단하면서도 강력한 설계 기법
  
• 거스름돈 문제, 배낭 문제