[Algorithm] 이분 매칭(Bipartite Matching) (개념+코드 정리)

서론알고리즘 문제를 풀다 보면,"N명의 사람에게 N개의 작업을 배정하는데, 서로 겹치지 않게 최대 몇 쌍을 만들 수 있을까?" 와 같은 유형을 마주하게 된다.이분 매칭 문제는 언뜻 보면 복잡해보이지만, "이분 그래프"의 개념과 "재귀 탐색"만 이해하면 잘 이해할 수 있다!한번 천천히 글을 보고 이해해보자. 이분 그래프와 매칭이분 매칭을 이해하려면 먼저 두가지 용어를 알아야 한다.매칭 (Matching)그래프에서 매칭이란, 간선(E) 들이 서로 정점(V)를 공유하지 않는 집합을 말한다. 만약 하나의 간선에서 특정 정점을 사용했다면, 그 정점은 다른 간선에 포함될 수 없다. 그럼, 최대 매칭은 무엇일까?최대 매칭(Maximum Matching) : 이 매칭의 쌍(Pair)의 수가 가장 많은 경우를 찾는 것 ..

• format_list_bulleted Algorithm
• · 2025. 12. 18.
• textsms

[Algorithm] 최단 경로 알고리즘 (1) Dijkstra 다익스트라 (개념+코드 정리)

최단 경로 알고리즘 (Shortest Path Algorithm)최단 경로 알고리즘 (Shortest Path Algorithm), 말 그대로 최단 경로를 찾기 위한 알고리즘이다. 그렇다면, 최단 경로가 무엇일까?최단 경로를 이해하기 위해서는 그래프에 대한 이해가 필요하다. 그래프 관련 용어 정리그래프(Graph) : 전체 지도 (노드와 간선의 집합)노드 (Node / 정점, Vertex) : 지점간선 (Edge) : 정점과 정점 사이를 연결하는 선가중치 (Weight) : 간선을 지나가는 데 소요되는 비용경로 (Path) : 한 노드에서 다른 노드까지 간선을 따라 이동하는 순서 최단 경로 : 경로에 포함된 가중치의 합이 최소가 되는 경로를 말한다. 최단 경로 알고리즘의 구분최단 경로를 구하는 알고리즘은..

• format_list_bulleted Algorithm
• · 2025. 11. 7.
• textsms

[Algorithm] Union & Find (유니온 파인드) (개념+코드 정리)

들어가며일반적인 그래프의 형태를 상상해보자.여러 개의 노드가 흩어져 있고, 이들 사이에는 간선으로 관계가 나타나고 있다. 만약 누군가가 이러한 질문을 던진다고 생각해보자. "2"와 "3"이 지금 같은 그룹에 속해 있나요?"2"가 속한 그룹과 "3"에 속한 그룹을 하나의 그룹으로 합치고 싶은데 어떻게 해야 하나요?예를 들어 친구 관계에서 '내 친구의 친구'는 모두 '내 친구'라고 가정해보자.A와 B가 친구이고, B와 C가 친구라면, A와 C도 결국 같은 그룹에 속한다고 말할 수 있다. Union & Find(유니온 파인드)는 이러한 경우의 문제 유형에 자주 사용되는 자료구조이다.여러개의 독립된 집합(Disjoint Sets)을 관리하고,두 집합을 합치고(Union),특정 원소가 어느 집합에 속하는지 찾는..

• format_list_bulleted Algorithm
• · 2025. 11. 4.
• textsms

[Algorithm] 트리, 이진트리, 이진탐색트리 (개념+코드 정리)

트리 (Tree)트리란?노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 트리의 구조이진 탐색 트리 (Binary Search Tree)왼쪽 자식을 left, 오른쪽 자식을 right 라고 하자.이진 탐색 트리는 3가지 주요한 특징을 가진다. 주요 특징1. 자식이 최대 2개2. left가 존재한다면 → left의 key 값 ≤ 자신의 키 값 3. right가 존재한다면 → right의 key 값 ≥ 자신의 키 값 여기서 또 하나의 중요한 특성은, 중위 순회(Inorder Traversal) 시 방문하는 순서에 따라 노드값이 반드시 증가(감소 x)한다는 점이다.ex) 9 → 12 → 14 → 17 → 19 → 23 → 50 → 54 → 72 → 74 → 76이진 트리의 종류정 이진트리 (..

• format_list_bulleted Algorithm
• · 2025. 10. 21.
• textsms

[BOJ] N과 M 문제 풀이(정답) (7번부터 12번까지)

N과 M 7번 (중복순열)https://www.acmicpc.net/problem/15656import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;/** * 중복순열 - 순열을 구할 수가 주어지는 경우 * 문제 * N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. * * N개의 자연수 중에서 M개를 고른 수열 * 같은 수를 여러 번 골라도 된다. * 입력 * 첫째 줄에 N과 M이 주어진다. (1 ..

• format_list_bulleted BOJ
• · 2025. 10. 20.
• textsms

[BOJ] N과 M 문제 풀이(정답) (1번부터 6번까지)

N과 M 1번 (순열)https://www.acmicpc.net/problem/15649import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;// 순열 - 배열class Main { static int N, M; //N개중 M개 static int[] arr; static boolean[] isSelected; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStr..

• format_list_bulleted BOJ
• · 2025. 10. 17.
• textsms