전체 글

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/9567#번역  #문제 간단 정리 #문제 해결 방법 우선 입력이 들어오면 A번째 축사를 선호하는 몇마리가 들어오는지 알게 되는데 이걸 배열에다가 누적해서 기록을 해두자0 1 2 3 4 5 6 7 8 9 축사가 있으면3번째좋아하는 소가 3마리 6번째 좋아하는 소가 3마리6번쨰 좋아하는 소가 3마리 들어오면  0 1 2 3 4 5 6 7 8 9 :축사 번호0 0 0 3 0 0 6 0 0 0 : 소 누적 배열 이런식으로 누적을 해준 후에목장을 2번 돌면서  cowStack 이란 변수를 선언해주고 (현재 대기하고 있는 소들 누적 변수)누적배열에 소가 잇다면 소를 더해주고(예를들어 i = 3 이고 누적배열[3] 에 소가 0 이상이라면 더해주면 된다) boo..

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/20291  #문제 해결 방법sstream을 사용하자  #전체 코드#include #include #include #include #include #include using namespace std;int main() { int n; cin >> n; map exts; for (int i = 0; i > s; stringstream ss(s); string token; getline(ss, token, '.'); getline(ss, token); exts[token]++; } for (const auto& p : exts) { cout

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만이니 시간복잡도는 충분하다  #전체 코..