Part4 - chapter02 : 알고리즘과 코딩(수정전)

01. 알고리즘

 

[알고리즘]

• 알고리즘의 정의
  • 알고리즘 : 주어진 문제를 해결하기 위해 잘 정의된 동작의 유한 집합
  • 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화 한 형태로 표현한 것
• 알고리즘이 갖추어야 할 조건
  • 입력 : 외부에서 입력되는 자료가 0개 이상 존재
  • 출력 : 출력이 적어도 1개 이상의 결과가 있어야 함
  • 명확성 : 명령어들은 명확하고 모호하지 않아야 함
  • 유한성 : 명령어들은 유한 번의 수행 후 종료되어야 함
  • 유효성 : 모든 명령들은 명백하고 실행 가능한 연산들이여야 함
• 알고리즘을 분석하는 판단 기준
  • 정확성 : 알고리즘이 정확한지, 입력에 대해 정확한 출력이 되는지 나타내는 기준
  • 간결성 : 표현이 간단하고 읽기 쉽고 이해가 용이한지의 기준
  • 작업량 : 명령어의 실행 횟수로 평균과 최악의 경우를 나타내는 기준
  • 최적성 : 알고리즘 수행 시간의 평균과 최악이 같을 때 최적이라 하며 두가지 경우의 시간 차이를 계산하여 분석
• 순서도 : 누구나 알아볼 수 있는 형식으로 표현해야함
• 코딩 : 알고리즘을 선정한 프로그래밍 언어로 변환하여 작성하는 것
• 알고리즘 설계법
  • 동적 계획법 : 해결하고자 하는 문제의 최적해를 부분 문제들의 최적해로 구성된 경우 이를 통해 최적해를 구하는 기법
  • 탐욕 알고리즘 : 최적해를 구하는 알고리즘으로 가장 좋아 보이는 해법을 선택하는 알고리즘으로 결국 최적해법을 구할 수는 없을지라도 근사적 해답을 얻을 수 있음
  • 재귀적 알고리즘 : 같은 알고리즘을 반복하여 수행하는 알고리즘
  • 근사 알고리즘 : 
  • 배낭 알고리즘 : 
  • 분할 정복법 : 
  • 퇴각 검색법 :