하루이의 개발 노트

트리 예시우선, 다음과 같은 간단한 이진 트리를 가정하자: 1 / \ 2 3 / \ 4 5위의 트리에서 노드 1이 루트 노드이고, 2와 3이 각각 루트의 왼쪽과 오른쪽 자식 노드이며, 4와 5는 2의 자식 노드다.1. 전위 순회 (Preorder Traversal)전위 순회에서는 루트 -> 왼쪽 -> 오른쪽 순으로 노드를 방문한다.1. 루트(1)를 먼저 방문2. 왼쪽 서브트리로 이동하여 2를 방문3. 다시 왼쪽 서브트리로 이동하여 4를 방문4. 4의 부모 노드인 2로 돌아가 오른쪽 자식인 5를 방문5. 루트 노드의 오른쪽 서브트리로 이동하여 3을 방문방문 순서: 1 → 2 → 4 → 5 → 32. 중위 순회 (Inorder Traversal)중위 순회에서는 왼쪽 -> 루..

Union-Find 자료 구조는 Disjoint Set(서로소 집합)이라고도 불리며, 집합 간의 합집합(Union)과 특정 원소가 속한 집합을 찾는(Find) 연산을 효과적으로 수행하기 위한 자료 구조다. 이 자료 구조는 주로 그래프 알고리즘에서 사이클을 판별하거나, 서로 연결된 컴포넌트를 찾는 데 사용된다.기본 개념집합(sets): 각 원소는 하나의 집합에 속하며, 처음에는 모든 원소가 자신만을 포함하는 집합에 속하게 된다.합집합(Union): 두 집합을 하나의 집합으로 합친다.찾기(Find): 특정 원소가 속한 집합의 대표 원소(루트)를 찾는다.주요 연산Union-Find 자료 구조는 두 가지 기본 연산을 제공한다:Find(x):원소 x가 속한 집합의 루트(대표 원소)를 찾는다.경로 압축(Path C..

위상 정렬(Topological Sorting)의 개념위상 정렬은 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서 노드들을 선후 관계에 따라 순서대로 나열하는 것이다. 여기서 선후 관계란 그래프의 방향을 나타내는 간선(Edge)에 의해 결정되는 노드 간의 의존성을 의미한다. 위상 정렬의 목적은 이 의존성을 지키면서 모든 노드를 나열하는 것이다.위상 정렬의 기본 개념방향 그래프(Directed Graph):그래프의 각 간선이 방향을 가지며, 이는 한 노드에서 다른 노드로의 일방향성 연결을 의미한다.예를 들어, 작업 A가 끝나야 작업 B를 시작할 수 있다면, 이는 A에서 B로 향하는 방향 간선으로 표현된다.사이클이 없는 그래프(Acyclic Graph):그래프에 사이클(Cy..

다익스트라 알고리즘이란?다익스트라 알고리즘(Dijkstra's algorithm)은 그래프에서 단일 출발점에서 모든 다른 노드로의 최단 경로를 찾는 알고리즘이다. 가중치가 있는 그래프에서 가중치가 양수일 때 사용할 수 있으며, 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 1956년에 고안한 알고리즘이다.다익스트라 알고리즘의 동작 원리초기화:시작 노드를 선택하고, 시작 노드에서 다른 모든 노드까지의 거리를 무한대(∞)로 초기화한다.시작 노드의 거리는 0으로 설정한다.아직 방문하지 않은 모든 노드를 포함하는 집합(보통 우선순위 큐를 사용)에 시작 노드를 추가한다.반복:큐에서 가장 작은 거리를 가진 노드를 꺼낸다. 이 노드를 현재 노드로 설정한다.현재 노드의 인접 노드들을..

다익스트라 알고리즘을 공부 하면서 풀어볼수 있는 문제를 찾다가 미로만들기 문제를 풀어보았는데 다익스트라가 어떤 알고리즘 인지 보여주는데 적합한 문제인것 같아 정리 해보았다.문제 개요"미로 만들기" 문제(백준 문제 번호: 2665)는 흑백 미로에서 최소한의 방을 바꾸어 시작점에서 도착점까지 도달하는 최단 경로를 찾는 문제이다.문제 설명미로는 NxN 크기의 정사각형으로, 각 칸은 흰 방(0) 또는 검은 방(1)으로 이루어져 있다.흰 방(0)은 그대로 지나갈 수 있지만, 검은 방(1)은 흰 방으로 바꾸어야만 지나갈 수 있다.목표는 시작점 (0, 0)에서 도착점 (N-1, N-1)까지 도달하는데 필요한 최소한의 검은 방 변환 횟수를 구하는 것이다.다익스트라 알고리즘을 사용한 접근그래프 모델링각 방을 그래프의 ..

DFS(Depth-First Search, 깊이 우선 탐색)는 그래프나 트리 구조에서 노드를 탐색하거나 순회하는 알고리즘 중 하나다. 이 알고리즘은 가능한 한 깊이(즉, 자식 노드)를 먼저 탐색하는 것을 목표로 한다. DFS는 스택 자료구조를 사용하여 구현할 수 있으며, 재귀적으로도 쉽게 구현할 수 있다.1. DFS의 기본 원리DFS는 시작 노드에서 시작하여 다음 노드를 방문할 때마다 깊이(자식 노드)로 최대한 내려간다. 더 이상 내려갈 수 없는 노드에 도달하면, 직전에 방문한 노드로 돌아와서 탐색하지 않은 다른 자식 노드를 탐색한다. 이 과정은 모든 노드를 방문할 때까지 계속된다.2. DFS 구현 방법DFS는 재귀 방식과 비재귀(반복문과 스택 사용) 방식으로 구현할 수 있다.3. DFS의 특징완전 탐색..

1197 번 문제는 MST(최소 스패닝 트리)를 구현하는 문제이다. MST를 구현하는 방법에서는 크루스칼 알고리즘,프림 알고리즘 두가지가 존재하는데 프림은 잘 사용 되지는 알고리즘이다. 따라서 이번 문제에서는 크루스칼을 이용해 풀어보자 크루스칼(Kruskal) 알고리즘은 가중치가 있는 연결 그래프에서 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 중 하나다. 이 알고리즘은 그리디 알고리즘의 한 종류로, 간선의 가중치가 작은 것부터 차례대로 선택하여 MST를 구성하는 방법을 사용한다.1. 기본 개념그래프: 정점(Vertex)과 간선(Edge)으로 이루어진 구조.신장 트리: 그래프의 모든 정점을 포함하며, 사이클이 없는 트리.최소 신장 트리(MST): 그래프에서 모든 ..

2주차 에 접어들며 bfs 문제를 풀고 있다. 그중 미로 탐색 문제에 대한 정리 이다.1. 문제 이해목표: N×M 크기의 미로에서 시작점 (1, 1)에서 출발하여 도착점 (N, M)으로 이동하는 최단 경로를 찾는 것.제약 조건:미로는 1과 0으로 구성되며, 1은 이동 가능한 경로, 0은 벽을 의미한다.서로 인접한 칸으로만 이동할 수 있다.항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.출력: 시작점에서 도착점까지 이동하기 위해 지나야 하는 최소 칸 수.2. 접근법이 문제는 BFS(너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있다. BFS는 탐색 과정에서 가장 가까운 노드부터 탐색하므로, 최단 경로를 찾는 데 적합하다.BFS의 기본 개념:BFS는 시작 노드에서 인접한 노드를 먼저 방문하고, ..

BFS(Breadth-First Search, 너비 우선 탐색)는 그래프 또는 트리를 탐색하는 알고리즘 중 하나로, 가까운 노드부터 탐색을 진행하는 방식이다.BFS의 기본 개념탐색 순서: BFS는 시작 정점에서부터 시작하여 인접한 모든 정점을 먼저 탐색한 후, 그다음으로 가까운 정점들로 확장해 나가는 방식이다. 이 과정을 반복하며 그래프를 탐색해 나간다.큐(Queue)를 이용한 구현: BFS는 큐(Queue) 자료구조를 사용해 구현한다. 큐는 FIFO(First In, First Out) 원칙에 따라 먼저 들어온 요소가 먼저 나가는 구조다. BFS는 정점을 탐색할 때 큐에 넣고, 큐에서 꺼내면서 그 정점의 인접한 정점을 다시 큐에 넣는 과정을 반복한다.방문 여부 체크: BFS는 같은 정점을 여러 번 방문..

그래프(데이터 구조에서의 그래프)는 노드(정점)와 엣지(간선)로 이루어진 비선형 자료구조로, 다양한 문제를 해결하는 데 사용된다. 그래프는 서로 연결된 데이터 간의 관계를 표현하기에 유용하다. 이를 통해 다양한 알고리즘이 적용될 수 있으며, 특히 네트워크, 소셜 미디어 분석, 경로 탐색 등에서 자주 사용된다.1. 그래프의 기본 요소노드(Node, 정점): 데이터 포인트를 의미한다. 그래프에서는 보통 원으로 표시되며, 각 노드는 고유한 값을 가진다.엣지(Edge, 간선): 노드 간의 연결을 의미한다. 두 노드 사이의 관계를 나타내며, 방향성 여부에 따라 유향 그래프와 무향 그래프로 나뉜다.2. 그래프의 종류1. 무향 그래프(Undirected Graph)예시: 노드 A와 노드 B가 있고, 이 둘을 연결하는..