자료추상화와 알고리즘
- 자료 추상 데이터 타입과 알고리즘
자료의 추상화 : 어렵고 복잡한 문제를 단순화시켜 쉽게 문제해결을 하는 절차
데이터타입 : 데이터의 집합과 연산의 집합
추상화 : "무엇인가?"를 논리적으로 정의
구체화 : "어떻게 할 것인가?"를 실제적으로 정의
추상데이터 타입의 정의
객체 : 추상 데이터 타입에 속하는 객체를 집합의 개념을 사용하여 정의
연산 : 추상 데이터 타입과 외부를 연결하는 인터페이스 역할을 한다
알고리즘 : 문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서
알고리즘의 조건
1. 입력 : 알고리즘 수행에 필요한 자료가 외부로부터 입력되어야 한다.
2. 출력 : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다.
3. 명확성 : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 표현되어야 한다.
4. 유한성 : 알고리즘은 수행 뒤에 반드시 종료되어야 한다.
5. 효과성 : 알고리즘의 모든 명령어는 실행이 가능해야 한다.
알고리즘 표현 방법
1. 자연어
인간이 읽기 쉽지만 자연어 단어의 정확한 정의가 없으면 의미 전달이 모호해진다.
2. 순서도
직관적이고 이해가 쉽지만 복잡해질수록 이해가 어려워진다.
3. 가상코드
가상코드 즉 알고리즘 기술언어로 프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘을 기술한다.
4. C
가장 정확한 알고리즘 기술이 가능하다.
5. 조건문
조건에 따라 실행한 명령문이 결정되는 선택적 제어구조를 만든다.
6. Case문
조건식들 중에서 해당하는 조건을 찾아서 명령문을 수행한다.
7. 반복문
일정한 명령을 반복 수행하는 루프 형태의 제어구조이다.
알고리즘 성능분석 기준과 기법
- 알고리즘 성능분석 기준
정확성, 명확성, 수행량, 메모리사용량, 최적성 등이 있다.
알고리즘 성능분석의 필요성
최근 프로그램 규모가 대규마화되어 데이터 처리량이 많아지고 있다.
알고리즘간 효율성 차이는 입력량이 커질수록 그 차이가 커진다.
수행시간 측정방법
두 개의 알고리즘의 실제 수행 시간을 측정하는 것이다.
알고리즘을 구현하여 실행시간을 측정하는 방법은 정확하고 확실한 방법이다.
알고리즘의 복잡도 분석
직접 구현하지 않고서도 수행시간을 분석하는 것으로 알고리즘이 수행하는 연산의 횟수를 측정한다.
1. 시간복잡도 분석 : 수행시간 분석
2. 공간복잡도 분석 : 수행 시 필요로 하는 메모리 공간 분석
빅O 표기법
자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 그 영향이 미미하다.
연산의 횟수를 대략적으로 표기한 것으로 알고리즘분석을 쉽게 할 목적으로 시간 복잡도를 표시한다.
주의점으로 상수항이나 계수가 굉장히 큰 경우는 실행시간에 영향을 미친다.
자료구조의 표기법
- 알고리즘 실행시간의 자료집합 평가기준
최선의 경우 : 수행시간이 빠른 경우로 알고리즘이 의미가 없다
평균의 경우 : 방대한 데이터 수집 등 계산하기가 상당히 어렵다
최악의 경우 : 수행시간이 가장 늦은 경우가 가장 널리 사용된다 계산하기 쉽고 응용에 따라 중요한 의미를 가질 수 있다
순차탐색
정렬되지 않은 배열을 순차적으로 탐색하여 특정한 값을 찾는 알고리즘에서 시간복잡도 함수를 계산한다.
최선의 경우 : 찾고자 하는 숫자가 맨 앞에 있다 -> O(1)
최악의 경우 : 찾고자 하는 숫자가 맨 뒤에 있다 -> O(n)
평균의 경우 : 모든 경우가 균일하게 탐색된다 -> (1+2+....+n)/2 -> O(n)
- 자료구조 표기법
프로그램 작성시 변수, 상수, 함수의 이름을 짓는것에 신중해야 한다.
1. 상수
상수는 전체를 대문자로 표기한다
2. 변수
소문자로 표기한다. 언더라인으로 단어와 단어를 분리하고 약어는 가급적 제한한다.
3. 함수
동사를 이용하여 함수가 하는 작업을 표기한다.
typedef
C언어에서 typedef는 사용자 정의 데이터 타입을 만드는데 유용하게 사용된다.
사용자 정의 데이터 타입은 데이터 타입을 사용자가 직접 만든다
형식 : typedef <타입의 정의><타입의 이름>
간결하고 정리된 코드를 작성할 수 있는 장점이 있다.