기술 블로그

https://www.acmicpc.net/problem/17472 1. DFS로 각 섬을 Group화 한다.(1, 2, 3, ...) 2. BFS로 각 정점끼리의 거리를 구하는데 이 때, 4가지 방향(동서남북)에 대한 배열(코드의 vertex)을활용해야 한다. 이유는 아래 예제를 생각해보자.(주의 : 나의 코드에서는 방문 처리를 말하는 것이 아니다. 다른 방법으로 방문 처리를 4가지 방향으로 해도 된다. 단순 이 글에서의 설명이다.) 1234565 101 1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 0 11 0 0 0 0 0 1 0 0 11 0 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 1 1 cs 3. MST로 활용하기 위해, mst vector에 {간선의 가중치, 현재 정..

https://www.acmicpc.net/problem/2842 복습 bfs 생각 이분 탐색 bfs로 가중치가 더 작으면 갱신하는 방식으로 구현하려다가 반례가 바로 눈에 들어왔다. 핵심은 투포인터 + dfs이다. 또한, vector v에서 중복 원소를 없애는 것도 핵심이 될 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include using namespace std; #define Max 52 int N, sy, sx, k;int dy[8] = { 0, 1, 0, -1, -1, 1..

https://www.acmicpc.net/problem/2606 유니온 파인드(Union Find) 문제이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include using namespace std; #define Max 101 int parent[Max], virus[Max], N, C; int Find(int x){ if (parent[x] == x) return x; return parent[x] = Find(parent[x]);} void Union(int a, int b){ a = Find(a); b = Find(b); if (a != b) { if (a

https://www.acmicpc.net/problem/17471 백트래킹 + bfs 문제이다. bfs로 같은 구역인지 확인하고(chk 함수), bt함수에서는 백트래킹으로 탐색한다. 당연히 g의 size가 N이면, return 해야하고(하나의 구역이므로),g가 비어있으면 안된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include using namespace std; int N, person[11], Min = 2e9;vector v[11]; bool c..

https://www.acmicpc.net/problem/1938 처음에 나의 접근은 방문처리를 3개(B,B,B)를 모두 하려 했지만, 생각해보니 굳이 이렇게 할 필요가 없었다. 즉, 중간만 방문처리 하면 된다. 또한, 가로, 세로 여부만 따지면 된다. 코드가 다소 긴 문제이다. 점 하나 하나 조건을 따져야하기 때문이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081..

https://www.acmicpc.net/problem/1152 그냥 세주면 된다. 1234567891011121314151617181920212223242526#include using namespace std; int main(void){ int ans = 0; string s, word = ""; getline(cin, s); for (auto i : s) if (i == ' ') { if (word.length() >= 1) { word = ""; ++ans; } } else word += i; printf("%d\n", word.length() >= 1 ? ans + 1 : ans); return 0;}Colored by Color Scriptercs

https://www.acmicpc.net/problem/2230 정렬, 투포인터 문제이다. 값의 차이가 M보다 큰 경우 left를 증가시켜 값의 차이를 감소해준다.값의 차이가 M보다 작으면 right를 증가시켜 값의 차이를 증가시킨다. 12345678910111213141516171819202122232425262728293031323334#include using namespace std; vector v; int main(void){ int N, M, input, Min = 2e9; scanf("%d %d", &N, &M); for (int i = 0; i = v.size() || right >= v.size()) break; int d = v[right] - v[left]; if (d >= M) ..

https://www.acmicpc.net/problem/1049 3가지 경우로 나누면 된다. 6개 패키지 세트만 사는 경우낱개로만 사는 경우조합을 해서 사는 경우 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include using namespace std; int n, m; vector pack, piece, total(3, 0); int main(void){ int six_pack, pie; scanf("%d %d", &n, &m); for (int i = 0; i