1. 자료구조와 알고리즘

1.1 자료구조와 알고리즘

프로그램 = 자료구조 + 알고리즘

알고리즘 : 컴퓨터로 문제를 풀기 위한 단계적 절차

 

알고리즘의 조건

• 입력 : 0개 이상의 입력이 존재

• 출력 : 1개 이상의 출력이 존재

• 명백성 : 각 명령어의 의미는 모호하지 않고 명확

• 유한성 : 한정된 수의 단계 후에는 반드시 종료

• 유효성 : 각 명령어들은 실행 가능한 연산

알고리즘 기술방법

자연어 -> 순서도 -> 의사코드(Pseudo code) -> 프로그래밍 언어

 

자연어

• 인간이 이해하기 쉬움

• 자연어의 단어들을 정확히 정의하지 않으면 모호해질 우려가 있음

 

순서도

• 직관적, 이해하기 쉬움

• 복잡한 알고리즘의 경우, 굉장히 복잡해짐

 

의사코드

• 알고리즘 기술에 가장 많이 사용

• 알고리즘의 핵심적인 내용에만 집중 가능

 

프로그래밍 언어

• 알고리즘을 가장 정확하게 기술

• 실제 구현에서는 구체적인 사항들이 알고리즘의 핵심에 대한 이해를 방해할 수 있음

---

1.2 추상 자료형

자료형(data type) : 데이터와 연산의 집합

자료구조 : 추상 데이터 타입을 프로그래밍 언어로 구현한 것

 

추상 데이터 타입(ADT : Abstract Data Type)

• 데이터 타입을 추상적으로 정의

• 데이터나 연산이 무엇인지 정의

• 데이터나 연산의 구현 방법은 정의하지 X

ADT의 유래

추상화(Abstraction) -> 정보은닉기법(Information hiding) -> 추상 자료형(ADT)

추상화 : 사용자에게 중요한 정보는 강조, 중요치 않은 세부사항은 제거하는 것

 

ADT 정의

객체 : ADT에 속하는 객체가 정의됨

연산

• 이름, 매개변수, 결과, 기능의 기술 등을 포함

• 객체 사이의 연산이 정의. 연산은 ADT와 외부를 연결하는 인터페이스 역할을 함

---

1.3 알고리즘의 성능분석

성능 분석 기법

수행 시간 측정

• 2개의 알고리즘의 실제 수행 시간 측정

• 실제 구현하는 것이 중요

• 동일한 하드웨어 사용

 

알고리즘 복잡도 분석

• 직접 구현하지 않고도 수행 시간 분석
• 알고리즘이 수행하는 연산 횟수를 측정하여 비교
• 보통 연산의 횟수는 n의 함수
• 시간복잡도 분석 : 실행 시간 분석
• 공간복잡도 분석 : 실행에 필요한 메모리 공간 분석

 

시간복잡도 분석

• 시간복잡도는 알고리즘을 이루는 연산들이 몇번이나 실행되는지 숫자로 표시

• 산술/대입/비교/이동 연산등 기본적 연산

• 알고리즘이 실행하는 연산의 개수를 계산하여 2개의 알고리즘 비교 가능

• 연산의 실행횟수는 입력 개수 n에 대한 함수(시간복잡도 함수) -> T(n)

빅오 표기법

• 자료의 개수가 많은 경우 차수가 가장 큰 항이 가장 영향 --> 다른 항들은 상대적으로 무시 가능
• 보통 시간복잡도 함수에서 차수가 가장 큰 항만을 고려하면 충분
• 시간복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시 --> 빅오 표기법
• 빅오 표기법은 시간복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략 --> 시간복잡도를 간단하게 표시할 수 있음
• 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것 --> 최고차항의 계수도 버림, 오직 최고차항의 차수만 사용

 

알고리즘 수행시간 비교

• O(1) : 상수형

• O(log n) : 로그형

• O(n) : 선형

• O(n log n) : 선형로그형

• O(n^2) : 2차형

• O(2^n) : 지수형

• O(n!) : 팩토리얼형 

--> O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

 

!!! : 알고리즘이 지수형, 팩토리얼형의 시간복잡도를 가지면 사실상 사용 불가

( if 입력의 개수 > 30, 지금까지의 시간보다 더 많은 수행시간 요구)