Hash Table - (key, value) 한 쌍의 형태로 데이터 저장 key와 value가 한 쌍의 형태로 저장되는 자료구조. 각 key에 해시 함수를 적용해 내부 버킷에 값을 저장하여 관리한다. 트리를 이용하면 해당 위치에 맞는 자리를 찾아야 하지만, 해싱은 key 하나로 쉽게 값을 가져올 수 있다. 특징 순서대로 저장되지 않는다. 트리나 배열보다 빠른 속도로 데이터에 접근할 수 있다. key는 중복된 값을 가질 수 없다. value는 중복된 값이 올 수 있다. key는 value를 찾기 위한 열쇠의 역할을 한다. 만약 동일한 키가 여러개 존재한다면, 해당 키로 우리가 찾고자 하는 값을 찾을 수 없다. 해당 컬렉션에서 키는 유일하게 존재해야 한다. 해시 함수 Hash Function 해시 함수를 ..

트리(Tree) - 계층적 관계를 표현하는 비선형 자료구조. 상위·하위로 나뉘거나 포함하는 관계일 시 계층구조로 표현. 자료가 저장된 노드 Node와 이 노드는 잇는 간선 Edge로 구성 루트 노드 Root node: 최상위에 있는 노드 단말 노드 Leaf node, Terminal node: 하위 노드가 없는 노드 내부 노드 Internal node: 단말 노드가 아닌 (하위 노드가 있는) 노드 형제 노드 Sibling node: 같은 부모 노드를 가지는 노드 레벨 Level: 루트 0레벨부터 아래로 내려갈수록 값 증가 크기 Size: 본인을 포함하여 자손 노드의 수 깊이 Depth: 해당 노드부터 루트까지 간선의 수 높이 Height: 최하 리프에서 루트까지 깊이 = 최대 레벨의 크기와 동일 서브 트..

Stack - Last in, First out : LIFO Queue - First in, First out : FIFO 스택과 큐는 일렬로 늘어선 자료를 표현한다. 자료구조는 데이터 표현에 따라 선형 자료구조와 비선형 자료구조로 나뉜다. 스택과 큐도 배열이나 리스트처럼 선형 자료구조의 일종이다. 이 두 가지를 나누는 기준은 자료를 어떤 순서로 삽입하고 삭제하냐로 볼 수 있다. 1. Stack 스택 : 후입선출 방식을 사용한다. 가장 늦게 들어온 데이터가 가장 먼저 빠져나간다. 웹 브라우저의 뒤로가기를 예시로 들수있다. 우리가 지나온 순서에 따라 스택에 삽입되고, 뒤로가기 버튼을 통해 직전에 왔던 길을 따라 되돌아간다. 이와 같이 가장 먼저 들어온 것이 제일 마지막에 빠져나가는 방식이 스택이다. 기본 ..

순차 리스트: 배열 기반의 리스트 연결 리스트: 메모리 동적 할당을 기반으로 구현된 리스트 리스트 자료구조 기본 기능은 동일하지만 기능을 제공하는 특성에 차이가 있다. 리스트 나란히 저장된 자료구조로 중복된 데이터를 저장할 수 있다. 순서가 있고, 중복을 허용한다. 일렬로 늘어선 자료를 저장하기 때문에 선형 자료구조 라고 부른다. 배열과 비슷하게 볼 수 있지만, 배열과 전혀 다른 형태를 가지고 있다. 배열은 메모리가 연속적으로 위치해 있지만, 연결 리스트의 원소는 각자 메모리를 가지고 다음 원소를 가리키는 형식으로 구서현된다. 각 요소들을 노드 라고 부르며, c언어로 표현하자면 포인터로 다음 요소의 주소값을 가리키고, 자바로 표현하면 다음 요소를 참조하는 방식으로 연결된다. 연결리스트는 많이 사용하는 자..

Graph - 선형 자료구조로 표현하기 어려운 다:다 관계를 가지는 원소를 표현 G = ( V , E ) vertex 정점: 대상이나 개체 → V : 정점의 집합 edge 간선: 정점 간의 관계 → E : 간선의 집합 그래프는 정점과 간선으로 정의된다. 계층구조로 이루어진 트리는 선형으로 표현하기 어렵다. 선형으로 표현하기 어려운 자료를 표현하기 위해 그래프가 사용된다. 1. 종류 1) 방향으로 분류 ① 무방향 그래프, 무향 그래프 (undirected graph) 정점을 연결하는 간선의 방향이 없는 그래프 방향이 없어 정점 i와 j가 있으면 (i, j) = (j, i) ② 방향 그래프, 유향 그래프, 다이 그래프 (directed graph) 간선이 방향을 가지고 있는 그래프 선후 관계 등을 나타낼 수..