2주 1차 추상 자료형과 알고리즘
1. 추상 자료형
① 뇌의 추상화 기능
- 자세하고 복잡한 것 대신 필수적이고 중요한 특징만 골라서 단순화 시키는 작업 : 추상화
② 컴퓨터를 이용한 문제해결에서의 추상화
- 크고 복잡한 문제를 단순화시켜 쉽게 해결하기 위한 방법
- 자료 추상화 : 처리할 자료, 연산, 자료형에 대한 추상화 표현
③ 추상 자료형이란?
- 자료형에 대한 자료의 특성, 연산자, 연산자가 무엇을 수행하는 지 등
자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료
2. 알고리즘 개념
① 알고리즘이란?
- 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서
- 알고리즘 조건 : 입력, 출력, 명확성, 유한성(반드시 종료되어야), 효과성
② 알고리즘의 표현 방법의 종류
- 자연어(사람이 쓰는 언어)를 이용한 서술적 표현 방법 : 일관성, 명확성 유지 어려움/ 잘 사용하지 않음
- 순서도(Flow Chart) 이용 도식화 표현 방법 : 흐름 쉽게 파악, 복잡한 알고리즘 표현에 한계
- 프로그래밍 언어를 이용한 구체화 방법 : 알고리즘 자체가 구체화 됨,
특정 프로그래밍 언어로 작성 -> 언어모르면 이해 어려움
다른 프로그램밍 언어로 개발시 변환해야함-> 비효율적
- 가상코드(Pseudo-code)를 이용한 추상화 방법 : 프로그래밍 언어의 형태 갖춘 가상코드 사용
직접 실행 불가, 원하는 프로그래밍 언어로 구체화 쉬움
③ 가상코드 형식의 기본 요소
- 기호(변수, 자료형 이름, 프로그램 이름, 레코드 필드 명, 문장의 레이블), 자료형, 연산자, 조건문, 반복문, 함수문
- 함수문 : 처리작업 별로 모듈화하여 만든 부프로그램
3. 알고리즘 성능분석 방법
① 알고리즘 성능 분석 기준
- 정확성, 명확성, 수행량, 메모리 사용량, 최적성
- 정확성 : 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부
- 명확성 : 알고리즘이 이해하기 쉽게 작성되었는 지 여부
- 수행량 : 알고리즘 특성 나타내는 중요 연산을 모두 분석해서 수행량의 대소여부 판별
- 메모리 사용량 : 명령어, 변수 등 저장하기 위해 메모리 사용하는데, 대소 여부
- 최적성 : 조건에 맞는 최적의 알고리즘 여부
② 알고리즘 성능 분석 방법 : 공간 복잡도, 시간 복잡도
- 공간복잡도 : 알고리즘을 프로그램으로 실행하고 완료하기까지 필요한 저장 공간의 양
= 고정공간 + 가변공간(실행과정에서 사용되는 자료, 변수 저장공간/ 함수 실행 시 정보저장 공간)
- 시간 복잡도 : 알고리즘을 프로그램으로 실행하고 완료하기까지 총 소요시간
= 컴파일 시간 + 실행시간(실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산)
- 실행 빈도수 계산 : 하나의 단위시간을 갖는 기본 명령문의 횟수 계산
- 빅-오 표기법 : 함수의 상한을 나타내기 위한 표기법(최악의 경우 고려) -주로 사용
실행 빈도수 구하여 f(n) 찾고, 가장 큰 영향 주는 n에 대하여 나타냄.
- 빅-오메가 표기법 : 함수의 하한을 나타내기 위한 표기법(적어도 ~의 수행시간 필요)
- 빅-세타 표기법 : 상한과 하한을 같이 표기
③ 프로그램 성능 구별방법
- 처리시간과 메모리 사용량 이용하여 비교 가능
- 메모리 가격 낮아져 공간적 여유가 있기에 시간복잡도가 성능에 영향 많이 줌.
- 시간 복잡도란? 알고리즘 수행하는데 얼마나 많은 절차 거쳐야하는 지 나타냄.
연산의 회수(처리해야할 요소의 개수)가 증가할수록 커짐.
빅-오 표기법으로 요소의 개수와 복잡도 관계를 표현할 수 있다.