Tag Archives: 자료구조

C++로 쉽게 풀어쓴 자료구조/ 큐

큐(Queue)의 추상 자료형

큐란?

입출력이 선입선출(First-In First-Out)인 자료구조.

삽입과 삭제가 같은 위치에서 일어나는 스택과 달리 큐는 삽입과 삭제가 다른 위치에서 일어나는데, 삽입이 일어나는 곳을 후단(rear), 삭제가 일어나는 곳을 전단(front)이라고 한다.

Continue reading

C++로 쉽게 풀어쓴 자료구조/ 배열과 클래스

배열(Array)

배열의 개념

배열은 거의 모든 프로그래밍 언어에서 기본적으로 제공되는 자료형으로 많은 고급 자료구조들에서 사용된다. 배열은 주로 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다.

배열의 가장 기본적인 특징은 ‘인덱스, 요소’ 쌍의 집합이라는 것이다. 즉, 인덱스가 주어지면 해당하는 요소가 대응되는 자료구조이다. 배열에서는 모든 요소가 동일한 자료형이며 인덱스를 사용하여 직접 접근 할 수 있다.

Continue reading

프로그래밍/ 자료구조

트리

각 노드들이 나무처럼 계층 구조를 가진 자료 구조. 상위 노드를 부모, 하위 노드를 자식, 동일 계층의 노드를 형제라고 부른다.


http://stackoverflow.com/questions/19330731/tree-implementation-in-java-root-parents-and-children

이진 트리 (Binary Tree)

트리 구조 중에서 자식 노드를 최대 2개까지만 갖는 경우를 이진트리라고 한다.


https://en.wikipedia.org/wiki/Binary_tree

이진 검색 트리 (Binary Search Tree)

이진 검색 트리는 이진 트리 중에서 값의 배치를 일정한 규칙에 의거하여 배치한 이진 트리를 의미하는데, 임의의 노드의 왼쪽 자식은 해당 노드 보다 작은 값을 가지며, 오른쪽 자식은 해당 노드보다 큰 값을 갖는다.

이렇게 구성된 트리는 특정 값을 찾을 때 현재 노드의 값보다 큰지, 작은지에 따라 어느쪽 노드를 찾을지를 빠르게 결정 할 수 있다.


https://en.wikipedia.org/wiki/Binary_search_tree

힙 (Heap)

힙은 이진 트리 중에서 부모와 자식 간에 대소 관계가 성립하는 트리를 말하는데 –형제 간의 대소 관계는 없다– 부모가 자식보다 큰 값을 가질 때 ‘최대 힙’, 부모가 자식보다 작은 값을 가질 때 ‘최소 힙’이라고 부른다.


https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

해시 테이블

키(key)-값(value)으로 구성된 자료구조. 해시 맵이라고도 한다. 저장된 자료와의 비교를 통해 자료를 찾지 않고, 키 값을 이용해 원하는 값을 단 한 번에 찾을 수 있는 자료구조이다.


https://en.wikipedia.org/wiki/Hash_table

그래프

각 노드(Node)들과 노드들을 잇는 선(Edge)로 이루어진 집합. 노드와 노드를 잇는 선에 방향이 없는 그래프를 무향 그래프, 있는 그래프를 유향 그래프라고 한다.


http://www.codediesel.com/algorithms/building-a-graph-data-structure-in-php/

노드와 노드를 잇는 선에 가중치가 존재할 수도 있고 없을 수도 있다.

행렬을 이용한 그래프 표현

노드와 노드의 관계는 행렬을 이용해서 표현할 수 있다. 행렬상의 0은 노드간의 연결이 없음을 의미하며, 1이상의 숫자가 있으면 노드간에 연결이 있음을 뜻한다.


http://www.thecrazyprogrammer.com/2014/03/representation-of-graphs-adjacency-matrix-and-adjacency-list.html

리스트를 이용한 그래프 표현

노드와 노드의 관계는 리스트를 이용해서도 표현할 수 있다.


http://www.thecrazyprogrammer.com/2014/03/representation-of-graphs-adjacency-matrix-and-adjacency-list.html