천천히 꾸준히

헝가리안 알고리즘을 보다 보면 matching과 vertex cover이라는 용어가 계속 나온다.

이게 도대체 무슨 의미길래 계속 나오는가?

vertex cover란?

어떠한 그래프에서의 접점인데, 모든 간선들을 커버하는 접점

도대체 접점은 뭐고, 그래프는 뭐고, 간선은 뭔데???

이러한 기본 지식을 설명하려고 한다.

그래프(graph)

"그래프란 정점(vertex)들이 간선(edge)들로 연결되어 있는 구조"

아래 그림을 보면 이해가 쉽다.

vertex란 선과선이 연결되는 지점, 끝점이며

edge란 정점들을 연결하는 간선이다.

아래에는 6개의 vertex와 5개의 edge가 있는 그래프이다.

자 그러면, 다시 vertex cover의 정의로 돌아가려고 한다.

vertex cover

"어떠한 그래프에서의 접점인데, 모든 간선들을 커버하는 접점"

이제 좀 이해가 가는가? 

아래의 각각의 그래프에서 빨간점은 모두 vertex cover가 된다. 

쉽게 말해 빨간점과 빨간 점에 이어진 선을 모두 제거하게 되면

남아있는 것이 없는 상태가 되는 vertex의 집합을 vertex cover라고 한다.

해당 내용을 기반으로 헝가리안 알고리즘을 다시 한번 보게 되면, 다른 블로그들의 설명을 좀 더 쉽게 이해할 수 있을 것이다. 

https://billionaire-hossa.tistory.com/36

reference

https://namnamseo.tistory.com/entry/Matching%EA%B3%BC-Vertex-cover

https://namnamseo.tistory.com/entry/Tree%EC%9D%98-%EA%B8%B0%EC%B4%88?category=589725

https://brilliant.org/wiki/vertex-cover/

SORT 논문을 학습중에 헝가리안 알고리즘이란 것을 쓴다는데... 도대체 이건 또 뭔지 알아보려고합니다.. 

Hungarian Algorithm이란?

헝가리안 알고리즘이라는 것은 assignment problem을 해결하는 최적의 솔루션(optimal solution) 입니다. 

그럼 먼저 assignment problem이 뭔지?,

그리고 어떻게 헝가리안 알고리즘이 사용하는지? 

알아보겠습니다.

assignment problem이란?

직역하면 할당 문제입니다.
어떻게 하면 가장 효과적으로 할당할 것이냐의 문제인데,
예를 들면, 회사에서 외주를 맡겨야 할 일이 3개가 있다고 한다면(식당, 보안, 환경관리)
해당 일들을 3개의 업체에 맡겨야 하는데 어떻게 맡기는것이 가장 효과적인가 하는 문제입니다.

아래는 각 업체별 업무에 따른 가격이 나와있습니다.

Optimal Solution (Hungarian algorithm)

위와 같은 상황에서 어떻게 하면 회사는 가장 저렴한 가격으로 각각의 업무를 부여할 수 있을까요?

이것을 해결하는 방법은 다음과 같은 절차를 따릅니다.  

1. 행에 대해서 가장 작은 값으로 뺀다

    -> 이 이유는 A업체에 각각에 비용에 3을 빼더라도 환경관리가 가장 싸고, 보안관리가 가장 비싸다는 내용 자체의 변화는 없기 때문입니다. 동일하게 행에 해당하는 B,C 업체도 동일하게 진행해줍니다.   

2. 열에 대해서 가장 작은값으로 뺀다.

이유는 동일합니다. 식당일은 1을 빼더라도 A,C업체가 가장 싸고 B업체가 비싼것에는 차이가 없기 때문입니다.

이렇게 얻은 행렬에서 0의 값을 가지는 업체-업무 쌍만 알게된다면 가장적은 비용으로 모든 업무를 처리해 낼 수 있을것입니다. 단 여기서 값에 해당하는 모든 행과 열은 0 이상의 값이여야 최적화를 할 수 있습니다. 

3. 모두가 0이되는 행과 열을(minimum-size vertex cover) 제외하고 가장 작은 값을 찾아 모든 행에 빼줍니다.

4. 음수가 되는 행렬의 원소를 음이 아닌수로 만들어 줍니다. 

최종적으로 A업체 - 식당, B업체 - 환경관리, C업체 - 보안관리가 최적의 선택이라는 결과가 나옵니다.

이 같은 알고리즘이 바로 헝가리안 알고리즘입니다. 

reference

https://gazelle-and-cs.tistory.com/29

수학에서 자연상수 e는 매우 중요한 역할을 하는 숫자입니다. e는 아래의 수학 상수들처럼 수학의 세계에서 빼놓을 수 없는 존재입니다.

• 1: 덧셈과 곱셈의 항등원
• 0: 덧셈의 항등원
• π: 원주율
• e: 자연로그의 밑

그렇다면 e는 정확히 무엇일까요?

e를 정의해봅시다

e는 **"1에 아주 작은 수를 더한 값을 무한히 큰 숫자로 거듭제곱했을 때 나오는 값"**입니다.

수식으로 표현하면 다음과 같습니다:

위 식을 보면, x가 무한히 커질수록 e에 가까워지는 것을 알 수 있습니다.

e의 근삿값은?

e는 무리수이자 초월수로, 정확히 표현할 수는 없지만 근삿값은 다음과 같습니다:

e ≈ 2.718281828

다시 말하면 e는 자연상수이고 값은 2.1828...이며 1에다가 0에 가까운 무한소를 더하고 그값을 무한대로 제곱한 값이다. 

e를 이해하는 다른 방법: 그래프

e를 더 잘 이해하기 위해 아래 함수의 그래프를 그려보겠습니다.

이 그래프를 보면 x가 0에 가까워질수록 함수의 값이 e≈2.71828에 가까워지는 것을 알 수 있습니다. 반대로 x가 음수로 가면 값은 점점 커집니다.

왜 중요한가요?

e는 단순한 숫자가 아닙니다. 아래와 같은 중요한 역할을 합니다:

1. 자연로그의 밑으로 사용됩니다.
2. 복리 계산, 성장과 붕괴 모델(예: 인구 증가, 방사성 붕괴)에서 핵심적인 역할을 합니다.
3. 미적분학의 여러 공식에서 핵심적인 상수로 등장합니다.

reference

- https://terms.naver.com/entry.naver?docId=1134067&cid=40942&categoryId=32210

- https://www.desmos.com/calculator?lang=ko

공분산이란?

공분산은 두 개의 확률변수의 선형 관계를 나타는 값입니다. 

그렇다면 확률 변수란 무엇일까요?

확률 변수는 확률함수의 변수로, 예를 들어 동전을 던졌을 때 앞면이나 뒷면이 나오는 것을 의미합니다.

확률변수의 개념이 궁금하시다면 아래 글을 참고하세요.

https://billionaire-hossa.tistory.com/46

예시

다음과 같은 데이터가 있다고 가정해 보겠습니다.

위 표에서 몸무게와 키를 비교해 보면, 몸무게가 높을수록 키도 크다는 것을 알 수 있습니다. 즉, 두 변수 간에는 양의 선형 상관관계가 있다고 할 수 있습니다.

공분산의 의미

공분산은 "공+분산" 입니다. 

두 변수의 분산을 계산하여 그 사이의 상관관계를 파악하는 것입니다.

분산이란 변수가 평균(기댓값)으로부터 얼마나 멀리 퍼져 있는지를 나타내는 값입니다.

아래 값과 같죠. 분산에 대한 자세한 내용은 아래 글을 참고하세요.

https://billionaire-hossa.tistory.com/27

공분산 계산 방법

공분산은 아래와 같이 구할 수 있는데,

• 평균으로부터 각각의 변수 값을 뺐을 때, 두 값 모두 양수 또는 음수라면 공분산은 양수가 됩니다.
• 평균으로부터 각각의 변수 값을 뺐을 때, 하나는 양수, 다른 하나는 음수인 경우 공분산은 음수가 됩니다.
• 값들이 평균을 기준으로 고르게 분포하면 공분산은 0에 가까워지며 상관성이 없다고 할 수 있습니다.

공분산에 따른 해석

이제 아래 그래프를 보면 이해가 쉬워집니다.

• 공분산이 양수이면 두 변수(X, Y)는 양의 선형 상관관계를 가집니다. (X가 증가하면 Y도 증가)
• 공분산이 음수이면 두 변수는 음의 선형 상관관계를 가집니다. (X가 증가하면 Y는 감소)
• 공분산이 0에 가까울수록 두 변수는 선형 상관관계가 거의 없습니다.

reference

위키백과 "공분산"

https://losskatsu.github.io/statistics/mean-vairance/

https://seeyapangpang.tistory.com/13

https://www.youtube.com/watch?v=RymrCV3K5J8