본문 바로가기

자료구조

[자료구조] 트리(Tree)의 개념과 종류
[자료구조] 트리(Tree)의 개념과 종류 2024. 3. 29. ❓ 트리(Tree)란? 트리(Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다. 트리는 나무를 거꾸로 뒤집어 놓은 모양과 유사합니다. 또한 트리 내에 다른 하위 트리가 있고, 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 합니다. 트리의 대표적인 예시로는 컴퓨터의 directory구조가 있습니다. 📌 트리 구조에서 사용되는 기본 용어 명칭 설명 노드(node) 트리에서 데이터를 저장하는 기본적인 단위 그래프의 정점 루트 노드(root node) 부모가 없는 노드, 트리 구조에서 최상위에 존재하는 A와 같은 노드 내부 노드(internal node) 단말 노드가 아닌 노드 단말 노드(leaf node) 자식이 없는 노드, (말단 노드, 잎 노드 라고도 부름) 밑..
[자료구조] 그래프(Graph)의 탐색 및 구현
[자료구조] 그래프(Graph)의 탐색 및 구현 2024. 3. 29. 📌 그래프(Graph)의 탐색 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적입니다. 원하는 값만 한 번에 찾고 싶지만 그래프의 데이터는 배열처럼 정렬이 되어 있지 않기 때문에, 원하는 자료를 찾으려면 하나씩 모두 방문하여 찾아야 합니다. 그래프의 탐색에는 크게 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)이 있습니다. 1. 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것..
[자료구조] 그래프(Graph)의 개념
[자료구조] 그래프(Graph)의 개념 2024. 3. 29. ❓ 그래프(Graph)란? 그래프(Graph)란 연결되어 있는 원소 간의 관계를 표현한 자료구조를 말합니다. 일상에서는 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수과목 등을 예시로 들 수 있습니다. 그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraph)로 구성될 수 있습니다. 그래프는 연결할 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합으로 구성됩니다. 그래프 G를 G=(V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미합니다. 📌 그래프의 종류 무방향 그래프(Undirected Graph) 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프입니다. 무방향 그래프에서 정점 Vi왕..
[자료구조] 스택(Stack)과 큐(Queue)
[자료구조] 스택(Stack)과 큐(Queue) 2024. 3. 27. ❓ 스택(Stack)이란? 스택(Stack)은 "쌓다"라는 의미로 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다. 덧붙여 설명하자면 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조(LIFO)를 가지고 있습니다. 스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있습니다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능합니다. ⛏️ 스택의 작동 원리 스택(Stack)은 기본적으로 후입선출(나중에 들어온 데이터가 가장 먼저 나가는)인 LIFO(Last-In-First-Out)구조로 이루어져 있습니다. ✅ 스택 제공 연산 종류 pop( ): 스택에서 가장 위에 있는 항목을 제..
[자료구조] 자료구조의 종류와 분류
[자료구조] 자료구조의 종류와 분류 2024. 3. 27. 💾 자료구조의 종류와 분류 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, 자료구조라는 이름을 붙였습니다. 👉 자주 등장하는 네 가지의 자료구조 Stack, Queue, Tree, Graph
[자료구조] 자료구조란
[자료구조] 자료구조란 2024. 3. 27. ❓ 자료구조(Data Structure)란? 자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다. 개발 과정에서 데이터를 가지고 전처리 하는 방식들, 기능(함수)를 구현하는 것들 모두 자료구조라고 할 수 있습니다. 그러나 그 방법들 중에서도 효율적인 방식이 존재하는데 그것들을 정의한 것이 자료구조입니다. 사전적 의미로는 자료(Data)의 집합을 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이라고 합니다. ❓ 왜 필요한가? 그렇다면 자료구조는 왜 필요한 것일까요? 그 이유로는 자료구조를 익힘으로서 효율적으로 데이터를 다루어 문제를 해결하기 위함이 1순위일 것입니다. 잘 선택된 자료구조는 실행..

티스토리툴바