알고리즘 (44) 썸네일형 리스트형 트리(Tree) Goal트리 기본 용어에 대한 이해트리와 이진 트리의 정의를 말할 수 있다트리와 이진트리의 성질에 따른 특징을 설명할 수 있다이진 탐색 트리에 대한 이해(정의, 연산, 성능, 활용 예시)힙에 대한 이해(정의, 연산, 성능, 활용 예시)트리의 기본 용어트리는 그래프의 특수한 형태로 그래프 모양이 나무를 뒤집어 놓은 것 같다고 해서 이름 붙여졌다. (트리 용어 이전에 그래프에 대한 이해와 관련 용어를 찾아보면 좋다)그래프 루트 노드(Root Node) : 트리에서 부모가 없는 최상위 노드. 트리의 시작점 부모 노드(Parent Node) : 루트 노드 방향으로 직접 연결된 노드 자식 노드(Child Node) : 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(Siblings Node) : 같은 부모 노.. 그래프(Graph) Goal그래프가 무엇인지 설명할 수 있다그래프 기본 용어에 대한 이해특징에 따라 그래프를 구분지어 말할 수 있다인접행렬, 인접 리스트에 대한 이해 (그래프 표현 방법에 대한 이해)그래프 탐색에 대한 기본 이해 (DFS, BFS)그래프(Graph)정점(vertex/node)과 간선(edge/link)으로 구성된 자료구조 그래프(G) = 정점 집합(V) + 간선 집합(E)수학적으로 그래프를 G = (V,E)와 같이 표현 정점(vertex / node) : 여러 가지 특성을 가질 수 있는 객체간선(edge / link) : 정점들간의 관계ex) 그래프 G1, G2가 있을 때 각각의 그래프의 정점과 간선은 다음과 같이 표시할 수 있다.- V(G1), E(G1)- V(G2), E(G2) 설명정점과 간선은 집합이.. 덱(Deque) Goal 덱을 구현 할 수 있다 덱의 구조를 그리고 설명할 수 있다 덱(Deque) 데이터의 입/출력이 양 끝단에서만 이루어지는 형태의 자료구조 특징 원소의 추가 O(1) 원소의 삭제 O(1) 원소의 확인 O(1) - 제일 앞, 뒤쪽만 확인 가능 삽입 삭제가 양 끝단에서만 이루어지는 제한적 선형 자료구조이다 덱(Deque)은 앞, 뒤 양쪽에서 데이터의 삽입 삭제가 가능하다는 점에서 스택이나 큐보다 덜 제한적이다. 이런 특징 때문에 Deque을 Stack또는 Queue형태로 사용이 가능하다. (입출력 부분의 함수를 제한을 걸면된다) 덱(Deque)의 구현 BOJ 덱 구현 문제 : https://www.acmicpc.net/problem/10866 - 배열 덱 - https://github.com/jihyu.. 큐(Queue) Goal 큐를 구현할 수 있다. (배열, 링크드 리스트로 구현) 큐 구조를 그리고 설명할 수 있다 큐가 사용되는 예시를 들고, 어떨 때 사용되는지 설명할 수 있다 큐(Queue) 데이터의 입력은 가장 뒤쪽(back, rear)에서, 출력은 가장 앞쪽(front)에서 이루어지는 형태의 제한적 선형자료구조 먼저 입력된 순서대로 출력되는 선입선출(FIFO) 형태의 자료구조 특징 원소의 추가 O(1) 원소의 삭제 O(1) 제일 앞쪽(front), 제일 뒤쪽(back) 원소 확인 O(1) => 원칙적으로 중간에 있는 데이터 확인 및 변경 불가능 원형 큐(Circular Queue) 큐를 논리적으로 원형 형태로 설계한 자료구조 원형큐는 큐를 배열로 구현했을 때 발생하는 문제점을 보완하기 위해 고안된 자료구조이다. .. 스택(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) 세부 구현으로부터 분리해 핵심 개념이나 기능을 간추려 낸 자료형 => 구현 내용은 명시하지 않고 인터페이스만 제공 특징 추상화를 통해 정의됨 (데이터 모델링) 무엇.. 이전 1 2 3 4 5 6 다음
