1753 최단경로 알고리즘 1. 다익스트라 코드 #include <iostream> #include <queue> #include <vector> #define INF 2000000000; using namespace std; int V, E, s, length[20001]; vector<pair<...

17404 RGB Distance 2 알고리즘 : DP 1. bottom-top 방식으로 품 2. DP 구성 : (현재 깊이, 이전에 고른 색깔)칸에 현재 깊이에서의 최솟값 저장. 3. DP 작동 a. 첫번째 집은 for문으로 하나씩 들어감. b. 두번째 집부터 이전에 고른 색이 아닌 색으로 이동 c. 마지막집 + 1에 도착하면 0을 리턴 ...

17144 Samsung sw test 알고리즘 1. 기존 map에서 미세먼지가 있는 부분만, 기존에 있던 미세먼지만 확산시키는 게 관건 2. 따라서 tempMap을 만들어서 map을 복사한 다음에, map에 있는 미세먼지 양을 받아서, tempMap에 확산시키고, 다 확산하면 tempMap을 map에 복사하고 순환하여야 한다. 3. 자꾸 갱신되는...

16954 움직이는 미로탈출 알고리즘(BFS) 1. q와 nextq를 선언 2. q엔 현재 노드를 저장. 하나식 꺼내서 이동가능한 인접 칸을 nextq에 추가. 3. 다 추가하면, 벽을 한칸 내림 4. 이후 q에 nextq를 넣고, nextq는 비운채 다음 루프 시작. 5. 루프 중에 q에서 꺼낸 노드가 벽이 있는 칸이라면 추가안하고 다음 노드로,...

16946 벽부수고 이동하기 4 알고리즘 (BFS) 1. 각 맵의 빈공간마다 각자의 크기를 BFS로 구함 2. 이때, 각자의 id를 지정하여 같은 집합에 속하면 같은 id를 갖도록 하자 3. BFS가 끝나면 각 벽을 검사 -> 주변에 인접한 모든 빈공간의 아까 구한 크기를 모두 더하고 자기자신 + 1해서 리턴 -> 이때, 주변에 인접...

16724 피리부는 사나이 알고리즘 (DFS) 1. 맵에 있는 서로 이어져있는 그래프의 개수를 세면 됨. 2. visit을 만들어, 이미 검사한 그래프의 원소엔 true를 표시한다. 그리고 tempVisit을 만들어, 현재 검사하고 있는 그래프의 원소에 true를 표시한다. 3. 먼저, 첫번째 셀부터 검사하지 않았으면 DFS를 실시한다. ->...

16566 카드게임 알고리즘(이분탐색, 정렬, 분리집합, 세그먼트트리?) 1. 고른 카드를 버킷정렬함(400만개이므로 버킷정렬이 훨씬 빠르다. sort는 NlogN) 2. 범위를 저장하는 set<pair<int,int>>을 선언하고 첫 범위를 넣음(0-m) 3. 철수가 뽑은 카드의 수가 저장된 범위의 끝의 수보다 작을 때의 범...

16562 친구비 알고리즘 (union find) 1. unionfind 를 구현하되, 루트에 친구비가 적은 것이 오도록함 2. 루트만 골라 친구비를 정산한다. 코드 #include <iostream> #include <vector> #include <cstring> #include <algorithm&g...

1655 가운데를 말해요 내 방식 (multiset) 1. 멀티셋으로 가운데를 트래킹해가면서 구함 2. 첫번째 원소를 넣고, s.begin()으로 첫번째 iter를 middle로 받고 그대로 출력 3. 두번째부턴 middle과 같은 원소가 들어오면, s.insert(s.upperbound(*middle), input) 으로 가장 앞에 넣음 아...

1647 split town 알고리즘(MST) 1. MST를 만들고, 가장 거리가 긴 길을 빼면 된다. 2. n개의 노드에 대해 n-1개의 간선만 연결되어있으므로, 1개만 빼면 딱 두개로 나눌 수 있는데, 뺀다면 가장 거리가 긴 길이기 때문이다.(2개 이상 빼면 3개이상으로 나눠짐) 코드 #include <iostream> #inc...