우선순위 큐를 이용하여 이 문제를 풀면 된다. 우선순위 큐를 2 개를 운용하는데, 현재까지 말한 숫자들의 부류를 작은 순서대로 정렬한다고 가정할 때, 절반은 작은 부류, 절반은 큰 부류로 나눈다. 이렇게 나눌 때 작은 부류는 내림차순이, 큰 부류는 오름차순이 우선순위인 큐로 설정한다. 이렇게 되면 작은 부류의 top 원소는 전체 숫자가 홀수일 때는 가운데 숫자가 되고, 짝수일 때는 가운데 두 수 중에서 작은 숫자가 된다. 그러면 출력할 때 항상 작은 부류의 top 원소를 출력하면 정답이 된다. 목표한 바 대로 정렬하기 위해서, 첫 번째 원소는 무조건 작은 부류의 우선순위 큐에 넣어줌으로, 작은 부류의 큐가 큰 부류의 큐보다 항상 사이즈가 1이 크도록 설정한다. 첫 번째 원소를 넣어주고, 입력받는 숫자를 ..
전체 글
최소 신장 트리, 크루스칼 알고리즘으로 문제를 풀었다. 크루스칼 알고리즘은 간선이 있으면 간선으로 접근하기 때문에, 간선을 먼저 생성하고 가중치가 적은 순서대로 정렬하였다. 근데, 문제를 다 풀고 나서 시간초과에 걸리게 되었는데, 간선의 정보를 담아둘 장소를 배열로 설정하느냐, 벡터로 설정하느냐에 따라 달라졌다. 처음에 접근은 전체 정점으로 트리를 구성하게 될 때 생길 수 있는 최대 간선 수를 계산하여서 배열에 할당을 하였다. 최대 간선 수 계산은 정점의 개수가 N이라고 할 때, N(N - 1) / 2로 설정하면 된다. N = 100이 최대였기 때문에, 최대 간선 수는 4950개 크기의 배열을 할당하고 시작한다. 배열의 크기를 고정시키기 때문에 불필요한 저장소 사용이 되었을 수 있다. 배열이 벡터 활용보..
신장 트리는 정점이 N개 존재할 때, 항상 N - 1 개를 이룬다. #define _CRT_SECURE_NO_WARNINGS #include int main() { int T; scanf("%d", &T); for (int t = 0; t < T; ++t) { int N, M; scanf("%d %d", &N, &M); for (int m = 0; m < M; ++m) { int tempA, tempB; scanf("%d %d", &tempA, &tempB); } printf("%d\n", N - 1); } return 0; }
방금 프로그래머스에서 풀어본 방식인 크루스칼 알고리즘으로 풀어보았다. 여기서 좀 헷갈렸고, 놓쳤던 부분은 parent를 설정할 때 정점이 1부터 시작한다는 것으로 생각해야하고, 그래서 V + 1 사이즈로 초기화해야한다. // MST(Minimum Spanning Tree) // 최소 신장 트리는 두 종류 알고리즘으로 풀 수 있다. // 크루스칼 알고리즘 VS 프림 알고리즘 // 크루스칼 알고리즘은 간선을 선택하며 찾는 알고리즘 // 프림 알고리즘은 정점을 선택하며 찾는 알고리즘이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; long long V, E; long long getRoot(vector& par..