기술 블로그

https://www.acmicpc.net/problem/2792 이분 탐색 문제이다. 핵심은 total이 N보다 작거나 같으면 right = mid - 1로 통해 계속해서 mid를 작게 한다. 문제에서 어차피 모두에게 나눠주지 않아도 된다고 하였기 때문이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include using namespace std; int N, M; vector v; int bs(int left, int right){ int ret = 2e9; while (left N) break; } if (total

https://www.acmicpc.net/problem/1173 2가지 방법이 있다. 시뮬레이션, BFS [시뮬레이션]운동은 맥박을 고려해야한다.(M을 초과하면 안 됨) 그러나 휴식은 무조건 가능하므로(M-R M의 경우만 고려하면 된다. [BFS]시간이 중복되지 않게 방문 처리한다.물론 BFS인 경우 배열의 범위를 초과하면 안 된다.문제에서는 통과가 된다. 시뮬레이션1234567891011121314151617181920212223242526272829#include using namespace std; int N, m, M, T, R, t, ec, h;/*t : 시간, ec : 운동 횟수, h, 맥박*/ int main(void){ scanf("%..

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