1.1 알고리즘
알고리즘
- 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차
- 어떤 입력을 어떤 출력으로 변환하는 일련의 계산과정
-
잘 정의된 계산 문제를 풀기 위한 도구
정렬 문제
입력 : n개 수들의 수열
\[<a_1,a_2, ..., a_n>\]출력 :
\[a^{'}_1≤a^{'}_2≤ ...≤a^{'}_n\]을 만족하는 입력 수열의 순열(재배치)
\[<a^{'}_1, a^{'}_2, ..., a^{'}_n>\]
ex) <31, 41, 59, 26, 41, 58>이 입력 수열로 주어지면 정렬 알고리즘은 수열 <26, 31, 41, 41, 58, 59>를 출력한다. -> 입력수열 : 정렬 문제의 사례
일반적으로 어떤 문제의 사례는 그 문제의 해를 계산하기 위해 필요한 입력으로 구성, 문제의 정의에서 요구하는 입력에 대한 제약조건을 만족해야함
훌륭한 정렬 알고리즘 중 “어떤 알고리즘이 가장 좋은가” :
- 정렬할 대상이 몇 개인가
- 이미 얼마나 정렬되어 있는가
- 정렬 대상의 값에 어떤 제약이 있는가
- 컴퓨터의 구조는 어떠한가
- 이용되는 저장 장치가 무엇인가(주기억장치, 디스크, 테이프 등)에 따라 달라짐
타당하다(correct) : 알고리즘이 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료
푼다(solve) : 그 타당한 알고리즘이 주어진 계산 문제를
타당하지 않은 알고리즘 -> 모든 또는 일부 입력 사례에서 종료하지 않거나 잘못된 답을 도출하며 종료 but 오류의 비율을 조절할 수 있으면 유용할 때가 있음
자료구조 : 자료를 편리하게 접근하고 변경하기 위해 자료를 저장하거나 조직하는 방법
