자료구조

1.1 자료구조와 알고리즘 자료구조란? 컴퓨터 프로그램 = 자료구조(data structure) + 알고리즘(algorithm) 구성 자료구조: 프로그램에서 자료들을 정리하는 여러 가지 구조들(스택, 큐, 리스트, 사전, 탐색 구조, 그래프, 트리) 알고리즘: 문제를

순환(recursion): 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법순환은 본질적으로 순환적으로 정의된 문제나 자료구조를 다루는 프로그램에 적절 ex) 팩토리얼 함수 계산, 피보나치 수열, 이항 계수 계산, 각종 이진 트리 알고리즘,

3.1 배열 배열의 개념 배열(array): 거의 모든 프로그램밍 언어에서 기본적으로 제공되는 데이터 타입, 여러 개의 동일한 데이터 타입의 데이터를 한 번에 만들 때 사용 각각의 변수를 사용하는 것은 서로 다른 이름으로 접근해야 하므로 추후 다른 연산이나 데이터의

4.1 리스트 추상 자료형 리스트 소개 리스트(list) 또는 선형 리스트(linear list)의 항목들은 순서 또는 위치를 가짐 $$L = (item0, item1, item2, ..., item{n-1})$$ 리스트 연산 새로운 항목을 리스트의 임의의 위치에

5.1 스택 추상 자료형 후입 선출(LIFO: Last-In First-Out): 가장 최근에 들어온 자료가 가장 먼저 나가는 것 스택(stack): 후입 선출의 형식으로 입출력이 일어나는 자료구조 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터

큐(queue): 먼저 들어온 데이터가 먼저 나가는 구조, 선입 선출(FIFO: First-In First-out) 특성을 지닌 자료구조스택: 삽입과 삭제가 같은 쪽에서 일어남큐: 삽입과 삭제가 다른 쪽에서 일어남, 삽입이 일어나는 곳 후단(rear), 삭제가 일어나는

7.1 트리의 개념 선형 자료구조(linear data structure): 자료들이 직선과 같이 나열되어 있는 구조(리스트, 스택, 큐) 계층적인 구조(hierarchial structure): 자료의 계층적인 관계를 표현할 수 있는 구조(트리) 트리(tree):

8.1 우선순위 큐 추상 자료형 우선순위 큐의 소개 우선순위 큐(priority queue): 데이터들이 우선순뤼를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 됨 |자료구조|삭제되는 요소| |----|----| |스택| 가장 최근에 들어온 데이터| |큐| 가

9.1 정렬이란? 정렬(sorting): 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미 레코드(record): 정렬시켜야 될 대상 필드(field): 레코드가 더 작은 단위로 나눠짐 키(ke

10.1 그래프란? 그래프 소개 그래프(graph): 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프의 역사 수학자 오일러(Euler)는 "모든 다리를 한 번만 건너서 출발했던 장소로 돌아올 수 있는가?" 라는 문제에 대한 답을 그래프 이론을 이용해서

11.1 해싱이란? 해싱: 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근 -> 해시 테이블을 이용한 탐색 해시 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능항 구조 11.2 추상 자료형 사전

12.1 탐색이란? 탐색: 탐색 키와 데이터로 이루어진 항목 중에서 원하는 탐색 키를 가지고 있는 항목을 찾는 것 탐색의 단위: 항목 힝목 안에는 항목과 항목을 구별시켜주는 키(Key) 존재 => 탐색 키(search key) 12.2 정렬되지 않은 배열에서의 탐색