C++로 구현하는 자료구조와 알고리즘 pdf - c++lo guhyeonhaneun jalyogujowa algolijeum pdf

[C++로 쉽게 풀어쓴 자료구조] 01_자료구조와 알고리즘

본 포스팅의 내용은 [C++로 쉽게 풀어쓴 자료구조] 교재를 정리한 내용입니다.

Chapter 01 자료구조와 알고리즘

1.1 자료구조

1.2 알고리즘

1.3 추상 자료형

1.4 알고리즘의 성능 분석

자료구조(Data Structure)란

컴퓨터가 자료들을 정리하고 조직화하는 여러 가지 구조들

[ 자료구조 분류 ]

① 단순 자료구조 : 정수, 실수, 문자 등 프로그래밍 언어에서 기본적으로 제공하는 자료

② 복합 자료구조 : 여러 가지 자료들이 복합적으로 구성된 자료들

- 선형 자료구조(Linear data structure) : 자료들이 순서적으로 나열된 자료 구조

· 연결리스트 → 순서 접근 (sequential access)으로 시작 노드에서부터 하나씩 다음 노드로 이동하면서 원하는 자료를 찾아야 함

· 배열 → 직접 접근(direct access) 방식으로 인덱스를 이용해 한 번 만에 접근 가능

· 스택, 큐, 덱 → 자료의 접근이 맨 앞과 맨 뒤 항목으로 제한됨

- 비선형 자료구조(Non-linear data structure) : 자료들 간에 선형적인 순서가 있는 것이 아니고 복잡한 연결을 갖는 자료의 형태

· 그래프 : 정점을 연결하는 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 나눌 수 있음

· 트리 : 계층 구조를 표현하기에 적합한 자료구조

알고리즘(Algorithm)이란

어떤 문제를 해결하는 절차

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

​

추상화(Acstraction)란

복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념이나 기능을 간추려 내는 것

즉, 어떤 시스템의 간략화 된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것

​

추상자료형(Acstract Data Type, ADT)이란

자료의 집합과 자료에 가해지는 연산들의 집합에 대한 수학적인 명세

​

· 데이터 타입을 추상적(수학적)으로 정의한 것

· 데이터나 연산이 무엇(What)인가를 정의함

· 데이터나 연산을 어떻게(how) 구현할 것인지는 정의하지 않음

​

- 추상 자료형을 표현할 때는 먼저 객체를 정의하고, 다음으로 연산들을 정의한다. 객체는 주로 집합의 개념을 사용하여 표현하고, 연산의 정의에는 연산의 이름, 매개변수, 연산의 결과, 연산이 수행하는 기능 등을 기술

​

▶ 추상 자료형과 C++의 관계

· 추상 자료형의 데이터 : 구조체 사용

· 추상 자료형의 연산 : 함수를 사용

- 추상 자료형의 개념은 객체지향의 개념과 정확히 일치

- 객체지향언어인 C++에서는 클래스를 사용하여 추상 자료형을 구현

- 추상 자료형에서의 "객체"는 클래스의 속성(멤버 변수)으로 구현되고 "연산"은 클래스의 메소드(멤버 함수)로 구현

- C++에서는 private나 protected 키워드를 이용하여 속성과 연산에 대한 접근을 제한할 수 있음

- 클래스는 계층구조(상속)로 구성될 수 있음

복잡도 분석 : 알고리즘을 직접 구현하지 않고서도 대략적인 효율성을 분석 가능

- 좋은 알고리즘은 실행 시간이 빠르고 처리를 위해 필요한 기억 공간이 적은 것

① 시간 복잡도(Time complexity) : 알고리즘의 실행 시간을 분석 → 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지 숫자로 표현

② 공간 복잡도(Space complexity) : 알고리즘이 사용하는 메모리 공간 분석

​

빅오표기법이란

시간 복잡도 함수 T(n)에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법

- 시간 복잡도 분석에서는 함수의 전체 항이 아닌 최고차항만을 고려 → 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략하기 때문

​

시간 복잡도

​

[ n이 증가할 때 시간 복잡도 함수의 증가 ]