01. 자료구조와 알고리즘

<C언어로 쉽게 풀어쓴 자료구조> 책을 읽고 공부한 내용을 정리하기 위한 글입니다. 

---

1.1 자료구조와 알고리즘

자료구조란?

프로그램에서 자료들을 정리하여 보관하는 구조를 자료구조(data structure)라고 부른다.

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

자료구조(data structure): 자료를 저장하는 구조

알고리즘(algorithm): 주어진 문제를 처리하는 절차

 

ex)시험성적을 읽어 들여서 최고성적을 구하는 프로그램에서
자료구조: 배열로 선택
알고리즘: 변수를 하나 만들고 배열의 첫 번째 요소값을 저장-> 변수와 배열의 요소들을 순차적으로 비교-> 만약 배열요소가 더 크다면 배열요소의 값을 변수에 저장

 

자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다.

 

알고리즘이란?

 알고리즘(algorithm)

1. 컴퓨터로 문제를 풀기위한 단계적인 절차

2. 특정한 일을 수행하는 명령어들의 집합 (알고리즘이 되기위한 조건들을 만족하는 집합만이 가능)

 

*알고리즘이 되기위한 조건

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

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

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

유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함

유효성: 각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 함

 

*알고리즘 기술 방법

1. 한글이나 영어 같은 자연어

2. 흐름도(flowchart)

3. 의사코드(pseudo-code)

4. 프로그래밍 언어

 통상 3,4번을 많이 쓴다. 

---

1.2 추상 데이터 타입

자료형(data type) : 데이터의 종류, 우리말로는 자료형 

객체(object)와 객체간의 연산(operation)의 집합으로 정의됨

ex)
정수, 실수, 문자열 - 기초적인 자료형 
이외에도 스택, 큐, 리스트, 트리등의 새로운 자료형들도 존재

 

자료형을 작성할 때는 실행가능한 연산에 대해서도 신경을 써야 함

ex) 나머지 연산을 할 때 정수 데이터에는 의미가 있지만, 실수 데이터에서는 의미가 없음.

 

추상 자료형(ADT: abstract data type)

자료형을 추상적, 수학적으로 정의한 것

실제적인 구현으로부터 분리되어 정의된 자료형이며, 많은 장점이 있음.

객체와 연산들의 명세가 구현으로부터 분리된 자료형

 

소프트웨어 개발과 유지보수에서 가장 중요한 이슈는 '소프트웨어 시스템의 복잡성'을 관리하는 것

-> 이 핵심이 추상화(abstraction)와 관련된 도구개발

 

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

-> 정보은닉개념(information hiding)의 개념이 되었고 추상개념화(ADT)의 개념으로 발전됨.

 

ADT는 프로그래밍언어에 따라 여러 방법으로 구현된다.

객체지향언어에서는 "클래스"개념으로 구현된다. 

---

1.3 알고리즘의 성능 분석

프로그램의 효율성은 중요함

이유 1) 최근 상용 프로그램의 규모가 이전에 비해 굉장히 커지고 있음 (=처리할 자료의 양이 많아지므로 알고리즘의 효율성이 더욱 중요해짐)

이유 2. 사용자들은 여전히 빠른 프로그램을 선호함

 

효율적인 알고리즘이란 
1) 시작하여 결과가 나올 때까지의 수행시간이 짧으면서
2) 컴퓨터 내의 메모리와 같은 자원을 덜 사용하는 알고리즘이다.

 

수행시간 측정방법

clock()함수와 time()함수를 사용하는 방법이 있음.

그러나 알고리즘을 직접 구현해야하고, 동일한 하드웨어를 사용해야 하는 등의 문제가 존재

 

알고리즘의 복잡도 분석방법

알고리즘 복잡도 분석(complexity analysis) 방법으로 직접구현하지 않고도 대략적인 알고리즘의 효율성을 비교할 수 있음

 

시간 복잡도 함수

알고리즘 분석은 2가지 측면으로 살펴볼 것이다.( 알고리즘의 수행시간과 알고리즘이 필요로 하는 기억공간 양) 

1) 알고리즘의 수행시간 분석= 시간 복잡도(time complexity)
2) 알고리즘의 기억공간 분석=공간 복잡도(space complexity)

 

알고리즘 복잡도를 이야기할때는 대개 시간 복잡도를 말하는 것. 

시간 복잡도는 절대적인 시간을 이야기하는 것이 아니라, 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시함.

보통 수행횟수는 n으로 주어지므로 연산의 수를 입력의 개수 n의 함수=T(n) 으로 나타내고 시간복잡도 함수라고 말함

 

빅오 표기법

보통 시간복잡도 함수에서는 차수가 가장 큰 항만을 고려한다. (차수가 가장 큰 항이 전체의 값을 주도하기 때문)

정확한 연산의 개수보다는 알고리즘의 일반적인 증가추세가 중요하다.

 

시간복잡도 함수에서 이렇게 불필요한 정보를 제거하고 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 함. 

 

빅오 표기법: n의 값에 따른 함수의 상한값을 나타내는 방법 O(n)으로 표현

빅오 표기법을 사용하면 시간복잡도 함수에 별로 기여하지 못하는 항을 생략함으로써 시간복잡도를 간단하게 표시가능

빅오표기법을 얻는 방법은 다항식의 최고차항의 차수만을 사용하는 것.

 

* 많이 쓰이는 빅오 표기법

o(1) < o(log n) < o(n) < o(n*log n) < o(n2) < o(n3) < o(2n) < o(n!)

빅오 표기법은 입력개수에 따른 기본연산의 수행횟수를 개략적으로 나타낸 것으로 알고리즘의 대략적인 수행시간 추정가능(알고리즘이 지수형이나 팩토리얼형 시간복잡도를 가지면 사실상 사용불가 -> 과도한 수행시간으로 인해서)

 

빅오표기법 이외의 표기법

빅오표기법은 상한을 표현한 것, but 상한은 여러개가 있을 수 있음

따라서 빅오표기법은 최소 차수 함수로 표기되었을 때만 의미가 있다.

이러한 문제점을 보완하기 위해 빅오메가와 빅쎄타 표기법이 있음

 

빅오메가 표기법(big omega)는 어떤 함수의 하한을 표시하는 방법

빅쎄타(big theta)는 동일한 함수로 상한과 하한을 만들 수 있는 경우를 말함

 

가장 정밀한 것은 빅쎄타이지만 통상적으로 빅오 표기법을 가장 많이 사용함

(빅오 표기법은 최소차수로 상한을 표시한다고 가정함)

 

최선, 평균, 최악의 경우

같은 알고리즘이라해도 입력집합에 따라 수행시간이 달라진다.

보통 최악의 경우(worst case)의 수행시간이 알고리즘의 시간 복잡도 척도로 많이 쓰인다.