알고리즘 문제풀이/백준134 [백준 1966] 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 약한 유형이어서 정리해본다. 문제의 핵심: 큐가 2개 필요하다. 1) 순서를 저장하기 위해 필요한 큐 2) 주어진 값들 중 최댓값을 찾기 위한 우선순위 큐 문제의 조건에서 선택되지 못한 숫자는 맨 마지막 열에 다시 합류하므로 이 순서를 저장할 큐가 필요하며 주어진 숫자 중 최댓값을 매번 찾아야 하므로 우선순위 큐가 필요하다. 접근법: 큐에는 인덱스와 값을 우선순위 큐에는 값만 저장한다. 1. IF 우.. 2021. 11. 11. [백준 5214] 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 느낌상 bfs를 사용해야 하는 것을 알겠으나 연결 그래프를 만들 때 모든 노드 각각에 대해 연결선을 만들면 시간 초과가 발생하는 문제이다. 이 때 사용하는 방법은 바로 더미노드를 만드는 것이다. 더미 노드를 만들어서 허브로 사용하여 노드를 연결한다. 1~n까지는 진짜 노드이고 n+1부터 더미 노드를 설정한다. 더미 노드의 경우 거리가 0으로 처리되게끔 한다. /* 환승 .. 2021. 7. 5. [백준 14501] 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net n=15라서 dfs와 dp모두 가능하다. 1번 접근 dfs 모든 경우의 수에 대해 최대 이익을 구하는 것이다. //브루트 포스 사용 #include #include #include #include using namespace std; int max_sum = -1; int n; struct Day { int during, val; }; vector tasks; void bruteforce(int cur_day, int val_sum, int val_cur) { if (cur_day == n + 1) { max_sum = max(max.. 2021. 7. 1. [백준 1806] 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N R이 되면 합이 음수가 .. 2021. 6. 20. 이전 1 2 3 4 ··· 34 다음