Byeo

문과 감성 이분 매칭 알고리즘은 사랑과 전쟁 이다. - 관심 있는 이성이 솔로라면 바로 커플을 맺는다. - 하지만 관심 있는 이성이 이미 커플이라면, 그 커플을 깨부순 뒤에 원하던 사랑을 쟁취한다. 다만, 지금 당장 행복한 커플을 내가 강제로 헤어지게 할 수는 없으므로 그 커플 중에서 동성이 새로운 이성과 바람나게 해야 한다. 내가 남자라면, 관심가는 여자를 쟁탈하기 위하여 그녀의 남자친구에게 새로운 여자를 소개시켜주는 것과 같다. 이분 그래프 (Bipartite Graph) 이분 그래프: 어느 그래프 $G$에 속해있는 모든 vertex를 두 그룹 $V_L$과 $V_R$으로 나누었을 때, 그래프 내의 모든 edge $e$의 양 끝이 $v_l \in V_L$ 과 $v_r \in V_R$ 인 그래프를 의미한..

1. 설명 MST를 구하는 유명한 알고리즘의 두 번째로는 크루스칼 알고리즘은 greedy 알고리즘으로 볼 수 있다. 간선의 가중치가 작은 것부터 하나하나 MST에 포함시켜보면서 cycle이 생기는 지 매번 판단하는 방법으로 이뤄진다. 이전 포스트의 프림 알고리즘 예제에서 사용했던 예제를 그대로 사용해보자! 추가로 MST가 무엇인지 알고 싶다면: 링크 2. 예제 (1) 초기 환경이 다음과 같다고 하자. 크루스칼 알고리즘은 가중치가 작은 간선부터 차례로 MST에 포함시켜 보는 것이다. 만약 포함시켰는데 MST에 위배된다면 뺀다. 오른쪽은 union-find array를 나타낸다. 자세히는, 각 vertex가 속해있는 그룹의 주인 (root, 특별한 역할이 있는 노드는 아니다. 단순히 학창 시절 '주번' 같은..

1. MST란 MST, 최소 신장 트리 (Minimum Spanning Tree)란? MST란, 가중치가 있는 무방향성 그래프 (weighted undirected graph)가 주어졌을 때, 모든 vertex를 연결할 수 있도록 edge를 선택하는데 그 가중치의 합(비용)이 최소가 되도록 하는 edge set을 말한다. MST 알고리즘을 통해 구한 edge들로만 그래프를 재구성하면, 임의의 vertex a와 b사이에는 항상 경로가 존재하며, 그래프에서는 cycle이 없다. 이를 구하기 위한 방법으로는 대표적으로 프림 알고리즘과 크루스칼 알고리즘이 있다. 프림 알고리즘은 우선순위 큐를 이용해서, 크루스칼은 union-find를 이용해서 해결한다. MST 특성 MST는 다음과 같은 특성을 지닌다. [참고]..

VSCode 설치 - vscode를 설치해봅니다! - 그리고 vscode를 이용해 원격 서버 접속 개발을 해봅니다. 1. Download https://code.visualstudio.com/download Download Visual Studio Code - Mac, Linux, Windows Visual Studio Code is free and available on your favorite platform - Linux, macOS, and Windows. Download Visual Studio Code to experience a redefined code editor, optimized for building and debugging modern web and cloud application..

목차 개요 설명 일반화 코드 개요 스위핑 (Sweeping)은 "쓸다" 를 의미합니다. 스위핑 알고리즘 이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이라고 보시면 됩니다. 이 알고리즘은 특정한 자료구조나 구체적인 코드가 있는 것은 아닙니다. 단지, 한쪽 방향에서 시작해서 다른 방향으로 차근차근 해결해 나가는 기법입니다. 이러한 특성 때문에, 보통 좌표와 관련있는 문제가 많이 보이는 듯 합니다. boj 2170 - 선 긋기 이 문제는 일직선상에 여러 길이의 선을 그어, 최종적으로 마지막에 그려져 있는 선의 길이를 구하는 문제입니다. 이 선끼리는 겹칠 수 있기 때문에 그린 길이의 총 합보다 그려져 있는 길이가 작거나 같을 수 밖에 없습니다. 여기서, 그릴 수 있는 좌표의 범..

목차 Solution 1. 선형 탐색 Solution 2. 세그먼트 트리 1) 생성하기 (Initialization) 2) 검색하기 (Search) 3) 수정하기 (Update) 예제) BOJ 2042 세그먼트 트리(Segment tree)는 어떤 수열들의 특정 구간에 대한 부분합, 최소값, 최대값 등을 쉽게 구하기 위하여 사용하는 자료구조 입니다. 보통 부분합, 최소값 등을 구하고자 하는 질의(query)가 여러 번 있을 때 사용합니다. 예를 들어, 배열(int arr[12])에 다음과 같은 값들이 있다고 가정하고 arr[1]~arr[8]의 부분합을 구해보죠. int arr[12] = {10, 7, 9, 0, 11, 7, 6, 5, 2, 13, 8, 6, 9}; Solution 1. 선형 탐색 구간 1..