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

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

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

[Algorithm] 최단 경로 알고리즘 (2) Bellman-Ford 벨만-포드 (개념+코드 정리)

최단 경로 알고리즘의 구분최단 경로를 구하는 알고리즘은 대표적으로 3가지 종류가 있다. 다익스트라 (Dijkstra)모든 거리값이 음수가 아닐 때만 적용 가능 [Algorithm] 최단 경로 알고리즘 (1) Dijkstra 다익스트라 (개념+코드 정리)최단 경로 알고리즘 (Shortest Path Algorithm)최단 경로 알고리즘 (Shortest Path Algorithm), 말 그대로 최단 경로를 찾기 위한 알고리즘이다. 그렇다면, 최단 경로가 무엇일까?최단 경로를 이해하기 위해서willie1020.tistory.com 벨만 포드 (Bellman-Ford)거리값이 음수일 때도 적용 가능 플로이드 와샬(Floyd-Warshall)거리값이 음수일 때도 적용 가능 오늘은 이 3가지 알고리즘 중에서,..

• format_list_bulleted 카테고리 없음
• · 2025. 11. 11.
• 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

[Database] RDB과 NoSQL의 차이에 대해 설명해주세요. (설명+꼬리질문 정리)

RDB와 NoSQL의 차이에 대해 설명해주세요RDB, 관계형 데이터베이스는 엄격한 규칙(스키마)에 따라 데이터를 저장한다. 그렇기 때문에 데이터가 중복 없이 체계적으로 관리되고, 테이블 간 관계를 맺어 데이터를 합쳐서(Join) 보기 용이하다. 데이터의 일관성(ACID)을 보장하기 때문이다. 하지만, 규칙이 엄격하기 때문에 정해진 형식과 다른 데이터는 RDB에 보관하기 어렵다. NoSQL은 정해진 규칙(스키마)이 없거나 매우 유연한 형태로 존재한다. 어떤 형태의 데이터든 빠르게 저장할 수 있다는 특징이 있어서, 비정형 데이터 저장에 주로 사용된다. 만약 저장소 공간이 부족해지면, 수평적인 확장이 용이하기 때문에 확장성이 뛰어나다. 하지만, 해당 저장소 안에 데이터 간의 관계성을 파악하기에는 매우 복잡하다..

• format_list_bulleted CS/Database
• · 2025. 11. 3.
• textsms

[Database] 정규화(Normalization) (설명+꼬리질문 정리)

정규화가 무엇인가요?정규화는 관계형 데이터베이스를 설계할 때, 데이터의 중복을 최소화하고, *무결성을 보장하기 위해 테이블을 특정 규칙에 따라 분해하는 과정이다. 정규화를 통해 삽입, 수정, 삭제 시에 발생할 수 있는 이상현상을 방지하고, 데이터 구조를 더 효율적으로 논리적으로 만들 수 있다. *무결성:데이터의 정확성, 일관성, 유효성이 유지되는 것을 의미한다. - 정확성 : 중복이나 누락이 없는 상태 - 일관성 : 원인과 결과의 의미가 연속적으로 보장되어 변하지 않는 상태 - 유효성 : 사용자로부터 값을 입력받을 때 정확한 값만 입력되도록 하는 성질 예를 들어보자.여기 학생과 수강 과목 정보가 하나의 엑셀 시트에 저장되어 있다. 만약 이렇게 저장되어 있을 때, 아래와 같은 상황이 발생하면 어떨까? - ..

• format_list_bulleted CS/Database
• · 2025. 10. 30.
• textsms