https://www.acmicpc.net/problem/8983 #문제 간단 정리 #문제 해결 방법 우선 동물의 개수가 10만개사대의 개수가 10만개 즉 완전 탐색으로는 10만 * 10만 으로 100억이라 완전 시간초과그래프 탐색도 최악의 경우에는 완전탐색이기에 방법이 없다 dp 는 딱히 떠올리는게 없고 결국 동물의 위치와 가장 가까운 사대는 x가 가까울수록 위치도 무조건 가까워지니이분탐색 log n으로 풀어주면 된다. 사대정렬 n log n + m log n 으로 시간복잡도가 충분하니 이대로 풀면 된다. #전체 코드 #include #include #include using namespace std;typedef long long ll;vector> animals;vector shooters;i..
https://www.acmicpc.net/problem/28333 #문제 간단 정리역방향 bfs 문제 #문제 해결 방법 여러개의 최단경로의 경로상의 도시들을 선택하는 문제 역방향 bfs에 대한 아이디어가 없었기에최단경로로 다익스트라를 선택해서다익스트라가 경로를 기억하도록 변경해서 했더니 최단경로가 여러개가 될 수 있다는 것을 간과했다.#include #include #include #include #include #include using namespace std;int dist[1001];vector> nodes;vector routes;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; w..
이번에 3/15일 멀티캠퍼스 역삼에서 삼성B를 보고동계 DX 알고리즘 특강이 마무리 되었습니다.간단하게 다른분들도 신청할 때 참고하시라고 간단한 후기글을 적습니다. 특강접수: 특강 접수는 대략 5일정도 진행됬었던거 같고.꽤나 접수 기간이 짧은 편이라서 신경 안쓰고 있다가는 놓치기 쉽습니다. 비슷한 SDS 특강과는 다르게자소서 없이 이메일이나 개인정보만 입력하면 신청 할 수 있습니다. #사전 문제 풀이 : 신청을 했다면 이제 사전 문제 풀이를 진행해야 되는데SWEA 에서 진행되고 대략 일주일정도의 풀이 시간이 주어지고3문제 나올때가 있고 2문제 나올 때가 있는 것 같은데 저는 2문제가 출제되었습니다.모두 API 구현이라는 형식으로 나오게 되는데 main.cpp 와 solution.cpp 가 주어지고저희는..
https://www.acmicpc.net/problem/15811 #문제 간단 정리브루트포스 + 백트래킹 문제 다만 최적화가 좀 필요하다 #문제 해결 방법 우선 제일 주목해야 될점은숫자는 0~9까지밖에 없으니까 한번에 나오는 알파벳은 10개로 제한된다. 즉 알파벳을 할당하는데 10!이라서 충분히 가능해 보인다. 거기에 18길이의 단어니까 18*3 * 10! 해도 충분해 보이니 #include #include #include #include #include #include using namespace std;unordered_map mapping;vector> alphas;vector token;bool possible;bool used[10] = { false };void check() { ..
https://www.acmicpc.net/problem/12786 #문제 간단 정리 다익스트라를 사용하거나dp를 사용하거나 #문제 해결 방법 우선순위 큐를 사용하는로직이 더 직관적이라 생각해서 우선순위 큐를 사용해서 풀었다기본적인 골자 로직은 다익스트라와 같게 풀었다고 생각한다. #전체 코드#include #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, K; cin >> N >> K; vector> holes(N, vector(21, false)); for (int i = 0; i > M; ..
https://www.acmicpc.net/problem/14575 #문제 간단 정리매개변수탐색 (이분탐색)#문제 해결 방법 우선 첫번째로 모든 최소값 Li 를 더해서T를 넘으면 불가능이고모든 최대값 Ri 을 더해서 T 보다 낮으면 T를 만들 수 없어서 불가능이다 그 외에는 s값을 이분탐색으로 구해서Li 만큼 우선 주고 mid 나 R[i] 값중 둘중 R[i] 이 mid 보다 크다면 mid - L[i] 으로 여유분으로 줄 수 있는 값을 구할 수 있다. 우선 최소값 + 여유분이 >= t 라면 무조건 t를 만들 수 있기 때문에이걸 조건으로 사용한다 #전체 코드#include #include #include using namespace std;typedef long long ll;int main() { ..
https://www.acmicpc.net/problem/32867 #문제 간단 정리 약간 시뮬레이션 같은 구현 #문제 해결 방법 우선 문제에서 나온데로 순서대로 건반을 쳐야되기때문에 우측값과 좌측값을 따로 관리해서K 가 넘으면카운트를 해주는 식으로 그리디한 방식으로 구현해주면 된다 #전체 코드#include #include #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector whites(n); for (int i = 0; i > whites[i]; } i..
https://www.acmicpc.net/problem/24041 #문제 간단 정리이분탐색(매개변수 탐색) #문제 해결 방법 범위 관리를 잘 해줘야 되는 문제 같다 우선 x가 범위가 매우 넓으니 매개변수 탐색으로 logn 을 사용하고 각각 세균의 개수를 확인하면 O(n) 인데정렬을 한 후에 최대 k개를 총합에서 제거한다고 생각하면n log n 이라 이분탐색 + 정렬이라log n * nlogn 정도로 생각 할 수 있는데 세균의 범위는 대략 2e9 (20억 정도)각 n의 s*max(1,x-L) 합 최악의 경우 N=1 G=1e9 , S:1, L 1e9로S * max(1, x - L) 1 * (x - 1e9) x - 1e9 x x의 범위는 2e9이다 n의 범위는 20만이니 시간복잡도는 충분하다 #전체 코..
