[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] 우선순위 큐 (Priority Queue) (개념+코드 정리)

들어가며먼저 들어온 요청을 먼저 처리하는 것은 일반적으로 당연하게 일을 처리하는 방식이라는 생각이 든다.우리는 이러한 처리 방식을 큐(FIFO) 방식이라 부른다. 하지만 모든 일이 도착한 순서대로 처리되어야 할까?병원 응급실에서 가벼운 부상인 환자가 심정지 환자보다 조금 먼저 도착했다.만약 가벼운 부상의 환자를 먼저 처리해야 하는가? 라고 질문한다면 꼭 그렇지만은 않을 것이다. 이런 상황에서는 보통 "도착한 순서"가 아닌 "중요도(우선순위)"에 따라 작업을 처리해야 한다.바로 이럴 때 사용하는 자료구조가 우선순위 큐(Priority Queue)이다. 우선순위 큐 (Priority Queue)우선순위 큐는 들어간 순서와 상관없이, 특정 기준(우선순위)에 따라 요소를 정렬하고 관리하는 추상 자료형이다. 우..

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

[Algorithm] 좌표 압축 Coordinate Compression (개념+코드 정리)

좌표 압축 (Coordinate Compression) 이란?좌표 압축(Coordinate Compression)은 값의 범위(range)는 매우 크지만, 값의 개수(N)는 적을 때, 값들 사이의 상대적인 순서 관계만 유지한 채로 값들을 0부터 시작하는 새로운 인덱스로 변환하는 기술이다. 예를 들어보자. 수직선 위에는 5개의 요소가 있다. ex. [ 100, 4, 50, 4, 100000 ]이 좌표들을 배열로 관리하고 저장하면 어떻게 될까? 요소는 고작 5개 뿐인데, 우리는 배열 인덱스로 사용하기 위해 최소 100001 크기의 배열이 필요할 것이다. 엄청난 메모리 낭비가 발생한다. 그렇다면, 만약에 실제 크기가 아니라 누가 누구보다 크고 작은지만 중요하다면 어떨까?그럼 아래와 같이 새로운 인덱스가 할..

• format_list_bulleted Algorithm
• · 2025. 10. 22.
• 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