자료구조 1주차 자료구조의 소개

자료구조의 소개

자료란 무엇인가?

• 시스템에서 제공하는 자료형
• 사용자가 정의하는 자료형

자료의 관리

1. 추가

2. 제거

3. 검색

검색을 가장 빈번하게 사용하므로 가장 중요

검색의 3가지 종류

1. 임의의 원소 찾기 (Find arbitrary)
2. 가장 먼저/늦게 온 원소 찾기 (Find earliest/last)
3. 최대/최소인 원소 찾기 (Find top)

효율적인 기법

1. 기법이란 무엇인가?

• 기법(테크닉)
• 자료를 적절한 구조 (structure)를 갖도록 조직하고 그에 따른 연산 (operation)을 제공
• 구조 (structure)
• 개별적인 자료들이 목적에 적합한 관계를 갖도록 배치된 상태

구조 1. 리스트 (list)

자료를 한곳에 보관하기

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

검색을 쉽게 정렬한 리스트

구조 3. 큐 (queue)

도착한 순서대로 정렬한 리스트

구조 4. 계층 구조 (hierarchy)

족보를 표현하는 법

구조 5. 그래프 (graph)

관계를 시각적으로 표현

추상화

공통된 속성을 추출하여 이를 이용하는 과정
추상 자료형: c++이나 Java의 클래스 개념으로 구현

2. 효율이란?

어떤 성과를 얻기 위해서 얼마나 많은 자원을 투입하였는지 측정
성능이라고도함
= solution/resource

1. 최선의 경우 -> 최고기록
2. 평균의 경우 -> 평점
3. 최악의 경우 -> 대기 시간

컴퓨터의 자원

1. 시간 = cpu
2. 공간 = memory

시간이 더 중요함 (비쌈)

자료구조의 성능

입력된 자료의 크기에 따른 시간의 증가 속도를 표현