민트의 공부일지

그래프 표현 방식으로서 인접행렬과 인접리스트의 근본적 개념 차이인접행렬의 정의정점 수가 V인 그래프에 대해 V × V 크기의 2차원 배열을 사용하여 정점 간의 연결 상태를 저장합니다.G[i][j]의 값은 정점 i에서 정점 j로의 간선 유무 또는 가중치를 나타냅니다.인접리스트의 정의정점마다 별도의 리스트를 만들어 각 정점에 연결된 이웃 정점들의 정보를 저장합니다.총 V개의 리스트가 존재하며, 리스트 내부에 연결된 간선만 저장합니다.메모리 사용 측면에서의 공간 복잡도 차이인접행렬의 공간 복잡도O(V²)→ 정점 쌍마다 하나의 값이 필요하므로, 간선의 수(E)와 무관하게 항상 정점 수 제곱 크기의 메모리가 필요합니다.희소 그래프에서 비효율적→ 대부분의 값이 0이지만, 그럼에도 불구하고 메모리를 차지함인접리스트의..

그래프 이론에서 인접리스트(Adjacency List)의 개념과 정의인접리스트(Adjacency List)란, 그래프의 정점 간 연결 관계를 표현하기 위한 자료구조로, 각 정점이 연결된 다른 정점들의 리스트를 개별적으로 유지하는 방식입니다.이는 희소 그래프(Sparse Graph) 즉, 간선의 수가 적은 그래프에서 특히 유리한 표현 방식으로, 메모리 공간의 효율성과 탐색 효율성을 동시에 고려한 구조입니다.인접리스트의 기본 구조 정의그래프에 정점이 V개 존재할 때, **크기가 V인 배열(또는 리스트)**을 생성합니다.각 인덱스 i는 정점 i를 의미하며, 그 위치에는 정점 i와 연결된 정점들의 리스트가 저장됩니다.예: 정점 0과 연결된 정점이 1, 3이면 → adj[0] = [1, 3]리스트의 구현 방식은 ..

그래프 이론에서 인접행렬(Adjacency Matrix)의 개념과 정의인접행렬은 그래프(Graph)의 정점(Vertex) 간 연결 관계를 2차원 배열 형태로 표현하는 방식입니다.그래프를 컴퓨터에 저장하거나 알고리즘을 적용하기 위해서는 정점 간의 간선(Edge) 정보를 구조화해야 하며, 그 대표적인 방식 중 하나가 인접행렬입니다.인접행렬의 기본 정의V개의 정점을 가진 그래프에 대해, **V x V 크기의 2차원 배열(matrix)**을 생성합니다.행과 열은 각각 그래프의 정점을 의미하며, 행 i, 열 j에 저장된 값은 정점 i에서 정점 j로의 간선 존재 여부나 가중치를 나타냅니다.G[i][j] = 1 → 정점 i와 정점 j가 연결되어 있음 (무가중치 그래프 기준)G[i][j] = w → 연결..

이진 탐색 트리의 정의 및 구조적 원리 설명이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 특수한 형태로, 각 노드가 정렬된 방식으로 데이터를 저장하는 구조입니다. BST는 다음과 같은 조건을 만족합니다:각 노드는 최대 두 개의 자식 노드를 가짐 (이진 트리 조건)왼쪽 서브트리의 모든 노드 값 오른쪽 서브트리의 모든 노드 값 > 현재 노드의 값이 속성은 모든 서브트리에 재귀적으로 적용됨이러한 구조적 원리를 통해 BST는 효율적인 검색, 삽입, 삭제 연산을 지원합니다.이진 탐색 트리의 삽입, 탐색, 삭제 알고리즘 설명삽입(Insert) 연산의 작동 방식루트 노드부터 시작하여 삽입할 값을 비교합니다.삽입할 값이 현재 노드보다 작으면 왼쪽 자식으로 이동합니다.크면 오른쪽 자식으로 이..

이진 트리(Binary Tree)의 정의와 기본 구성 설명이진 트리는 트리(Tree) 자료구조의 한 종류로, 각 노드가 최대 두 개의 자식 노드를 갖는 트리입니다. 이진 트리는 다음과 같은 기본 조건을 만족합니다:각 노드는 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)을 가질 수 있습니다.자식 노드의 개수는 0개, 1개, 또는 2개입니다.이진 트리는 매우 간결하면서도 강력한 자료구조로, 다양한 트리 기반 알고리즘과 응용 분야의 기반이 됩니다.이진 트리의 용어 및 구조적 관계 설명이진 트리를 이해하기 위해 반드시 숙지해야 하는 용어와 구조는 다음과 같습니다:루트 노드(Root Node): 트리의 시작 노드로, 부모가 없는 유일한 노드입니다.자식 노드(Child Node): 루트나 다..

트리(Tree)의 정의와 기본 구조 설명트리(Tree)는 비선형 계층적 자료구조로, 노드(Node)들이 부모-자식 관계를 이루며 연결된 구조입니다. 이 구조는 **사이클이 없는 연결 그래프(Connected Acyclic Graph)**의 한 종류로 간주되며, 노드들 간의 계층적 관계 표현에 매우 적합합니다.트리는 다음과 같은 조건을 만족합니다:하나의 루트 노드(Root Node)가 존재하며, 트리 전체의 시작점입니다.각 노드는 0개 이상의 자식 노드(Child Node)를 가집니다.사이클이 존재하지 않음 (비순환성)두 노드 간에는 단 하나의 경로만 존재함 (유일성)트리는 재귀적인 구조를 가지며, 서브트리(Subtree)는 자신 또한 트리의 구조를 가집니다.노드(Node)의 구성 요소 및 관계 설명트리에..