이분 매칭(Bipartite Matching)이란?이분 매칭은 그래프에서 간선들의 집합을 선택하되, 그 집합 안의 어떤 두 간선도 같은 정점(끝점)을 공유하지 않도록 하는 방식입니다. 여기서 최대 매칭(Maximum Matching)은 이러한 조건을 만족하면서 가장 많은 수의 간선을 선택하는 매칭을 의미합니다.최대 매칭을 찾으면 더 이상 새로운 간선을 추가할 수 없습니다. 만약 최대 매칭이 된 그래프에 간선을 하나 추가하면, 두 간선이 같은 정점을 공유하게 되어 더 이상 유효한 매칭이 아니기 때문입니다. 한 가지 흥미로운 점은, 하

문제 개요이 문제에서는 2차원 평면 위에 n개의 점이 주어집니다. 우리가 구해야 할 것은 이 점들 중 서로 간의 거리가 가장 짧은 점 쌍(pair)입니다.이 문제를 효율적으로 해결하려면 먼저 점들을 두 개의 절반으로 나눈 뒤, 각 영역 안에서 최소 거리를 재귀적으로 계산합니다. 이어서 중앙선을 기준으로 일정 거리 이내에 있는 점들을 스트립(strip) 형태로 모아, 스트립 배열 안에서도 최소 거리를 다시 확인합니다. 알고리즘 시작 시 두 개의 리스트를 준비하는데, 하나는 x좌표 기준으로 정렬된 점 목록이고, 다른 하나는 y좌표 기준

피크(peak) 요소란 어떤 항목이 자신의 상하좌우 네 방향 이웃 요소 모두보다 크거나 같은 값을 가질 때를 말합니다. 이웃 요소는 위, 아래, 왼쪽, 오른쪽에 위치한 요소들을 의미하며, 대각선 방향의 요소는 이웃으로 간주하지 않습니다. 하나의 행렬에는 두 개 이상의 피크 요소가 존재할 수 있으며, 피크 요소가 반드시 행렬 전체에서 가장 큰 값일 필요는 없다는 점에 유의해야 합니다.입력 및 출력입력: 서로 다른 숫자로 구성된 행렬. 10 8 10 10 14 13 12 11 15 9 11 11 15 9 11 21

배열의 역전(inversion)은 배열을 정렬된 상태로 만들 때 필요한 변경(교환) 횟수를 나타내는 지표입니다. 배열이 이미 정렬되어 있다면 역전 개수는 0이며, 반대로 배열이 완전히 역순으로 되어 있을 때 역전 개수는 최대가 됩니다.이 문제는 단순히 모든 쌍을 비교하는 O(n²) 방식 대신, 병합 정렬(Merge Sort)을 활용한 분할 정복(Divide and Conquer) 기법으로 접근하면 O(n log n)의 시간 복잡도로 훨씬 효율적으로 해결할 수 있습니다.역전(Inversion)이란?역전은 배열에서 앞선 위치의 원소가

중앙값(median)은 자료를 크기순으로 정렬했을 때 정확히 가운데에 위치하는 값을 의미합니다. 즉, 전체 데이터의 누적 백분율 50% 지점에 해당하는 관측치라고 할 수 있습니다.이 알고리즘은 두 배열의 크기가 같다(n1 = n2)는 전제 조건을 필요로 합니다. 기본 아이디어는 각 배열의 중앙값을 먼저 구한 뒤, 두 중앙값을 서로 비교하면서 탐색 범위를 절반씩 줄여 나가 최종적으로 두 리스트 전체의 실제 중앙값을 찾는 것입니다.입력 및 출력입력:크기가 같은 정렬된 두 배열이 주어집니다.배열 1: {1, 2, 3, 6, 7}배열 2:

이중 연결 그래프(Biconnected Graph)의 정의이중 연결 그래프(Biconnected Graph)란 무방향 그래프에서 임의의 두 정점 사이에 정점을 공유하지 않는 서로 다른 두 개의 경로가 존재하는 그래프를 말합니다. 다르게 표현하면, 그래프 내의 어떤 두 정점을 골라도 반드시 하나 이상의 사이클(cycle)이 존재한다는 의미입니다.좀 더 실용적인 관점에서 보면, 그래프 G가 다음 두 조건을 만족할 때 이중 연결 그래프라고 할 수 있습니다.그래프가 연결 그래프(connected graph)일 것그래프에 단절점(articu

너비 우선 탐색(Breadth First Search, BFS)은 주어진 그래프의 모든 노드를 방문하기 위해 사용되는 대표적인 그래프 순회 알고리즘입니다. BFS는 시작 노드 하나를 선택한 뒤, 해당 노드에 인접한 모든 노드를 차례대로 방문하는 방식으로 동작합니다. 인접한 정점들을 모두 처리하고 나면, 다음 정점으로 이동하여 그 정점의 인접 정점들을 다시 확인합니다.BFS의 핵심 원리BFS를 구현하려면 큐(Queue) 자료구조가 반드시 필요합니다. 현재 정점에 인접한 모든 정점을 큐에 추가하고, 인접 정점 처리가 끝나면 큐에서 하나

브리지(Bridge)란 무엇인가? 무방향 그래프(undirected graph)에서 브리지(bridge, 다리)는 해당 간선을 제거했을 때 그래프의 연결이 끊어지거나, 하나의 그래프가 서로 다른 컴포넌트(component)로 분리되는 간선을 의미합니다. 실제 네트워크 관점에서 생각해 보면, 네트워크에 브리지 역할을 하는 연결이 존재하고 그 연결이 끊어진다면 전체 네트워크가 마비될 수 있습니다. 따라서 네트워크의 안정성을 평가하거나 취약한 병목 지점을 찾을 때 브리지를 식별하는 작업이 매우 중요합니다. 입력과 출력 입력: 그래프의

이 문제에서는 하나의 무방향 그래프(undirected graph)가 주어지며, 해당 그래프가 트리(tree)인지 아닌지를 판별해야 합니다. 트리의 기본 조건을 검사하면 비교적 간단하게 확인할 수 있습니다. 트리는 사이클(cycle)을 포함하지 않기 때문에, 그래프에 사이클이 하나라도 존재한다면 그 그래프는 트리가 아닙니다.또 다른 접근 방식으로도 판별할 수 있습니다. 그래프가 연결 그래프이면서 간선의 개수가 V-1개(V는 그래프의 정점 수)라면, 그 그래프는 트리일 가능성이 높습니다. 즉, 사이클 없음과 모든 정점의 연결성 두 가

그래프의 연결성(connectivity)을 확인하는 기본 원리는 간단합니다. 임의의 탐색 알고리즘을 사용해 그래프의 모든 노드를 순회해 보고, 탐색이 끝난 후에도 방문되지 않은 노드가 하나라도 남아 있다면 그 그래프는 연결되어 있지 않다고 판단합니다.다만 유향 그래프(directed graph)의 경우에는 무향 그래프와 달리 주의가 필요합니다. 특정 노드가 나가는 간선(outward edge)만 존재하고 들어오는 간선(inward edge)이 없다면, 다른 노드에서 탐색을 시작했을 때 해당 노드에 도달할 수 없습니다. 따라서 유향

깊이 우선 탐색(Depth-First Search, DFS)은 그래프를 순회(traversal)하는 대표적인 알고리즘입니다. 하나의 시작 정점이 주어지면, 인접한 정점을 발견하는 즉시 해당 정점으로 먼저 이동하고, 같은 방식으로 계속해서 탐색을 이어갑니다.DFS는 이름 그대로 가능한 한 깊게 경로를 따라 들어간 뒤, 더 이상 나아갈 곳이 없으면 백트래킹(backtracking)을 통해 이전 정점들로 되돌아와 아직 탐색하지 않은 새로운 경로를 찾습니다.DFS를 반복문(iterative) 방식으로 구현하려면 스택(stack) 자료구조가

그래프 이론에서 M-착색 문제(M-Coloring Problem)는 하나의 무방향 그래프와 m가지 색이 주어졌을 때, 서로 인접한 두 정점이 같은 색을 갖지 않도록 모든 정점에 색을 배정할 수 있는지 판별하는 문제입니다. 해가 존재한다면 어떤 정점에 어떤 색이 배정되었는지도 함께 출력해야 합니다. 이 문제는 대표적인 백트래킹(Backtracking) 기법으로 해결합니다. 0번 정점부터 시작해 한 정점씩 차례대로 색을 시도하는데, 색을 배정하기 전에는 반드시 해당 색이 안전한지 확인해야 합니다. 인접한 정점 중 이미 같은 색을 사용

N-퀸 문제는 N개의 퀸을 체스판에 배치하되, 어떤 퀸도 다른 퀸을 공격할 수 없도록 배치하는 고전적인 알고리즘 문제입니다.체스에서 퀸은 가로, 세로, 대각선 방향 모두로 이동하며 공격할 수 있기 때문에, 같은 행·열·대각선 위에 두 개 이상의 퀸이 존재해서는 안 됩니다.퀸들의 위치는 이진 행렬(binary matrix)로 표현합니다. 행렬에서 값이 1인 칸은 퀸이 놓인 자리를, 0인 칸은 빈 칸을 의미합니다.입력과 출력입력: 체스판의 크기. 일반적으로 8을 사용합니다. (8 × 8은 일반적인 체스판의 크기입니다.) 출력: N개의

문제 개요 이 문제에서는 N × N 크기의 미로가 주어집니다. 출발점은 항상 좌측 상단 칸이며, 도착점은 우측 하단 칸입니다. 미로에는 이동할 수 있는 칸과 막혀 있는 칸이 섞여 있고, 한 마리의 쥐가 출발점에서 도착점까지 이동할 때 경로를 완성할 수 있는지 판별해야 합니다. 경로가 존재한다면, 쥐가 따라갈 올바른 이동 경로를 표시하는 것이 목표입니다. 미로는 이진 행렬(binary matrix)로 표현됩니다. 값이 1인 칸은 이동 가능한 유효한 경로이고, 값이 0인 칸은 막혀 있는(블록된) 영역을 의미합니다. 참고: 쥐는 오른쪽

암호 산수(Crypt-Arithmetic) 문제는 알파벳 문자에 숫자를 대입하여 산술 연산이 성립하도록 만드는 퍼즐입니다. 서로 다른 열 개 이하의 문자가 0부터 9까지의 숫자 값을 하나씩 가지며, 각 문자에 대응하는 숫자로 계산했을 때 연산 결과가 실제로 맞아야 합니다.가장 대표적인 예시는 두 단어 BASE와 BALL을 더한 결과가 GAMES가 되는 경우입니다. 각 문자에 적절한 숫자를 배정하면 BASE + BALL = GAMES라는 등식이 실제 숫자 연산으로 성립하게 됩니다.참고: 사용되는 고유 문자는 최대 10개여야 합니다.

부분집합 합 문제는 정수 원소들로 이루어진 하나의 집합과 목표 합계 값이 주어졌을 때, 집합의 부분집합 중에서 그 합이 목표 값과 일치하는 모든 부분집합을 찾는 문제입니다.이 문제는 백트래킹(Backtracking) 기법으로 효율적으로 해결할 수 있습니다. 백트래킹은 가능한 해를 하나씩 시도해 보다가, 현재 선택한 원소가 유효하지 않으면 이전 상태로 되돌아가(백트랙) 다른 원소를 추가하는 방식으로 탐색을 진행합니다. 이렇게 하면 불필요한 경우의 수를 가지치기(pruning)하며 전체 탐색 공간을 크게 줄일 수 있습니다.입력과 출력입

이 글에서는 세계적으로 유명한 숫자 퍼즐인 스도쿠(Sudoku)를 컴퓨터로 해결하는 방법을 다룹니다. 스도쿠는 9×9 크기의 숫자 격자로 이루어져 있으며, 전체 격자는 다시 3×3 크기의 작은 박스 아홉 개로 나뉩니다. 스도쿠를 풀 때는 다음과 같은 규칙을 반드시 지켜야 합니다. 1부터 9까지의 숫자만 사용하여 퍼즐을 완성해야 합니다. 같은 숫자는 하나의 행, 하나의 열, 그리고 하나의 3×3 박스 안에서 중복될 수 없습니다. 여기서는 백트래킹(backtracking) 알고리즘을 활용해 스도쿠를 해결합니다. 빈 칸에 숫자를 하나

체스에서 나이트(knight)는 다른 말들과 달리 특별한 방식으로 점프할 수 있습니다. 나이트는 가로로 두 칸, 세로로 한 칸 이동하거나, 세로로 두 칸, 가로로 한 칸 이동할 수 있으며, 어느 방향이든 이동 경로가 영문자 L 모양을 그리게 됩니다.이 문제는 비어 있는 체스판 위에서 나이트가 임의의 위치에서 출발했을 때, 체스판의 모든 칸을 정확히 한 번씩 방문할 수 있는지 확인하는 것입니다. 모든 칸을 방문하는 것이 가능하다면, 각 칸에 시작점으로부터 그 위치에 도달하기까지 필요한 이동(점프) 횟수를 기록합니다.나이트 투어는 여러

줄다리기 알고리즘이란?줄다리기(Tug of War) 알고리즘은 주어진 정수 집합을 두 그룹으로 나누되, 각 그룹에 속한 숫자들의 합이 서로 최대한 비슷해지도록 분할하는 문제입니다. 실제 줄다리기 경기에서 양 팀의 힘이 균형을 이루도록 팀을 편성하는 것과 같은 원리입니다.분할 조건원소 개수 n이 짝수인 경우: 두 부분집합의 크기는 각각 n/2로 같아야 합니다.원소 개수 n이 홀수인 경우: 한쪽 부분집합은 (n-1)/2개, 다른 쪽은 (n+1)/2개로 나눕니다.입력 및 출력 예시입력: 서로 다른 무게들의 집합 {23, 45, -34,

단어 분리 문제는 공백 없이 이어져 있는 하나의 문장과, 유효한 영어 단어들로 구성된 사전이 주어졌을 때 해당 문장을 사전 속 개별 단어들로 나눌 수 있는 모든 가능한 방법을 찾는 알고리즘 문제입니다.해결 방법은 문자열의 왼쪽부터 탐색을 시작하여 유효한 단어를 찾는 것입니다. 유효한 단어를 발견하면 그 단어 뒤에 남은 문자열 부분에서 다시 단어를 검색하는 과정을 재귀적으로 반복합니다.입력 및 출력입력: 유효한 단어들의 집합(사전)과, 여러 단어가 공백 없이 붙어 있는 문자열 사전: {mobile, sam, sung, man, man