CS/자료구조

해시(Hash)해시는 데이터를 다루는 기법 중 하나로 검색과 저장을 아주 빠르게 하는 자료구조이다.데이터를 저장할 때 키-값 형태로 데이터가 존재하고 키 값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어난다.해시 자료구조는 데이터를 키-값 형태로 저장해 준다고 했는데 그러기 위해서 키 값을 고정된 길이의 값으로 바꿔주는 해시 함수와 해싱이라는 과정 그리고 키-값 데이터를 저장해 주는 해시 테이블을 이해해야 한다.  해시 함수(Hash Function)와 해싱(Hashing)해시 함수라고 불리는 것으로 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 알고리즘이다.해시 함수는 키 값을 고정된 길이의 hash로 변환하는 역할을 한다. 그림과 같이 사람의 이름을 해시 함수를 거쳐서 ..

힙(Heap)힙은 완전 이진트리의 일종으로 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조이다.이진 트리에 대해서 잘 모른다면 밑의 글을 읽고 나서 힙을 공부해 보자. 자료구조 - 이진 트리(Binary Tree)이진 트리(Binary Tree)이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 뜻한다.트리 영역에서 가장 많이 사용되는 형태로 트리를 1차원 배열로 표현해준다. 이진 트리의hotechstory.tistory.com 힙의 특징힙 자료구조에는 여러 가지 특징이 있는데 하나씩 살펴보자.1. 힙은 완전 이진트리다. 즉, 왼쪽에서 오른쪽으로 채워지는 마지막 수준을 제외하고 트리의 모든 수준이 완전히 채워진다. 이 속성은 트리가 배열을 사용하여 효율적으로 표현되도록..

레드/블랙 트리(Red/Black Tree)레드/블랙 트리는 균형을 유지하기 위해 일련의 규칙을 사용하는 자가 균형 이진 탐색 트리의 유형으로 트리의 초기 모양에 관계없이 삽입, 삭제, 검색과 같은 작업에 대한 O(log n) 시간 복잡도를 보장한다.레드/블랙 트리는 각 수정 후 트리를 조정하기 위해 간단한 색상 코딩 체계를 사용하여 자체 균형을 유지한다.레드/블랙 트리는 각 노드가 빨간색 또는 검은색일 수 있는 색상이라는 추가 속성을 갖는 자체 균형 이진 탐색 트리이다.삽입 및 삭제 중에 균형을 유지하여 효율적인 데이터 검색 및 조작을 보장한다. 레드 블랙 트리의 속성레드/블랙 트리에는 여러 가지 속성들이 있는데 이러한 속성들을 알아야 동작 과정을 이해할 수 있다.어떤 속성들이 있는지 하나씩 살펴보자...

AVL 트리 AVL 트리는 모든 노드의 왼쪽 및 오른쪽 하위 트리 높이 차이가 1보다 클 수 없는 이진 탐색트리로 자체 균형 이진 탐색 트리라고도 한다. 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이를 노드의 균형 요소(BF, Balance Factor)라고 하는데 이러한 균형 요소를 가지고 트리의 균형을 확인하여 노드를 적절한 곳으로 재배치해준다. 그렇다면 그냥 이진 탐색 트리를 사용하면 되지 굳이 AVL 트리를 사용하는 이유가 뭘까? 일단 이진 탐색 트리는 루트 노드를 중심으로 들어오는 데이터가 큰지, 작은 지를 판별해 데이터를 삽입하게 된다. 이진 탐색 트리의 특징은 효율적으로 탐색, 삽입, 삭제를 할 수 있는데 데이터를 삽입하고 삭제하는 것은 결국 탐색이 먼저 이루어져야 하므로 이진..

이진 트리(Binary Tree)이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 뜻한다.트리 영역에서 가장 많이 사용되는 형태로 트리를 1차원 배열로 표현해준다. 이진 트리의 종류1. 편향 이진 트리: 노드들이 한 쪽으로 편향돼 생성된 이진 트리2. 포화 이진 트리: 프리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리3. 완전 이진 트리: 마지막 레벨(차수)을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽 부터 채워진 트리※ 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되므로 데이터를 담을 때 완전 이진 트리의 형태로 담는 것이 좋다. 이진 트리의 순차 표현가장 직관적이면서 편리한 트리 자료구조 형태는 바로 배열이다.배열의 인덱스..

트리(Tree)트리는 노드와 에지로 연결된 그래프의 특수한 형태로 비선형 계층적 자료구조이다.각 노드는 여러 노드의 주소를 저장한다. 모든 노드는 자식의 주소를 저장하고 첫 번째 노드의 주소는 루트라는 별도의 포인터에 저장된다.그래프의 특수한 형태이기 때문에 그래프의 표현으로도 트리를 표현할 수 있다. 트리의 구성 요소노드 - 데이터의 인덱스와 벨류를 표현하는 요소에지 - 노드와 노드의 연결 관계를 나타내는 선루트 노드 - 트리에서 가장 상위에 존재하는 노드부모 노드 - 두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드 - 두 노드 사이의 관계에서 하위노드에 해당하는 노드리프 노드 - 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리 - 전체 트리에 속한 작은 트리 트리의 ..

그래프(Graph)그래프는 자료구조 중 하나로 노드(Node, 정점)와 에지(Edge, 간선)로 구성된 집합으로 비선형 자료 구조이다.노드는 데이터를 표현하는 단위고 에지는 노드를 연결해 준다.언뜻 보면 그래프와 트리가 비슷하게 보일 수 있는데 차이점으로는 그래프는 사이클이 발생하지만, 트리는 사이클이 발생하지 않는다는 차이가 있다. 그래프의 종류그래프 자료구조는 다양한 형태를 가지고 있는데 그중에서 간단하게 3개만 살펴보자. 무방향 그래프무방향 그래프는 말 그대로 정점을 이어주는 간선에 방향성이 없는 그래프로 순서가 지정되지 않은 쌍이다.무방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 (Vi , Vj)로 표현하는데 방향이 없기 때문에 (Vi , Vj)와 (Vj , Vi)는 같은 간선이다. 방향 그..

스택(Stack)스택(Stack)은 삽입과 삭제 연산이 후입선출(LIFO, Last In First Out)로 이루어진 선형 자료구조이다.가장 마지막에 삽입된 요소가 가장 먼저 삭제되는 구조로 삽입과 삭제가 한쪽에서만 일어난다.- 스택은 DFS(깊이 우선 탐색), 백트레킹 종류의 코딩 테스트에 사용된다. 요리를 배웠던 기억을 되살려 햄버거를 가지고 스택을 표현해보려고 한다.우리가 햄버거를 만든다고 상상해보자.햄버거 재료들을 차곡차곡 쌓아서 맛있게 만들었지만, 만약 중간에 들어갈 토마토를 까먹었다고 하면 어떻게 해야 될까?토마토가 위치해야 되는 자리까지 위에서부터 하나씩 뺄 것이다. 빵에서부터 치즈까지 빼고 난 후 토마토를 다시 쌓고 뺏던 재료들을 다시 쌓는다. 스택에서 사용되는 주요 메서드- top():..

배열(Array)- 배열은 메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조이다.- 배열은 인덱스를 통해 값을 바로 접근할 수 있다.- 배열의 단점으로는 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.- 위의 사진처럼 6이라는 값은 3과 4 사이에 삽입하려면 4와 5를 한 칸씩 뒤로 옮겨야 된다. 만약 배열의 길이가 1,000,000 정도 된다면 하나의 값을 삽입하기 위해서 많은 양의 데이터를 움직여야 하는 단점이 있다.- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.- 구조가 간단하므로 코딩 테스트에서 제일 많이 사용된다. 리스트(List)리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 선형 자료구조이다.리스트는 배열과 ..