Elevation

알고리즘 공부를 다시 하는 김에 오랜만에 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)$을 따른다면, 서로 독립인 정규분포는 선형결합이 가능하기에 표..