수정 예정

monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다.

최악의 경우

이전 글 마지막 부분을 다시 가져와봅시다.

이번 글에서는 Union Find를 구현해봅시다. 배열을 이용한 구현과 트리를 이용한 구현, 총 두 가지를 살펴보도록 하겠습니다.

Union Find란?

Union Find는 상호 배타적 집합(disjoint set)을 표현할 때 쓰는 자료구조입니다.
라고 설명을 하면 무슨 소리인지 잘 모를 수도 있겠죠.

아주 간단하게 설명하자면, 전체 집합을 공통원소가 없는 부분 집합들로 나눠서 저장하는 자료구조입니다.

이분 매칭이란?

이전 글에서 Max-Flow를 구하는 방법에 대해 알아보았고, 마지막 부분에서는 문제 하나를 풀어보았습니다.
icpc.me/11375 문제를 풀어보았고, 문제를 그래프로 모델링하면 아래 사진처럼 그래프가 만들어졌습니다.

작동 방식

네트워크 플로우 관련 알고리즘 중 가장 기초적인 Max-Flow 중, Ford-Fulkerson알고리즘에 대해 알아보도록 하겠습니다.
이 알고리즘은 Max-Flow 뿐만 아니라 네트워프 플로우 관련 알고리즘 중 가장 먼저 고안된 알고리즘입니다.
동작 원리는 매우 간단합니다. 유량 네트워크에 있는 모든 간선의 유량을 0으로 초기화 시킨 뒤, 소스에서 source에서 sink로 유량을 더 보낼 수 있는 경로를 찾아 흘리는 동작만 반복하면 됩니다.

플로우 알고리즘

이전까지 다룬 그래프 알고리즘에서는 간선에 거리, 가중치 등을 나타내는 cost라는 값이 있었습니다. 네트워크 플로우에는 capacity라는 개념이 추가됩니다.
네트워크 플로우는 네트워크 유량이라고 부르기도 합니다. 핵심이 되는 아이디어는 (u, v)를 연결하는 간선이 있을 때, u에서 v로 용량 이하의 유량을 보낼 수 있다는 것입니다.
네트워크 플로우 관련 알고리즘은 위에서 말한 핵심 아이디어를 기반으로 해서, 시작점(source)에서 도착점(sink)까지 시작점에서 유량을 흘려보내 도착점까지 보내는 것이 목표입니다. 최대한 많이 흘려보내 Max-Flow, 최소한의 비용을 들여서 최대한 많이 흘려보내는 Min-Cost Max-Flow 등 여러 알고리즘이 있고, 몇 개의 글을 통해 하나씩 소개하려고 합니다.

이번 글에서는 입력 데이터를 학습한 뒤, 데이터를 두 가지로 분류하는 방법을 다룹니다.
이 글에서 사용할 예제는 다음과 같습니다.

Linear Regression에서는 가설 함수를 y = w1x1 + w2x2 + w3x3 형태로 작성을 하였습니다. 그러나 Logistic Regression에서는 결과를 0 또는 1로 만드는 것이 목표이기 때문에 가설 함수의 값을 0과 1 사이로 조정할 필요가 있습니다.
가설 함수를 다음과 같이 작성합시다.

아래줄에 있는 식은 시그모이드(sigmoid)함수라고 불리며, 입력 데이터를 0부터 1사이의 값으로 적절히 변환하여 반환해줍니다. 그래프는 아래 사진과 같습니다.

입력 값이 작아지면 0으로 수렴하고, 커지면 1로 수렴하는 함수입니다.

지금까지 해왔던 것과 달리, 이번 글에서는 행렬을 이용해 Linear Regression을 해보도록 하겠습니다.