Hungarian algorithm (헝가리안 알고리즘, 헝가리안 메소드 / C++)
헝가리안 알고리즘 0. 주저리주저리 배정 문제(assignment problem)를 해결할 수 있는 알고리즘. 예를 들어 보면 n명의 사람이 n개의 일을 할 때, 어떤 값의 최대(or 최소) 값을 구하는 데 사용된다. 여기서 보통 어떤 값은 비용이나, 효율 등을 적용할 수 있겠다. 정말 간단하게 문제를 접근해보면, brute force의 형태로 모두 대입해 볼 수 있다. 3명이 있다고 했을 때, 사람(1,2,3)과 일(1,2,3)을 매칭 해보자. 1번 사람이 일을 맡을 수 있는 개수 3개, 2번 사람은 2개, 3번 사람은 남는 거 1개. 따라서 3! 만큼 시간이 들고, 따라서 O(n!)의 시간 복잡도를 갖게 된다. (사용불가.) 헝가리안 알고리즘(Hungarian algorithm & Hungarian ..
boj, 백준) 19236. 청소년 상어 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 2. 문제 개요 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자. 물고기는 자기가 갖고 있는 고유의 방향이 있는데, 그쪽 방향으로 이동할 수 있다. 이동할 수 있는 칸은 빈칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다...
boj, 백준) 1655. 가운데를 말해요 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 2. 문제 개요 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 말해줬을 때 동생을 1, 1, 2, 2, 2, 2, 5와 같이 그때 불러준값의 중간값을 계속 말해야 한다. 프로그램을 작성하시오. 3. 문제 힌트 매번 가운데를 말해야 한다. 전체 크기를 알고 이게 정렬되어있다면 중간 인덱스를 지정하여 바로 출력할 수 있을 것이다. 그런데 이렇게 하기에는 ..
백준, boj) 1774. 우주신과의 교감 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 문제 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우� www.acmicpc.net 2. 문제 개요 주인공과 우주신들을 모두 연결해야 한다. 간접적으로 연결하여도 괜찮다. 이미 연결된 통로가 주어지고, 모두 연결하기 위한 통로길이의 합의 최솟값을 구해보자. 3. 문제 힌트 Kruskal 알고리즘을 사용해야한다. (1) 그런데, 이미 연결된 통로가 있다. 이런 경우에는 어떻게 전처리를 해야 할까? (2) 경로는 어떻게 구할까? 위의 두 가지 생각해야 할 점이 있다. ..
백준, boj ) 2211. 네트워크 복구 ( C++)
1. 문제 링크 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다� www.acmicpc.net 2. 문제 개요 N개의 컴퓨터로 구성된 네트워크가 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다. 어느 날 해커가 침입해서 네트워크를 복구해야 하는 상황에 이르렀다. 다음 두 가지 조건을 만족해야 한다. (1). 최소 개수의 회선만을 복구해야 한다. 네트워크를 복구한 후에..
boj, 백준) 2887. 행성터널 ( C/C++)
1. 문제 링크 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. � www.acmicpc.net 2. 문제 개요 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 두 행성을 x, y, z 좌표로 나타내고, 터널로 연결할 때 드는 비용은 min(|x2-x1|, |y2-y1|, |z2-z1|)로 정의한다. 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하자..