그리디 알고리즘 문제로, 1개의 회의실에 최대 몇 개의 회의를 배정할 수 있는지 찾는 문제이다. 그리디 알고리즘으로 풀어야한다는 것만 생각할 수 있으면 쉽게 풀 수 있는 문제다. 우선, 회의가 끝나는 순서대로 회의를 지정한다. 첫 번째 회의부터 배정을 하고 첫 회의의 끝나는 시간을 기록한다. 그 다음 종료되는 회의의 시작 시간과 이전 회의의 끝나는 시간을 비교하여 이전 회의의 끝나는 시간보다 시작 시간이 큰 경우만 추가하고, 끝나는 시간을 갱신하고 배정 카운트를 끝낸다. 이렇게 모든 회의를 끝까지 조회해보고 최종 카운트된 숫자를 출력해주면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include typedef struct room { int star..
알고리즘/백준(BOJ)
우선순위 큐를 이용하여 이 문제를 풀면 된다. 우선순위 큐를 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; }
