자료구조 2강 - 자료구조 기법(technique)란

기법(Technique)

- 자료를 적절한 구조(structure)를 갖도록 조직하고 그에 따른 연산(operation)을 제공

 

구조(structure)

- 개별적인 자료들이 목적에 적합한 관계를 갖도록 배치된 상태

 

연산(operation)

- 자료를 관리하기 위한 작업(추가, 제거, 검색 etc)

- 구조는 달라도 연산은 동일함 => 구조에 따른 연산의 구현 방법은 다름

 

1. 리스트(list)

자료를 한곳에 모아서 보관하면 편리

2. 정렬된 리스트(sorted list)

검색을 쉽게 하기 위해 자료가 있는 위치를 예측

3. 큐(queue)

만난 순서를 기억하기 위한 구조

4. 계층구조(hierarchy)

관계에 일관성이 있는 구조(트리)

5. 그래프(graph)

관계를 시각적으로 표현하는 구조

 

추상화(Abstraction)

개별적인 사람이나 사물, 상황의 성질로부터 추출되어 가공된 일반적이고 공통적인 개념

- 매우 다양한 형태의 자료가 존재

- 각 자료들의 개별적인 속성을 제거하고 공통된 속성을 추출하여 이를 이용하는 과정

- class of objects whose logical behavior is defined by a set of values and a set of operations

 

효율(efficiency)

- 어떤 성과(solution)를 얻기 위해서 얼마나 많은 자원(resource)을 투입하였는지를 측정

- 성능(performance)라고도 함

- Efficiency or Performance = solution / resource

 

효율적(efficient) vs 효과적(effective)

- 어떤 성과를 얻기 위해서 얼마나 많은 자원을 투입하였는지를 측정하는 점은 동일

- 효율적은 동일한 성과를 얻기 위해서 투입된 자원의 크기에 따라서 결정됨(성과 고정)

- 효과적은 동일한 자원을 투입했을 때 얻는 성과의 크기에 따라서 결정됨(자원 고정)

 

성능의 3가지 경우

1. 최선의 경우(Best Case)

ex. 최고 기록 -> 여러 기록들 중에서 가장 좋은 기록만 기억

2. 평균의 경우(Average Case)

ex. 평점 -> 여러 과목의 점수를 평균해서 산정

3. 최악의 경우(Worst Case)

ex. 대기 시간 -> 가장 긴 시간을 알려줌

 

자료 구조에서의 성능은 최악의 경우에 대한 성능이다 => 보장의 의미

 

컴퓨터의 자원(resource)

- 시간에 대한 자원이 더 중요하다

1. 시간(time) -> cpu

2. 공간(space) -> 메모리(memory)

 

자료구조의 성능

- 입력된 자료의 크기에 따라서 시간(공간)이 얼마나 필요한지 측정

- 입력된 자료의 크기가 증가할수록 요구되는 시간(공간)의 증가 속도를 표현