알고리즘/자료구조 (13) 썸네일형 리스트형 스택(Stack) Goal 스택을 구현할 수 있다. (배열 또는 연결리스트로 구현) 스택 구조를 그리고 스택에 대해 설명할 수 있다 스택이 사용되는 예시를 들 수 있고, 어떨 때 사용되는지 설명할 수 있다 스택(Stack) 한쪽 끝에서만 데이터가 삽입, 삭제가 일어나는 제한적 선형 자료구조 먼저 들어온 데이터가 나중에 출력되는 선입후출 FILO(First In Last Out) 형태의 자료구조 (FIFO = LIFO) 성질 데이터의 삽입, 삭제가 한쪽 끝에서만 이루어지는 제한적 선형자료구조 선입 후출 FILO(First In Last Out) (= 후입 선출 : LIFO) 형태의 자료구조 (스택, 큐, 데크와 같이 삽입 삭제가 특정 위치에서만 제한적으로 이루어지는 자료구조를 제한적 선형자료구조라 한다) 특징 원소의 추가 .. 연결 리스트(Linked List), 리스트(List) Goal 연결 리스트의 특징을 이해하고 장단점을 말할 수 있다 연결 리스트를 구현할 수 있다 배열과 연결 리스트의 차이점을 알고 적절히 사용할 수 있다 연결 리스트(Linked List) 개념 : 각 노드를 간선으로 연결시켜 표현한 자료구조 또는 그러한 표현 기법 특징 일반적으로 배열과 반대되는 특징들을 가지고 있다 연속된 메모리 공간에 저장할 필요가 없다 임의 접근이 불가능하다 저장 공간의 활용이 자유롭다 장단점 연결 리스트는 포인터의 연결을 맺고 끊을 수 있기 때문에 다음과 같은 장단점이 있다 [장점] 삽입, 삭제가 용이하다 배열에 비해 저장 공간 활용이 자유롭다 => 필요할때 추가/삭제가 가능하기 때 낭비되는 메모리가 적고 크기 변환에 유연하다 [단점] 배열에 비해 탐색이 느리다 O(n) => 임의.. 배열 Goal 배열의 특징을 이해하고 장단점을 말할 수 있다 배열의 장단점을 이해하고 적절한 상황에 맞게 배열을 사용할 수 있다 배열(Array) 개념 : 동일한 자료형을 연속적인 메모리 공간에 저장한 자료구조 특징 인덱스(index)를 사용하여 임의 접근(Random Access)이 가능하다. 각 항목이 동일한 자료형이므로 동일한 크기를 갖는다 저장 공간의 크기가 고정적이다. 장단점 [장점] 1. 원소 접근이 빠르다 원소 접근하는데 걸리는 시간이 상수 시간 O(1)이다. (배열시작 주소 + index * 원소 크기)로 해당 원소에 접근이 가능 => Random Access 가능 2. 캐시 적중률(Cache hit rate)이 높다 연속된 메모리 공간에 저장되기 때문에 캐시 지역성(cache locality).. 추상 자료형(Abstract Data Type) Goal 추상화와 추상자료형(ADT)에 대한 이해 추상 자료형을 정의할 수 있다 자료형(Data Type) 데이터를 식별하는 구분, 연산, 저장 방법 등을 모두 포함한 것 추상화(Abstraction) 핵심 개념이나 기능을 간추려 내는 것 => 개념을 만들어 가는 과정(개념의 일반화) 특징 자료구조에서 추상화는 세부 구현으로 부터 분리하여 개념을 일반화 시키는 것을 의미 (데이터 모델링) 무엇(what)인지는 정의하지만 어떤 언어를 사용해서 어떻게(how)구현할 것인지는 정의하지 않음 추상 자료형(Abstract Data Type : ADT) 세부 구현으로부터 분리해 핵심 개념이나 기능을 간추려 낸 자료형 => 구현 내용은 명시하지 않고 인터페이스만 제공 특징 추상화를 통해 정의됨 (데이터 모델링) 무엇.. 자료 구조 Orientation Goal자료구조에 대한 이해자료 구조(Data Structure)개념 : 자료를 효과적으로 표현, 저장, 처리하기 위한 기술 또는 그러한 형태사용 이유 : 자료의 특성이나 자료간의 관계 등에 따라 효율적으로 관리하기 위해 적절한 자료구조가 필요자료 구조의 구분자료들은 여러 가지 형태로 분류할 수 있다. - 정수, 실수, 문자 등과 같이 프로그래밍 언어 차원에서 기본적으로 제공되는 원시 타입(Primitive type)- 여러 자료구조가 복합적으로 구성된 복합 자료 구조- etc 주로 다룰 내용은 복합 자료구조이다. 선형 자료구조 / 비선형 자료구조선형 자료구조개념 : 자료들을 구성하는 원소들을 순차적으로 나열 시킨 형태종류 : 배열(리스트), 연결 리스트, 스택, 큐, 데크 등특징 : 한 원소 뒤에 하나.. 이전 1 2 다음
