되면한다

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 그래프를 이용한 bfs, 재귀 dfs, 비재귀 dfs로 풀 수 있다. 1. bfs #include #include #include using namespace std; int n, m; vector adj[1002]; int u, v; int vis[1002]; queue _queue; int main() { std::ios::syn..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제가 솔직히 제대로 이해되지 않아, 그냥 일단 구현했다. 문제에서 인풋으로 10, 20, 30, 40을 넣으면 100이라는 출력값을 원하는 것 같은데, 문제 조건으로 답을 생각해보면 190이었다. 그래서 나는 190을 만드는 방법으로 구현했는데,,, 맞았다. 1. 특징 1) 그리디 2) 우선순위큐 2. 구현 포인트 1) 그리디: 제일 작은값과 그 다음 작은값을 골라서, 합친다 ->..

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..