알고리즘과 자료구조의 정의

알고리즘

• 어떤 값이나 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차
• 잘 정의된 계산 문제를 풀기 위한 도구
• 계산 문제를 정의하려면 입력과 출력의 관계를 잘 서술해야 한다.
• 어떤문제의 사례는 그 문제의 해를 계산하기 위해 필요한 입력으로 구성되며 문제의 정의에서 요구하는 입력에 대한 제약조건을 만족해야 한다.
• 알고리즘이 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 이를 타당(correct)하다고 한다.
• 타당한 알고리즘이 계산 문제를 푼다(solve)고 말한다.
• 타당하지 않은 알고리즘도 오류의 비율을 조절할 수 있으면 유용할 때가 있다.
• 알고리즘에 대한 지식과 기술을 얼마나 알차게 학습했느냐가 숙련된 프로그래머와 초보자를 구분하는 기준이 될 수 있다.

알고리즘 문제의 두 가지 특징:

1. 후보해는 많지만 대부분이 문제의 해가 아니다.
   • 최상의 해 를 찾는 것은 도전적인 일이다.
2. 실용적인 응용 예가 있다.

자료구조

• 자료를 편리하게 접근하고 변경하기 위해 자료를 저장하거나 조작하는 방법
• 모든 목적에 가장 맞는 단일 자료 구조는 없다.

+ 좋은 정렬 알고리즘

• 정렬 대상이 몇 개인지, 어느 정도까지 정렬됐는지, 정렬 대상의 값에 어떤 제약이 있는지, 컴퓨터 구조는 어떠한지, 이용되는 저장 장치가 무엇인지에 따라 달라진다.

---

출처

Introduction to algorithm, 3rd edition