되면한다

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제를 보면 떠올릴수 있는 풀이가 1) 이진검색트리 2) 우선순위 큐이다. 우선순위큐가 이진검색트리보다 빠르다. 따라서, 가장 큰값 작은 값을 찾고, 값을 지우거나 넣는 연산만 있다면, 우선순위 큐를 쓰는게 좋다. (n번째로 큰수를 찾아라, upper_bound, lower_bound를 사용해야한다면 이진검색트리사용) 사실 내가 이 문제를 따로 정리하는 이유는 우선순위큐에서 ..

https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net multimap을 사용해서 구현하려고 했다. 이렇게 풀면 문제 레벨을 오름차순으로, 문제레벨이 같은경우 문제 번호로 다시 오름차순 정렬해야 한다. 정렬할 때부터 일단 답이 없을 뿐만아니라, add를 구현할 때에는 문제 레벨, 문제 번호 다 고려해야 되기 때문에 upper_bound를 아무리 사용해도 답이 없다. 그래서 이 풀이법을 포기하고 정답을 봤다^^ 코드 출처..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이는 https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x16/solutions/1202.cpp 에서 가져왔다. 1. 특징 1) 그리디 2) 정렬 3) 이진검색트리 - set, multiset, map 2. 구현 포인트 **그리디 아이디어를 떠오르는게 중요하다 -> 가장..

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net bfs 문제이다. 1. 특징 1) 시작점이 여러개인 bfs 2) 시작점이 두종류인 bfs 2. 삽질 포인트 2-1) 처음에 플레이어를 움직이는 bfs 코드에서, (i, j)좌표에 불이 먼저 도착한 경우는 플레이어가 해당 좌표에 갈 수 없게 했다. if((firemap[nx][ny] t; while(t--) { cin >> w >> h; for(int i = 0; i > board..

https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 연속하는 부분 수열의 개수를 묻는 문제이므로 투포인터를 사용하면 된다. 1. 특징 1) 투포인터 2) 연속한 값이 부분 수열에 있는 지 확인하기 위해 bool형 배열 사용 2. 코드 #include using namespace std; // 투포인터 int n; int a[100002]; bool v[100002]; int main() { ios::sync_with_stdio(0); cin.tie(0);..

https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 전형적인 dp 문제이다. 1. 특징 이 문제의 점화식이 백준 14501.퇴사 문제와 비슷하다. https://todaywithhaeul.tistory.com/159 나는 우선 dp 테이블을 정의했다. 1) d[i]: i원을 쓸 때 늘릴 수 있는 인원의 최댓값 or 2) d[i]: 고객수를 i명으로 늘릴때 비용의 최솟값. 나는 2번으로 정의했다. (1번 풀이로 하고 싶다면, https://ong..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net bfs를 이용한 구현 문제이다. 문제 아이디어는 다음과 같다 for(i = n) for(j = n) a[i][j]에서 bfs를 돌면서 연합을 이루는 나라를 찾고, 그 연합나라의 인구 재배치를 한다. 그리고 이것을 인원이 재배치 할 일이 없을 때 까지 반복한다(while) #include #include #include #include using namespace std; int n,..

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 순열을 이용한 구현 문제이다. 요새 dp 문제를 계속 풀고 있어서, next_permutataion으로 풀어야하는 문제인지 규칙이 있는데 못찾은 dp 문제인지 엄청 고민했다...... 이문제는 8!(40320) * 50(n, n ru를 -1로 초기화함. 5) 루에 있는 선수들을 회전시키는 함수에서, 선수들이 다음 루로 이동하면, 현재 있던 루는 더이상 그선수가 없음을 처리해주어야하는데 안해주어서 오류..