1865 웜홀 코드 #include <bits/stdc++.h> using namespace std; int tc, N, M, W, road[501][501]; long long d[501]; bool check[501][501]; vector<int> connect[501]; bool belmanford(); int ...

1806 partial sum 알고리즘 (브루트포스) 1. 길이를 1부터 N까지 검사 2. 한 길이를 검사할 때 다음을 실행 1. 수열의 처음부터 길이만큼 더하고 sum에 저장, 첫번째를 따로 first에 저장. -> S를 넘는지 확인하고 안넘으면 2 실행 2. 수열의 (길이)번째부터 검사. 위에서 구한 sum에서 first를 빼고, 현재...

17837 새로운게임2 Samsung sw test 알고리즘(구현) 1. 색깔을 저장한 map, 말을 저장하는 3차원 배열 맵(각 칸마다 4칸만 있으면 됨), 각 칸에 말이 몇개있는지 저장하는 인덱스맵 2. 턴을 계속 진행함. 각 말을 순차적으로 검사함. 이때 각 말들을 몇 번 검사했는지 저장하는 temp 배열을 생성. 방향과 색깔에 맞춰 이...

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. 철수가 뽑은 카드의 수가 저장된 범위의 끝의 수보다 작을 때의 범...