해시 테이블(Hash Table)은 키를 값에 연결하여, 하나의 키가 0 또는 1개의 값과 관련되는 것을 허용하는 자료구조입니다. 이는 키를 통해 데이터를 빠르게 검색할 수 있게 해주는 구조입니다. 해시 테이블은 해시 함수를 사용하여 키를 해시 코드라는 숫자로 변환하고, 이 해시 코드를 인덱스로 사용하여 값을 배열에 저장합니다. 이 때, 서로 다른 키가 동일한 해시 코드를 생성하는 경우를 해시 충돌이라고 합니다. 해시 충돌을 해결하기 위한 방법은 여러가지가 있습니다. 1. 체이닝(Chaining) : 같은 해시 코드를 가진 항목들을 연결 리스트로 관리하는 방법입니다. 충돌이 발생하면, 해당 인덱스에 리스트를 만들어 추가하는 방식입니다. 2. 오픈 어드레싱(Open Addressing) : 충돌이 발생하면..
그래프(Graph) 이해하기 그래프는 여러 상황을 모델링할 수 있는 강력한 도구로, 정점(Vertex)과 간선(Edge)으로 구성된 복잡한 네트워크를 표현하는 자료구조입니다. 그래프의 종류 그래프는 크게 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph), 그리고 가중 그래프(Weighted Graph)로 나뉩니다. 무방향 그래프: 간선에 방향성이 없는 그래프로, 간선으로 연결된 두 정점은 서로 동등한 관계를 가집니다. 방향 그래프: 간선에 방향성이 있는 그래프로, 간선으로 연결된 두 정점은 시작점과 끝점의 관계를 가집니다. 가중 그래프: 간선에 가중치가 부여된 그래프로, 각 간선은 특정한 값을 가지며 이는 경로의 비용, 길이 등 다양한 것을 표현할 수 있습니다. 그..
자료구조(Data Structure)는 데이터를 효율적으로 구성하고 관리하는 방법에 대한 개념을 의미합니다. 데이터 구조는 데이터를 저장, 조작, 관리하고 처리하는 방법을 제공하는 방식으로 구현됩니다. 프로그래밍에서 자료 구조는 데이터를 저장하는 방법과 함께 그 데이터에 접근하는 방법에 대한 규칙 집합으로 생각할 수 있습니다. 자료구조는 크게 선형 구조와 비선형 구조로 나눌 수 있습니다. 선형 구조는 데이터 요소를 일렬로 배열하는 방법이며, 비선형 구조는 데이터 요소를 계층적으로 배열하는 방법입니다. 자료구조는 데이터 구성 및 처리에 대한 효율성을 높일 수 있는 매우 중요한 개념입니다. 각 자료구조는 해당 문제를 해결하기 위해 적합한 방식으로 선택되어야 하며, 사용 시 기억해야 할 다양한 용도와 제약 조..
트리(Tree)는 계층 구조를 표현하는 비선형 자료 구조입니다. 하나의 루트(Root)노드에서 시작하여 여러 레벨의 자식 노드들이 분기되는 구조를 가지고 있습니다. 각 노드는 부모 노드와 자식 노드를 가지고 있으며, 한 노드는 여러 개의 자식 노드를 가질 수 있습니다. 트리는 이진 트리(Binary Tree)와 다진 트리(M-ary Tree)로 나뉩니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 의미합니다. 다진 트리는 각 노드가 최대 M개의 자식 노드를 가지는 트리를 의미합니다. 대표적으로 3진 트리, 4진 트리 등이 있습니다. 트리는 다음과 같은 용어를 사용합니다. 루트(Root) : 트리의 최상위 노드이며, 모든 노드는 루트로부터 직간접적으로 연결되어 있습니다. 부모(Pare..
큐(Queue)는 자료를 일시적으로 저장하기 위한 자료구조 중 하나로, 선입선출(First-In-First-Out, FIFO) 원칙을 따릅니다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있습니다. 일상생활에서 대기 줄을 예시로 들 수 있습니다. 가게에서 줄서는 사람들이나, 티켓을 발권하는 키오스크 등에서도 자주 사용됩니다. 큐는 대기열을 모델링하는 데 자주 사용됩니다. 예를 들어, CPU 스케줄링, 네트워크 패킷 라우팅, 입출력 버퍼, 작업 큐 등에서 사용됩니다. 큐는 주로 다음과 같은 기본 연산을 지원합니다. Enqueue : 큐의 끝에 데이터를 추가합니다. Dequeue : 큐의 맨 앞에서 데이터를 제거합니다. Peek/Front : 큐의 맨 앞에 있는 데이터를 조회합니다. IsEmpty..
스택(Stack)은 후입선출(Last-In-First-Out, LIFO) 방식으로 자료를 저장하는 선형 자료구조 입니다. 쉽게 말하면, 데이터를 쌓는 상자라고 생각하면 됩니다. 맨 위에 데이터가 추가되고, 가장 위에 있는 데이터부터 차례로 제거됩니다. 스택은 보통 push와 pop 두 가지 기본 연산을 제공합니다. push 연산은 스택의 맨 위에 데이터를 추가하는 것이며, pop연산은 스택의 맨 위에 있는 데이터를 제거하고 반환하는 것 입니다. 그 외에도 스택에서는 top 연산이 지원되며, 이는 스택의 맨 위에 있는 데이터를 반환하지만, 데이터를 제거하지는 않습니다. 스택은 컴퓨터 과학에서 광범위하게 사용되며, 여러 가지 알고리즘에서 활용됩니다. 예를들어, 함수 호출 시 함수 내부에서 사용하는 지역 변수..
연결 리스트는 자료를 저장하는 자료구조 중 하나로, 물리적인 순서와 논리적인 순서가 일치하지 않을 때 사용됩니다. 선형 자료 구조로서, 요소들이 일렬로 연결되어 있는 형태로 구성됩니다. 또한, 노드(node)들로 구성되며 각 노드는 자신이 저장하고 있는 값(data)과 다음 노드를 가리키는 포인터(pointer)로 이뤄져 있습니다. 첫 번째 노드를 가리키는 포인터를 헤드(head)라고 하며, 마지막 노드를 가리키는 포인터는 NULL값으로 설정됩니다. 연결 리스트의 가장 큰 특징은 요소들이 물리적으로 연속적인 공간에 저장되지 않는다는 것입니다. 즉, 연결 리스트에서 각 요소들은 메모리상에서 임의의 위치에 저장될 수 있으며, 각 요소들은 자신의 다음 요소를 가리키는 포인터를 가지고 있습니다. 연결리스트는 다..
동적 배열(Dynamic Array)이란? 동적 배열은 배열과 유사하지만, 크기를 미리 지정하지 않고 필요에 따라 크기가 동적으로 변경되는 자료구조입니다. 이러한 동적 배열은 컴퓨터 과학에서 매우 중요한 자료구조 중 하나이며, 많은 프로그래밍 언어에서 기본적으로 제공됩니다. 동적 배열은 메모리 상에서 연속된 공간에 요소들을 저장하는 배열과 달리, 요소들이 반드시 연속된 공간에 저장되지 않습니다. 대신, 배열의 크기가 변경될 때마다 새로운 메모리 공간을 할당하고, 기존의 데이터를 새로운 공간으로 복사하는 방식을 사용합니다. 이러한 방식으로 동적 배열은 필요한 만큼의 메모리를 동적으로 할당하여, 크기를 미리 지정하지 않아도 되므로 매우 유연한 사용이 가능합니다. 동적 배열은 일반적으로 배열과 같은 인덱스 방..