(1주차 1차) 자료구조의 개요

자료(Data)

현실 세계에서 관찰이나 측정을 통해 수집된 값이나 사실

 

정보(Information)

주어진 상황에 대해 적절한 의사결정을 위해 자료를 가공하여 얻어진 유용한 결과

자료를 처리하여 얻어진 유용한 결과로 i=P(D)로 표현할 수 있음

 

자료구조는 왜 필요할까?

일상생활에서 자료를 정리하고 조직화 하는건 사물을 편리하고 효율적으로 사용하기 위함.

 

자료구조(Data Structure)

컴퓨터에서 자료를 정리하고 조직화 하는 다양한 구조로, 추상화를 통해 자료의 논리적인 관계를 구조화한것

 

스택: 그릇을 쌓아서 보관하는것. (LIFO)

큐: 마트 계산대의 줄 (FIFO)

리스트: 할일 리스트

사전(정렬) : 영어사전

그래프: 지도

트리: 회사의 조직도

 

 

컴퓨터 프로그램은 자료구조와 알고리즘으로 구성됨

단순한 데이터를 처리하는게 아니라 데이터의 자료구조를 파악하여 알고리즘으로 푼다..

 

알고리즘  = 해답

컴퓨터로 문제를 풀기 위한 단계적인 절차, 방법 명령어들의 집합

 

알고리즘의 조건

입력: 0개 이상의 입력이 존재하여야 함

출력: 1개 이상의 출력이 존재하여야 함(1개이상)

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

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

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

 

알고리즘의 기술하는 4가지 방법

1. 영어, 한국어와 같은 자연어

2. 흐름도(Flow chart)

3.의사 코드(Pseudo-code) = 유사코드

4.프로그래밍 언어

 

 

자연어

인간이 읽기 쉬운 반면, 자연어의 단어들을 정확하게 정의하지 않으면 의미 전달이 모호해질 우려가 있음

 

흐름도

직관적이고 이해하기 쉬운 알고리즘 기술 방법이지만 복잡한 알고리즘의 경우 상당히 복잡해짐

도형에대한 학습이 되어있어야 한다.

 

의사코드 = 슈도코드

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

프로그램을 구현할 때의 여러 가지 문제들을 감출 수 있음

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

-> 특정 언어에서는 대입연산자를 '=' 으로 표현하지만, 의사코드는 <- 으로 표현한다.

 

특정 프로그래밍 언어

알고리즘의 가장 정확한 기술 가능

실제 구현시 많은 구체적인 사항들이 알고리즘의 핵심적인 내용에대한 이해를 방해할 수 있음

 

 

추상 자료형

추상화의 개념 < -- > 구체화(반대) 

공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는것

-> 어떤 시스템의 간략화 된 기술 또는 명세임

-> 시스템의 정말 핵심적인 구조나 동작에만 집중함

 

자료형의 개념 // 자료의 종류

> 자료형(Data type)은 데이터의 종류

> 데이터의 집합과 연산의 집합을 말함

> 기초 자료형에는 정수,실수,문자열 등이있음

> 다른 자료형을 묶을 수 있는 자료형,배열,구조체 등이 있음

 

 

자료형 구분

 

정수 자료형

데이터의 집합과 연산의 집합 ( +, -)

정수끼리  +, -, *, /, %, ==, >, <  가능하다. (연산자)

연산자는 기호로 표현 가능하고 함수로 표현도 가능하다.

 

추상 자료형의 개념(ADT)

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

> 데이터나 연산이 무엇인가를 정의함

  - 데이터나 연산이 어떻게(How)컴퓨터 상에서 구현할 것인지 정의하지않음

 

객체: 추상 데이터 타입에 속하는 객체가 정의함

연산: 객체들 간의 연산이 정의되는데 추상 데이터 타입과 외부를 연결하는 인터페이스 역활

->정보은닉, 외부 접근

 

예시)

TV를 보면 채널변경 버튼, 볼륨버튼이 인터페이스다.

어떻게 작동하는지는 아 필요가 없다.

 

 

알고리즘의 복잡도 분석

 

실행 시간을 측정하는 방법

> 2개의 알고리즘의 실제 수행 시간을 측정하는것

> 실제로 구현하는 것이 필요함 (프로그래밍언어로..)

> 동일한 하드웨어를 사용해야 함

 

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

> 직접 구현하지 않고서 수행 시간을 분석하는것

> 알고리즘이 수행하는 연산의 횟수를 측정하여 비교

> 일반적으로 연산의 횟수는 N함수

 

수행 시간 측정

> 알고리즘을 프래그래밍 언어로 작성하여 실제 컴퓨터상에서 실행시긴 후 그 수행 시간을 측정함

 

시간 복잡도

> 시간 복잡도는 알고리즘을 이루고 있는 연산들이 몇번이나 수행되는지를 숫자로 표시한 것

 :복잡도 분석의 종류 = 시간 복잡도 , 공간 복잡도

 

복잡도 분석의 종류와 고려사항

입력의 개수 고려

 

표기법

빅오표기법

> 자료 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있음

> 연산의 횟수를 대략적(점근적)으로 표기한것

> 비공는 함수의 상한을 표시함

 

빅오메가 표기법

> 빅공메가는 함수의 하한을 표기함

> 최소 이만큼의 시간이 걸린다...

 

빅세타 표기법

>빅세터는 함수의 하한인 동시에 상한을 표시함

> ~ 사이에있다.