코학다식

프로그래머스: 섬 연결하기 문제 링크 처음에는 아주 단순하게 생각해서 비용을 오름차순으로 정렬한 후에 선택된 다리의 수가 n-1개 이상이 되면 모든 섬을 방문하는지 확인하도록 했다. 결과는 당연히 틀렸다. 아마 사이클을 고려하지 않았기 때문인 것 같다. 질문하기를 보니 크루스칼 알고리즘(Kruskal Algorithm)을 사용했다는 말이 보였고, 바로 사용해 보았더니 쉽게 통과했다. 알고리즘 수업 이후로 잊고 살았던 이 친구를 다시금 리마인드하는 계기가 되었다. Kruskal Algorithm 가장 적은 비용으로 모든 노드를 연결하는 알고리즘이다. 즉, 최소 비용 신장 트리를 만드는 알고리즘이라고 할 수 있다. 모든 노드를 가장 적은 비용으로 연결시키기 위해 모든 간선(비용) 정보를 오름차순으로 정렬 후..

문제 링크 Solution 정렬 함수인 sort()만 사용하면 쉽게 풀 수 있는 문제로 보이지만, 주의해야 할 것이 하나 있다. 나이가 같은 경우 먼저 가입한, 즉 먼저 입력받은 요소가 앞에 와야 한다는 것이다. 이를 위해 비교 함수(comp)를 바꿔 줄 수도 있지만, sort()와 같이 정렬 함수 중 하나인 stable_sort()를 사용하면 간편하게 풀 수 있다. stable_sort()는 sort()와 같이 정렬을 수행한다는 것은 같지만 값이 같은 경우에는 원래의 순서를 그대로 유지한다. sort()의 경우 입력받은 데이터의 크기가 작으면 값이 같은 경우에 따로 처리를 해 주지 않아도 순서가 유지되는 것처럼 보이나, 데이터가 커지면 랜덤하게 바뀔 수 있다. code #include #include ..

문제 링크 :: https://www.acmicpc.net/problem/11375 Solution 이분 매칭으로 쉽게 풀 수 있는 문제이다. M개의 일을 해야 하는 상황에서 N명의 직원들 각각이 할 수 있는 일이 정해져 있고, 직원들은 하나의 일만 담당할 수 있다. 이분 매칭 알고리즘 설명 글에서 이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 하나의 간선으로만 연결되는 것을 의미한다고 했다. 일과 직원은 서로 같은 그룹끼리는 연결되지 않으면서 다른 그룹끼리만 연결 가능한, 전형적인 이분 그래프라고 할 수 있다. 이 문제는 이분 매칭을 최대한 많이 가능하게 만드는 것을 요구하고 있다. 그렇다면 어떻게 해야 이분 매칭을 최대한 많이 할 수 있을까? 이것 역시 이분 ..