알고리즘

목차

제1장 서론
제2장 정렬
제3장 탐색
제4장 스트링 매칭
제5장 기하 알고리즘
제6장 그래프 알고리즘
제7장 엔피-완전 문제

본문내용

제1장 서론

1.1. 기본 개념

∙알고리즘: 문제를 해결하거나 함수를 계산하기 위해 좇아야할 모호함이 없는 간단한 명령들로 구성된 일련의 순서적 단계. 튜링 기계에 의해 수행 가능한 프로시저.
∙알고리즘의 요건
조건 1. 외부에서 0개 이상의 입력을 받아들여, 하나 이상의 출력을 생성한다.
조건 2. 각 단계가 단순하고 모호하지 않아야 한다.
조건 3. 한정된 수의 작업 후에는 반드시 끝나야 한다.
조건 4. 모든 명령이 수행 가능해야 한다.
조건 5. 효율적이어야 한다.
∙알고리즘의 생성단계: 알고리즘의 설계, 알고리즘의 표현, 알고리즘의 정확성 검증, 알고리즘의 효율 분석

1.2. 알고리즘 기술 언어

∙C 언어에 기반을 둔 의사 언어

1.3. 기본 자료구조

∙배열, 연결 리스트
∙큐
- 뒤(rear), 앞(front)
- 원형 큐
- 선입선출(FIFO: First In First Out)
∙스택
- 후입선출(LIFO: Last In First Out)
∙나무(tree)
- 뿌리(root)
- 부분나무(subtree)
- 동기(同氣: sibling): 동일 레벨의 노드
- 조상(ancestor)
- 차수(degree)
- 이진나무
∙그래프
- 정점(vertex), 간선(edge)
- 무방향 그래프(undirected graph), 방향 그래프(directed graph)

1.4. 알고리즘의 설계와 분석

∙알고리즘 설계 방법은 다양하며 일정한 틀을 제시하기가 어려운 경우가 적지 않다.
∙대표적인 설계 기법: 욕심쟁이 방법(greedy method), 분할 정복(divide and conquer), dynamic programming 방법, branch and bound 방법 등.
∙알고리즘의 분석 - 시간 복잡도(time complexity)와 공간 복잡도(space complexity)
∙시간 복잡도 - 알고리즘의 수행시간. 입력 크기의 함수.

참고자료

· 없음