하루이의 개발 노트

동적 계획법(DP)는 하나의 알고리즘이라기보다는 문제를 해결하기 위한 방법론에 가깝다. 이는 문제를 작은 하위 문제들로 나누고, 그 결과를 재사용하여 최적화하는 방식이다. 동적 계획법은 문제마다 각기 다른 점화식을 세우고, 그에 맞는 알고리즘을 스스로 만들어가야 하기 때문에, 처음에는 이 방법을 쉽게 떠올리기 어려울 수 있다.그래서, 동적 계획법의 흐름을 따라가며 개념을 이해하는 방법을 예시를 통해 정리해보고자 한다. https://developsvai5096.tistory.com/76 위의 포스트 또한 dp를 통해 점화식을 구하는 내용이 자세히 정리 되어있다. 같이 보면 도움이 되지 싶다.1. Reduction & Recursion (문제를 작은 문제로 나누기)동적 계획법은 큰 문제를 작은 문제로 나누..

배낭 문제 는 동적 계획법(DP) 문제의 대표적인 예로, 주어진 아이템을 배낭에 담아 최대 가치를 구하는 문제다. 이걸 이하는데 시간이 매우 오래 걸렸지만 아직도 dp의 접근 방식과 , 점화식을 세우는건 좀 부족하다. 그래도 이해 한 만큼 에 대해서는 정리를 해보고자 한다. 1. 문제 정의주어진 무게 제한 k가 있는 배낭에 n개의 아이템을 넣으려고 한다.각 아이템 i는 무게 v[i]와 가치 w[i]를 가지고 있다.목표는, 무게 제한을 넘지 않으면서 배낭에 담을 수 있는 아이템들의 가치 합을 최대화하는 것이다.2. 문제의 특징각 아이템은 한 번만 선택할 수 있다. 즉, 선택하거나 선택하지 않는 두 가지 선택지뿐이다. (0/1 문제)선택을 할 때, 배낭의 용량을 넘지 않도록 해야 한다.목표는 최대 가치를 얻..

트리 예시우선, 다음과 같은 간단한 이진 트리를 가정하자: 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는 시작 노드에서 인접한 노드를 먼저 방문하고, ..