기술 블로그

https://www.acmicpc.net/problem/17250 유니온-파인드(union-find) 문제이다. 배열 2개를 활용하면 된다. 주의할 것은 루트 노드가 더 작은 쪽에 더해진다.(sum 배열) 또한, 루트 노드가 같으면 union을 하면 안 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include using namespace std; int n, m; int parent[100100], sum[100100]; vector v; int getParent(int x){ if (x == parent[x]) return x; return parent[x] = ge..

https://www.acmicpc.net/problem/17352 유니온-파인드(union-find) 문제이다. 주의할 것은 parent[i]와 getParent(i)를 구별하는 것이다. parent[i] : i의 부모 노드(번호) getParent(i) : i의 루트 노드(번호) 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include using namespace std; int n, parent[300003]; int getParent(int x){ if (parent[x] == x) return x; return parent[x] = getParent(parent[x]);} void unionP..

https://www.acmicpc.net/problem/17386 https://www.acmicpc.net/problem/17387 선분 AB와 선분 CD가 교차하려면, 선분 AB를 기준으로 C와의 방향과 D와의 방향이 서로 달라야 한다. 즉, CCW(A, B, C) * CCW(A, B, D)의 값이 음수여야 한다. 선분 CD의 입장에서 마찬가지이다. CCW(C, D, A) * CCW(C, D, B)의 값이 음수여야 한다. 즉, CCW(A, B, C) * CCW(A, B, D) d) swap(c, d); return a

https://hsdevelopment.tistory.com/382 위의 링크로 들어가면, 맨 아래에 문제와 정답 코드가 있다.

https://www.acmicpc.net/problem/2234 어려운 문제는 아니나, 자잘한 기능들을 구현하는데 귀찮은 문제이다. 내 생각엔 이 문제의 핵심은 그루핑(grouping, 그룹화, 그룹 저장 등)이다. 또한, 오른쪽이나 왼쪽으로 갈 경우 4, 1에 대한 검사와 위아래로 갈 경우 2와 8에 대한 검사만 잘 해주면 된다. 각 숫자에 대한 bit가 어떤 숫자들로 구성되어있는지는 [행][열]에 대한 vector로 저장했다. 코드가 좀 긴 것 같고, 배열의 이름이 헷갈릴 수도 있겠다. 더 간결하고, 빠른 코드가 있을 것이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253..

https://www.acmicpc.net/problem/17259 핸드폰 게임하면서, 푼 문제라서 다소 코드가 깨끗하지 못 하고, 변수명이 헷갈릴 수 있다. 처음 제출했을 때 틀렸었는데, 알고보니 isExit() 함수 내에서 present만 검사하였다. person도 검사해야 선물이 완전히 없어지는 것을 검사할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108..

https://www.acmicpc.net/problem/1726 핵심은 rotation 배열이다. rotation[a][b] = a번 상태에서 b번 상태로 회전하는데 횟수 또한, 문제 잘 읽자. 나는 최대 3까지 이동하는지 모르고, 끝까지 갈 수 있는 것으로 생각하여 구현했었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include using namespace std; typedef struct info{ int y, x, dir, Min;}info; in..

https://www.acmicpc.net/problem/14395 일반적인 BFS 문제이다. 복습하고, 다시 풀어볼 문제이긴 하다. 한 번에 맞을 줄은 몰랐다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include using namespace std; long long s, t; queue q; map m; vector v = { '*', '+', '-', '/' }; int main(void){ scanf("%lld %lld", &s, &t); if (s == t) { p..