Elevation

플로우그래프에서 파생된 개념인 네트워크 유량(Network Flow)에 대해 알아보자. 그래프의 각 간선에는 유량이 흐를 수 있는 값의 제한인 용량(capacity)이 있고, 유량을 발생시키는 정점인 S(source)와 유량이 최종적으로 도착하는 T(sink)가 있을 때, S에서 T까지 이동하는 경로에서 간선의 용량을 넘지 않도록 유량을 적절히 흘려보내는 것이 network flow의 개념이다. 도로의 폭에 따라 출발점에서 도착점까지 화물을 적절히 배송해야 하는 상황이나, 대역폭에 따라 데이터를 나누어 전송하는 상황 등 말 그대로 네트워크에서의 흐름을 계산해야 할 때 이용하는 개념이라고 보면 된다. 유량에는 다음과 같은 성질이 있다.$f(u,v)\leq c(u,v)$S, T를 제외한 정점에서 $\sum..

알고리즘 공부를 다시 하는 김에 오랜만에 ps대회에 나가봤다. scsc에 있던 작년에는 일정이 겹쳐 못 나갔었는데, 이번에는 잊고 있었다가 친구가 알려줘서 나갈 수 있었다. Div 1,2,3을 모두 지원했는데 Div.3를 배정받았다. 가장 낮은 디비전이라서 상위권을 목표로 했는데, 운좋게 우승까지 하게 되었다. 생각했던 것보다도 확실히 초보자분들이 많으신 것 같아서(중고등학생들도 있는 듯) 동기부여 정도로 생각하고, 내년에는 Div.2 10위권 정도를 목표로 하려고 한다. 그래도 상품으로 버즈3를 받아서 기분은 좋다. 이번에 그래프 알고리즘을 열심히 정리해서 골드 문제로 dp나 그래프가 나오면 꼭 풀어야겠다고 생각했는데, 골드 세 문제가 모두 ad_hoc이라 좀 난감했다. 오랜만의 오프라인 대회라 첨에는..

나 같은 ML 관련 전공자가 아닌 사람이 ML을 배운다면, 수학적 이론을 깊게 파는 것보다는 자신의 분야에 자유롭게 접목시킬 수 있도록 코드를 자유롭게 짤 수 있는 역량이 더 중요하지 않을까 싶다. 그래서 책과 다양한 자료를 접하면서 실전적인 내용 위주로 정리해볼 계획이다. 머신러닝의 분류지도 학습(supervised learning): 답이 있는 데이터로 훈련한다. 즉 훈련 과정에서 입력 데이터($X$)와 답($y$, 흔히 레이블이라고 부름)이 주어진다. 훈련된 모델은 기존에 보지 못한 입력값 $X'$에 대해 예상되는 답 $y'$을 출력한다.비지도 학습(unsupervised learning): 답이 없는 데이터로 훈련한다. 따라서 데이터 자체의 특징을 분석하는 데 초점이 맞춰져 있다. 예로 클러스터..

그래프 간선의 분류단절점/단절선 알고리즘의 원활한 이해를 위해 그래프 간선을 분류하는 방법에 대해 알아보자. 유향 그래프에서, dfs를 하여 dfs 스패닝 트리가 형성되면 해당 트리를 기준으로 간선은 4가지로 분류할 수 있다.tree edge: dfs 트리에 속하는 간선forward edge: 조상에서 자손으로 향하지만, tree edge는 아닌 간선backward edge: 자손에서 조상으로 향하는 간선cross edge: 서로 조상-자손 관계가 아닌 두 정점 간 간선 무향 그래프의 경우, 방문하지 않은 정점을 연결하는 간선이 존재한다면 그 간선을 탐색할 것이므로 cross edge는 존재할 수 없다. 또한 방향이 없어 forward edge와 backward edge의 구분이 사라진다. 따라서 tre..

강한 연결 요소(Strongly Connected Component, SCC)를 구하는 알고리즘에 대해 알아보자. scc란 방향 그래프에서 정의되는 정점들의 최대 부분집합인데, 집합 안의 임의의 두 정점 $u, v$에 대해 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 모두 존재해야 한다. 쉽게 생각해서, 임의의 한 점에서 다른 점으로 자유롭게 이동 가능한 점들의 최대 그룹이라고 생각하면 된다. scc를 구하는 방법에는 코사라주(kosaraju) 알고리즘과 타잔(tarjan) 알고리즘이 있다. 두 방법 모두 dfs를 이용하기 때문에 시간복잡도는 $O(V+E)$가 된다. 코사라주 알고리즘코사라주 알고리즘은 다음과 같이 dfs를 2번 진행하여 scc를 구한다. 한 점에서부터 dfs를 진행..

앞서 4편에서는 하나의 출발점으로부터 각 정점의 최단경로를 구하는 알고리즘들에 대하여 알아보았다. 이번에는 임의의 두 정점 간 최단경로를 구하는 방법에 대해 알아보자. 플로이드-워셜모든 정점 간의 최단 거리가 필요할 때 가장 널리 사용되는 알고리즘이 플로이드-워셜(Floyd-Warshall) 알고리즘이다. 플로이드-워셜 알고리즘의 아이디어는 단순하다. $k$번 정점을 거쳐갈지 말지를 기준으로, 다음과 같은 점화식을 이용해 정점 $a$와 $b$ 간의 최단 거리를 구하게 된다. $$dist[a][b]=\min(dist[a][b], dist[a][k] + dist[k][b])$$ 따라서 인접 행렬을 이용해서 그대로 구현할 수 있다. 자기 자신으로 이동하는 거리는 0, 간선이 이어져 있지 않은 배열의 나머지 ..

https://www.acmicpc.net/problem/6198은근히 발상이 어려워서 고민을 했다. ​포인트는 한 건물에서 볼 수 있는 건물의 수를 따로따로 더하는 것이 아니라, 0~N-1까지 스캔하면서 해당 건물이 보이는 건물의 수를 더해준다고 생각하는 것이다. 예제를 가지고 순차적으로 사고해 보면, i번째 건물의 턴에서 자기보다 높이가 낮은 건물들은 치워주면 된다고 생각할 수 있다. 이때 순차적으로 스캔하기 때문에 최신(직전)의 건물들만 치워주면 높이 내림차순으로 자동 정렬되기에 추가적인 절차가 필요하지 않다. 후입선출이므로 스택을 사용한다. import sysinput = sys.stdin.readlineN = int(input())h = [int(input()) for _ in range(N)]..

통계적 추론의 또 다른 방법인 검정에 대해 알아볼 것이다. 추정이 사전 정보 없이 모수의 값을 직접 예측하는 것이라면, 검정은 모수에 대한 주장을 받아들일지의 여부를 표본을 통해 판단하는 간접적 추론으로 볼 수 있다. '기존 주장이 틀렸고 나의 주장이 맞다'는 것을 입증해야만 하는 과학의 세계에서, 검정은 그 도구로 유용하게 쓰인다. 가설 검정은 다음의 단계로 진행된다.1. 가설 설정2. 검정의 유의수준 $\alpha$ 설정3. 표본을 바탕으로 검정통계량 계산4. 검정통계량을 바탕으로 기각역이나 p-value를 구해 결론 도출 통계적 가설귀무가설($H_0$): 알려진(현재 믿어지는) 가설. 모집단의 모수를 하나의 값 또는 구간으로 표시한다.대립가설($H_1$): 연구자가 주장하고자 하는 가설. 귀무가..

표본을 통해 모집단을 예상하는 통계적 추론으로 본격적으로 들어가 보자. 통계적 추론에는 추정과 검정이 있는데, 먼저 추정에 대해 간단히 다뤄볼 것이다. 추정의 원리추정량(estimator): 모수를 추정하는 데 사용하는 통계량(함수)추정값(estimate): 추정량의 관측값 추정이란, 추출한 표본을 토대로 모수의 값을 추측하는 과정이다. 추정에는 점추정과 구간추정이 있다.이때 모집단 전체가 아닌 표본을 보기 때문에 오차가 생길 수밖에 없는데, 이를 표집오차(sampling error)라 한다.표집오차는 변동(variance)와 편의/편향(bias)로 분해된다. $$\hat{\theta}-\theta = [\hat{\theta}-E(\hat{\theta})] + [E(\hat{\theta})-\theta..

저번 편에서 categorical data의 개수를 통계량으로 하여 얻을 수 있는 분포인 초기하분포와 이항분포에 대해 구체적으로 다루었다. 이번에는 연속형 모집단에서 추출한 표본의 통계량을 바탕으로 한 표본분포들에 대해 정리해 보자. 표본평균의 분포 (feat. 정규분포)먼저 표본평균이라는 통계량의 성질에 대해, 다음처럼 유도할 수 있다. 표준오차(standard error)는 통계량의 변동성으로 통계량 자체의 정확성과 관련있다. 일반적으로 각 표본에서의 변동성을 표준편차(standard deviation)으로 부르므로 서로 다른 개념이다. 그렇다면 표본평균은 어떤 분포를 따를까? 모집단이 만약 정규분포 $N(\mu, \sigma^2)$을 따른다면, 서로 독립인 정규분포는 선형결합이 가능하기에 표..