[백준 / C++] 15903번: 카드 합체 놀이 (그리디, 우선순위 큐)

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그리디 알고리즘, 우선순위 큐 접근 방법 점수를 최소로 하기 위해서는 매 선택마다 가장 작은 수를 가진 카드 두 장을 선택해야 한다. 따라서 가장 작은 수가 top에 오도록 하는 우선순위 큐를 이용한다. 우선순위 큐에서 가장 작은 수 2개를 뽑아서 합친 후 그 결과를 다시 우선순위 큐에 두 번 넣으면 된다. 그..

• format_list_bulleted PS/백준
• · 2023. 7. 29.
• textsms

[백준 / C언어] 11279번: 최대 힙(배열로 구현)

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 난이도: solved.ac 실버 2 자료구조 힙(Heap)을 구현하는 문제다 일반 이진트리(Binary Tree)는 input이 100,000개일 때 높이(depth)가 2^100000 - 1가 될 수 있지만 (한쪽으로만 연결된 경우에) 힙은 완전 이진트리(Complete Binary Tree)라서 input이 100,000개여도 높이는 log(2)100,000 밖에 되지 ..

• format_list_bulleted PS/백준
• · 2023. 5. 31.
• textsms

[백준] 1927번: 최소 힙 (C언어)

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 난이도: solved.ac 실버 2 그냥 우선순위 큐 구현 문제다 #define _CRT_SECURE_NO_WARNINGS #include #define HEAP_LEN 100001 #define TRUE 1 #define FALSE 0 typedef int PriorityComp(int d1, int d2); typedef struct _heap { PriorityComp* ..

• format_list_bulleted PS/백준
• · 2023. 2. 19.
• textsms

[백준] 1715번: 카드 정렬하기 (C언어)

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 난이도: solved.ac 골드 4 처음에 문제 풀이를 시도했을 때 이게 골드 4? 너무 쉬운데? ㅋㅋㅋㅋㅋㅋ 하고 답안을 제출했지만 틀렸습니다 ....? '어디가 틀린 거지?' 하고 의아했던 문제다 이 문제에서 주의할 점 두 가지가 있다 1. 비교할 카드 묶음의 개수가 남아있는 카드 묶음 중 최소가 되어야 하는 점 2. N = 1일 때는 비교할 대상이 없으므로 0이 출력되어야 한다..

• format_list_bulleted PS/백준
• · 2023. 2. 12.
• textsms