이 글에서는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 대표적인 알고리즘인 크루스칼 알고리즘과 프림 알고리즘에 대해 정리하였습니다.최소 신장 트리(Minimum Spanning Tree, MST)MST의 개념가중치가 있는 무방향 그래프에서, 모든 정점을 연결하면서 그 간선들의 가중치 합이 최소가 되는 서브그래프를 의미조건 : 모든 정점을 포함 + 사이클이 없는 트리 구조 + 간선 가중치의 합이 최소MST를 구하는 대표 알고리즘크루스칼(Kruskal) 알고리즘간선을 가중치 오름차순으로 정렬한 뒤, 가장 작은 것부터 하나씩 트리에 포함시킬지 결정이미 사이클이 형성되는 간선은 버리고, 아니면 포함사이클 판별을 빠르게 하기 위해 Union Find(서로소 집합, DSU)를 사용U..

이 글은 서로소 집합 자료구조(Disjoint Set Union, DSU)에 대해서 정리한 글입니다.DSU와 Union Find✅ "Union Find"라는 이름은 합치기를 뜻하는 Union과 찾기를 뜻하는 Find라는 두 가지의 주요 연산에서 유래한 표현으로 서로소 집합 자료구조(Disjoint Set Union, DSU)과 동일한 자료구조를 의미✅ DSU는 "서로소(disjoint)인 여러 집합을 관리하고, 필요할 때 이 집합들을 합쳐(Union)주면서 집합의 대표나 구조를 빠르게 찾는(Find) 기법"을 의미하는 더 일반적이며 학술적인 표현 Union Find랑 DSU는 동일한 자료구조를 나타내는 용어이며, 이 글에서 사용하는 Union Find와 DSU는 동일한 개념으로 이해하면 됩니다.DSU(D..

2025년 1월과 2월은 정말 많은 부분이 바뀐 시기라 생각된다. 이전까지 하던 일들을 마무리하며 동시에 새로운 일들이 시작되었고, 또 한편으로는 가장 빠르게 성장한 시기이기도 했다.나는 재미로 매달 사주풀이를 받아보고 있는데 1월과 2월는 비슷하게 흘러간 것 같다.사실 다른 키워드는 잘 모르겠고, 1월의 "신뢰와 책임으로 만드는 새로운 기회"과 2월의 "자기 관리와 휴식, 그리고 작은 목표와 추천 방향성"의 키워드는 잘 맞아 떨어진 것 같다. (사실 1월의 신뢰와 책임은 모르겠고... 그냥 새로운 기회였다ㅎㅎ) 일단 1월에는 학사 4년과 석사 2년을 모두 마치며 총 8년(2년 군대 포함) 동안 다니던 학교를 떠나게 되었다. 연구실에 마지막 출근을 하고 나올 땐 아무 느낌이 들지 않았지만 (뭔가 다시 내..

이 글은 BFS 알고리즘을 활용하여 최단 경로를 탐색하는 플러드 필(Flood Fill)과 다익스트라(Dijkstra) 알고리즘에 대해 정리한 글입니다.플러드 필 (Flood Fill)플러드 필의 개념정의플러드 필은 시작 지점에서부터 같은 값(색, 타입 등)을 가지며 연결되어 있는 모든 칸을 탐색(방문)하고, 그 칸들에 대해 특정 작업(색, 값 갱신, 카운트 등)을 수행하는 알고리즘연결 기준2D 격자에서 일반적으로 상, 하, 좌, 우의 4방향(4-connected)을 인접한 영역으로 취급문제에 따라서, 대각선 4방향을 포함하여 8방향(8-connected)을 인접한 영역으로 취급하기도 함주요 특징탐색은 같은 값, 혹은 특정 조건을 만족하는 값을 대상으로 수행탐색된 영역에 대해 일괄적으로 처리방문 체크(v..

이 글은 알고리즘을 설계할 때 많이 사용되는 대표적인 자료구조 중 하나인 스택(Stack)과 큐(Queue)에 대해 정리한 글입니다.스택 (Stack)스택의 개념스택은 데이터를 임시 저장하는 데 사용하는 자료구조후입선출, LIFO (Last-In, First-Out) : 가장 나중에 들어간 데이터가 가장 먼저 나오며, 물리적인 동작으로는 한쪽 끝에서만 데이터를 넣거나 뺼 수 있는 구조스택의 주요 연산스택의 기본 연산은 언어에 상관없이 동일하나, 구현 방법이나 문법은 언어 별로 차이가 있을 수 있다.Push새로운 데이터를 스택의 맨 위(top)에 삽입ex) push(item)Pop스택의 맨 위에 있는 데이터를 제거하고 반환스택이 비어 있는 상태에서 pop을 시도하면 에러(underflow)가 발생ex) i..

이 글은 가장 대표적인 그래프 탐색 방법인 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)에 대해 정리한 글입니다.깊이 우선 탐색 (DFS)깊이 우선 탐색(DFS, Depth First Search)은 그래프 탐색 알고리즘 중에서도 가장 기초적이고 중요한 알고리즘 중 하나로, 트리 구조 및 다양한 그래프 문제에서 폭넓게 활용된다.DFS의 개념정의DFS는 시작 정점에서부터 한 경로로 깊숙이 들어가며 탐색을 진행하다가, 더 이상 진행이 불가능해지면 바로 앞 단계로 되돌아와 다른 경로를 탐색하는 방식재귀 또는 스택을 사용하여 구현특징그래프에서 한 정점에서 출발하면, 가능한 멀리까지(깊이) 진행탐색 과정에서 한 번 방문한 정점은 보통 다시 방문하지 않도록 방문 배열(visited) 등을 사용트리 구조(사이클..

이 글은 재귀(recursion)와 백트래킹(backtracking)에 대해 정리한 글입니다.재귀 함수 (Recursion Function)재귀 함수는 복잡한 문제를 단순화해서 생각할 때 유용하며, 특히 분할 정복, 트리/그래프 탐색(DFS). 백트래킹 등 다양한 알고리즘 설계 기법에서 매우 중요한 역할을 한다. 직관적으로 이해하기에는 어려움이 있으나, 디버깅을 통해 재귀 함수가 동작하는 과정을 이해하면 알고리즘 설계에 있어서 도움이 된다재귀란?정의어떤 함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법을 의미문제를 풀기 위해 문제의 부분 문제를 재귀적으로 해결하고, 그 해를 이용하여 전체 문제의 해를 구하는 구조를 가짐재귀의 기본 구조재귀 함수를 작성할 때에는 기저 조건(base case..

https://www.acmicpc.net/problem/11723문제비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)all: S를 {1, 2, ..., 20} 으로 바꾼다.empty: S를 공집합으로 바꾼다.입력첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 ..

많은 탐색 알고리즘 중 기본이라고 할 수 있는 선형 탐색, 이진 탐색, 그리고 해시를 활용한 탐색에 대해 정리한 글입니다.탐색의 기본 개념정의주어진 데이터 구조 안에서 특정 값(key) 또는 조건을 만족하는 데이터를 찾아내는 과정목표해당 값이 존재하는지 확인 (존재 여부)존재한다면 그 위치(인덱스, 노드 포인터 등)를 반환 (위치 정보)존재하지 않는다면 탐색 실패 처리성능 척도시간 복잡도 : 탐색에 걸리는 평균 / 최악 / 최선 연산 횟수 확인공간 복잡도 : 추가 메모리 사용량 (보조 자료구조가 필요 여부 등)구현 난이도 : 자료 구조의 복잡도 & 코드 구현의 편리성분류배열 기반 탐색 : 선형 탐색, 이진 탐색 등연결 리스트 기반 탐색트리 기반 탐색 : 이진 검색 트리, 트리 순회, 자가 균형 트리 등그..

정렬 알고리즘에 대해 정리한 글입니다. 정렬 알고리즘의 전반적인 내용과 대표적인 기본 정렬 알고리즘인 버블 정렬, 선택 정렬, 삽입 정렬, 그리고 카운팅 정렬에 대해 정리하였습니다.(병합 정렬, 퀵 정렬, 힙 정렬 등의 알고리즘은 추후 정리할 예정입니다.)정렬 (Sorting)정렬(Sorting)은 주어진 데이터를 특정 기준(ex. 오름차순, 내림차순 등)에 맞춰 순서대로 재배열하는 과정오름차순 정렬 : 작은 값부터 큰 값 순서로 정렬내림차순 정렬 : 큰 값부터 작은 값 순서로 정렬가장 기초적이면서도 광범위하게 사용되는 알고리즘으로, 데이터 검색과 데이터 관료 효율을 높이는데 필수적이며, 여러 문제 해결에서도 자주 활용정렬 알고리즘 평가 기준시간 복잡도 (Time Complexity)주어진 N개의 데이터..