JUNOTE

그래프를 구현하는 방법은 크개 두 가지가 있다. 인접 행렬을 이용하거나 인접 리스트를 이용하는 방법을 주로 사용한다. 그래프에 대한 자세한 내용은 전 포스팅을 참고하기 바란다.2024.06.26 - [CS/자료구조] - [자료구조] 그래프 (Graph) [자료구조] 그래프 (Graph)그래프란?그래프는 정점(vertex: V)과 정점들을 연결하는 간선(edge: E)으로 구성된 자료구조이다. 예를 들어 지하철 노선도를 그래프라고 할 수 있다.그래프는 트리와는 달리 순환이 발생해도 된다.junote.tistory.com 인접 리스트를 이용한 방법 (JAVA)import java.util.LinkedList;import java.util.List;public class Vertex { String la..

그래프란?그래프는 정점(vertex: V)과 정점들을 연결하는 간선(edge: E)으로 구성된 자료구조이다. 예를 들어 지하철 노선도를 그래프라고 할 수 있다.그래프는 트리와는 달리 순환이 발생해도 된다. 순환이 발생하지 않는 무방향 연결 그래프를 트리라고 할 수 있다. 트리도 그래프의 한 종류인 것이다.  그래프 용어 정의노드 또는 정점 (Node or Vertex): 그래프의 기본 단위로 각 노드는 데이터를 포함할 수 있다.간선 또는 변 (Edge): 두 노드를 연결하며 방향이 있을 수도 있고 없을 수도 있다.정점의 차수 (Degree): 하나의 정점에 근접하는 변의 개수를 말한다. 모든 정점의 차수의 합은 변의 개수의 2배이다. 그리고 그래프에서 차수가 홀수인 정점의 개수는 짝수이다.내차수 또는 진..

트리는 주로 계 층적 구조를 표현하는 데 사용하는 자료구조로 노드들로 구성되어 있다. 트리에 대한 자세한 내용은 전 포스팅을 참고하기 바란다.2024.06.22 - [CS/자료구조] - [자료구조] 트리 (Tree)2024.06.23 - [CS/자료구조] - [자료구조] 이진 트리 (Binary Tree) 이진 탐색 트리 구현간단한 이진 탐색 트리를 만들고 전위, 중위, 후위 및 레벨 순회를 실행해 보는 코드를 구현해 보도록 하겠다.public class Node { Object data; Node left; Node right; Node(Object data) { this.data = data; this.left = null; this.righ..

이진 트리란?이진 트리는 트리의 한 종류로 각 노드가 최대 두 개의 자식 노드를 가지는 트리이다. 이진 트리는 구조에 따라 다양한 종류로 나뉘게 된다. 기본적인 트리에 대한 설명은 전 포스팅을 참고하기 바란다.2024.06.22 - [CS/자료구조] - [자료구조] 트리 (Tree) [자료구조] 트리 (Tree)트리란?트리는 노드들로 구성된 자료구조로, 주로 계층적 구조를 표현하는 데 사용한다. 노드들간에 부모-자식 관계를 통해 트리를 구성한다.위 그림에서 선으로 연결된 관계를 부모-자식 관계junote.tistory.com 이진 트리의 종류완전 이진 트리 (Complete Binary Tree): 트리의 마지막을 제외한 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워져 있는 트리이다.정 이진 트리 ..

트리란?트리는 노드들로 구성된 자료구조로, 주로 계층적 구조를 표현하는 데 사용한다. 노드들간에 부모-자식 관계를 통해 트리를 구성한다.위 그림에서 선으로 연결된 관계를 부모-자식 관계라고 부른다. 트리 용어 정의노드 (Node): 정보 항목과 다른 노드로의 가지(branch)로 구성된다.루트 노드 (Root Node): 트리의 최상위 노드이며, 트리는 단 하나의 루트 노드만을 가질 수 있다.부모 노드 (Parent Node): 특정 노드의 상위 노드를 말한다.자식 노드 (Child Node): 특정 노드의 하위 노드를 말한다.형제 노드 (Sibling Node): 동일한 부모 노드를 가지는 노드들을 말한다.잎 노드 | 말단 노드 (Leaf Node | Terminal Node): 자식 노드가 없는 노드..

연결 리스트는 데이터와 포인터로 구성된 노드들의 집합이다. 연결 리스트에 대한 자세한 내용은 전 포스팅을 참고하기 바란다.2024.06.18 - [CS/자료구조] - [자료구조] 연결 리스트 (Linked-List) [자료구조] 연결 리스트 (Linked-List)연결 리스트란?연결 리스트는 노드들로 구성되어 있다. 위 그림에서 각각의 큰 직사각형들이 하나의 노드이다. 노드는 데이터 영역과 링크(포인터) 영역으로 구성되어 있다. 데이터 영역은 데이junote.tistory.com 단일 연결 리스트 구현단일 연결 리스트의  각 노드는 다음 노드를 가리키는 하나의 포인터를 가지며 마지막 노드의 포인터는 null이다.public class Node { Object data; Node next; ..

연결 리스트란?연결 리스트는 노드들로 구성되어 있다. 위 그림에서 각각의 큰 직사각형들이 하나의 노드이다. 노드는 데이터 영역과 링크(포인터) 영역으로 구성되어 있다. 데이터 영역은 데이터를 저장하는 공간이고 링크 영역은 다음 노드를 가리키는 역할을 한다. 연결 리스트의 특징연결리스트의 가장 큰 특징은 데이터를 삽입/삭제할 때, 노드를 추가/삭제하면 되므로 미리 크기를 정의하지 않아도 된다는 것이다. 연결리스트는 필요에 따라 크기를 동적으로 조절할 수 있다. 연결리스트의 다른 특징은 다음과 같다.삽입 및 삭제의 효율성: 데이터의 삭제와 삽입 모두 삽입하는 위치의 전 노드의 포인터 또는 삽입하는 노드의 포인터를 조정하기만 하면 된다. 따라서 시간복잡도는 O(1)로 효율적이다.임의 접근(random acce..

큐란 선입선출(FIFO) 구조를 갖는 자료구조이다. 큐에 대한 자세한 설명은 전 포스팅을 참고하기 바란다.2024.06.15 - [CS/자료구조] - [자료구조] 큐 (Queue) [자료구조] 큐 (Queue)큐란?큐는 스택과 마찬가지로 컴퓨터에 있어서 중요한 자료구조 중 하나이다.큐는 후입선출(LIFO)인 스택과 달리 선입선출(First-In First-Out: FIFO) 구조를 갖는 자료구조이다. 스택에서는 접시 더미junote.tistory.com 큐 구현 방법큐를 구현하는 것은 크게 두 가지 방법이 있다.배열(Array) 기반 큐: 고정 크기의 배열을 사용하여 큐를 구현한다. 간단하지만 큐의 크기가 고정되어 있다는 단점이 있는 방법이다.연결 리스트(Linked-List) 기반 큐: 동적으로 크기를..

스택이란 후입선출(LIFO) 구조를 갖는 자료구조이다. 스택에 대한 자세한 설명은 전 포스팅을 참고하기 바란다.2024.06.15 - [CS/자료구조] - [자료구조] 스택 (Stack) [자료구조] 스택 (Stack)스택이란?스택은 컴퓨터에서 매우 자주 사용되는 자료구조이기 때문에 굉장히 중요한 자료구조이다.Stack이라는 단어를 단어사전에 검색하면 "무더기(더미)"라는 결과를 얻을 수 있다. 스택은 말junote.tistory.com 스택 구현 방법스택을 구현하는 방법에는 크게 2가지 방법이 있다.배열(Array) 기반 스택: 고정 크기의 배열을 사용하여 스택을 구현한다. 배열의 크기를 초과하면 새로운 배열을 할당해야 한다.연결 리스트(Linked-List) 기반 스택: 동적 크기의 연결 리스트를 사..

큐란?큐는 스택과 마찬가지로 컴퓨터에 있어서 중요한 자료구조 중 하나이다.큐는 후입선출(LIFO)인 스택과 달리 선입선출(First-In First-Out: FIFO) 구조를 갖는 자료구조이다. 스택에서는 접시 더미를 예로 들었다면 큐에서는 음식점 대기줄을 예로 들 수 있다. 음식점의 대기줄에서는 먼저 온 사람이 먼저 식당에 들어갈 수 있다.큐는 선입선출 구조이므로 먼저 들어온 데이터가 먼저 나간다. 큐의 연산큐의 주요 연산은 다음과 같다.Enqueue(): 큐의 끝에 새로운 요소를 추가(삽입)Dequeue(): 큐의 앞에서 요소를 제거(제거)front(): 큐의 맨 앞에 있는 요소를 제거하지 않고 반환rear(): 큐의 맨 뒤에 있는 요소를 제거하지 않고 반환 큐의 구현과 예시 (JAVA)큐를 구현하는..