자료구조와 알고리즘
프로그램 = 자료구조 + 알고리즘
'자료구조'란 프로그램에 필요한 자료들을 보관하는 방법
주어진 문제를 해결하는 방법은 '알고리즘'
예를 들어 학생 10명의 수학 성적 중 가장 높은 점수를 찾는 문제가 있다면
학생 10명의 성적을 배열에 저장하고 배열의 첫번째 요소를 변수 largest에 복사한 뒤
순차적으로 largest와 배열의 마지막 요소까지 비교하여 최고 성적을 구한다고 했을 때
여기서 배열은 자료구조가 되고 배열의 값을 순차적으로 비교하는 방법이 알고리즘이 되는 것이다.
int largest = score[0];
for(int i=1; i<N; i++){
if(largest<score[i])
largest=score[i];
}
알고리즘
알고리즘은 문제 해결을 위해 컴퓨터가 이해가능하도록 작성한 명령어들의 집합이다.
그러나 모든 명령어 집합이 알고리즘이 되는 것은 아니고 다음과 같은 조건을 만족해야 한다.
- 입력이 0개 이상
- 출력이 1개 이상
- 명백성 : 명령어의 의미가 모호하지 않고 명확해야 함.
- 유효성 : 실행 가능한 연산이어야 함.
- 유한성 : 단계가 끝나면 프로그램이 반드시 종료되어야 함.
알고리즘을 기술하기 위한 방법에는 자연어, 흐름도, 의사코드, 프로그래밍 언어가 있다.
이 중 자연어보단 명확하고 프로그래밍 언어보단 덜 엄격한 의사코드와
명백한 의미를 가진 프로그래밍 언어가 가장 많이 사용된다.
추상자료형 ADT (Abstract Data Type)
자료형 작성 시에는 데이터 뿐만 아니라 실행 가능한 연산에 대해서도 생각해야 한다.
예를 들어 나머지를 구하는 연산자는 정수 데이터에선 의미가 있지만 실수 데이터에선 무의미하다.
복잡한 자료형 구현 시 연산은 함수로 구현된다.
스택같은 경우 값을 추가하는 연산은 add() 함수로 정의된다.
추상자료형 ADT는 추상적으로 자료형을 구현한 것으로, 실제적 구현과는 분리되어 있다.
데이터, 연산은 정의되지만 연산을 어떻게 구현할 것인지는 정의되지 않는다.
연산 정의 시 연산 이름, 매개변수, 반환형은 정의되지만, 연산을 구현하는 코드는 주어지지 않는다.
다만 연산을 구현하는 추상적인 의사코드는 주어질 수 있다.
ADT 구현 시 보통 외부에는 인터페이스만 알린다.
사용자는 인터페이스만 사용하므로 변경가능성이 있는 구현세부사항은 알리지 않아도 되는 것이다.
이는 인터페이스만 지켜진다면 구현세부사항은 얼마든지 변경될 수 있다는 의미로도 해석가능하다.
이것은 정보은닉의 기본 개념으로 객체지향 언어에서는 클래스의 개념으로 구현된다.
ADT의 객체는 클래스의 속성으로, ADT의 연산은 클래스의 멤버함수로 구현된다.
알고리즘 복잡도
알고리즘 분석에서 '좋다'는 의미는 두가지 측면으로 나뉠 수 있다.
알고리즘 수행 시간과 알고리즘이 필요로 하는 기억공간의 양으로 나뉘는데
수행 시간 측면에서 알고리즘 분석을 '시간 복잡도'라고 하고
기억공간 측면에서의 분석을 '공간 복잡도'라고 한다.
시간 복잡도 함수
알고리즘 복잡도는 대개 시간 복잡도를 의미한다.
기억공간의 양보다는 수행 시간을 더 중요시 여기기 때문이다.
시간 복잡도는 알고리즘 수행 시간이 아닌 연산이 수행되는 횟수를 나타낸다.
연산 횟수는 상수가 아닌 입력 갯수 n에 따라 달라지기 때문에 n에 대한 함수로 나타내며 T(n)으로 표기한다.