문제 링크: https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 우선순위큐, 시뮬레이션 저는 이 문제를 다음과 같은 순서로 구현했습니다. 1. 적들을 아래로 한 칸 이동시키기 N행을 모두 0으로 만듭니다. (성에 도달한 적은 게임에서 제외) N-1행부터 1행까지 순회하면서 i행에 있는 모든 원소를 i + 1행으로 옮긴다. void moveEnemy() { for (int c = 1; c = 1; r--) { // N-1행 ~ 1행에 있는 모든 적을 int n..

문제 링크: https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS, 우선순위 큐, 정렬 BFS를 이용해서 현재 아기 상어가 있는 위치에서부터 아기 상어가 먹을 수 있는 상어들의 위치까지 최단거리를 구하고 먹을 수 있는 상어의 좌표를 우선순위 큐에 넣습니다. 이때 우선순위 큐의 정렬 기준은 거리가 짧은 순, 같다면 X좌표가 작은 순, 같다면 Y좌표가 작은 순입니다. 이제 아기 상어의 위치를 우선순위 큐에서 꺼낸 좌표로 갱신하고 그 위치까..

문제 링크:https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬, 우선순위 큐 indegree가 0인 정점 중에서 가장 번호가 낮은 정점을 먼저 방문해야 되기 때문에 위상 정렬을 우선순위 큐로 구현하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 4..

문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1 m; int data; int mid; priority_queue max_pq; priority_queue min_pq; vector ans; cin >> data; mid = data; ans.push_back(mid); //1개 일때는 ..

문제 링크: https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 www.acmicpc.net 우선순위 큐 항상 카드 수가 최소가 되는 카드 묶음끼리 뭉치면 됩니다. 최소 힙을 사용해서 입력받은 데이터를 모두 pus..

문제 링크: https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다. www.acmicpc.net 우선순위 큐 pair로 최소 힙을 만들면 되는데 frist는 x 절댓값을 저장하고 second는 x의 원본을 저장하면 된다. (절댓값의 최소니깐 first 기준으로 최소 힙을 만들면 됨) 1 2 3 4 5 6 7 8 9 10 ..

문제 링크: https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. www.acmicpc.net 우선순위 큐 priority_queue 비교연산자에 greater 넣어주면 힙을 오름차순으로 정렬 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #inclu..

문제 링크: https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. www.acmicpc.net priority_queue 사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include #include using namespace std; int..