결국 오고야 마는 것들

다잌으로 모든 최단 경로를 찾고(길이가 같은 여러개의 최단 경로가 있을수도 있음) 그 경로들을 지운다음 나머지 경로들로 최단 경로를 찾으면 된다. 삽질했던 포인트: 1. 길이가 같은 여러개의 최단 경로를 생각 못함 2. pq에 거리가 같은 경우는 경로만 넣어야 하는데 중복되는 간선을 넣음 (주석으로 표시) 3. 경로를 제거할때 사이클이 있는 경우가 있어서 visited 배열로 중복 방문을 막았어야 함 공식 사이트에 있는 TC로 체크해서 답이 맞는데도 시간초과가 나와서 굉장히 헤맸다... 결국 8트만에 성공... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using ..

혼내주기 2021. 7. 21. 12:12

lis. 개인적으로 이분 탐색보다 세그먼트 트리가 더 이해하기 쉬운 것 같다. 2개의 element를 정렬해서 갯수세는 세그먼트 트리 문제들이 재미있는듯. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const int N = 1 a; arr[i] = {a, i}; } } int query(int l, int r, int i = 1,..

혼내주기 2021. 7. 21. 12:08

꼬인것만 보고 lis인 줄 알았는데 알고보니 inversion counting이었다. 롱롱이도 안써서 또 삽질. 문제를 꼼꼼히 읽는 습관... 문제를 꼼꼼히 읽는 습관... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const int N = 1 a; idx[a] = i+1; } for(int i = 0; i < n; ++i) { ..

혼내주기 2021. 7. 21. 11:00

구간의 맨 왼쪽 전구 색을 c라고 하면, [l,r]구간을 c로 통일시키는 최소 횟수를 구하려고 했다. 그래서 구간을 색 c와 c가 아닌 구간으로 나눠서 재귀적으로 c가 아닌 구간들의 값을 구해서 더하려고 했는데 삽질을 아주 오래 하고 안풀렸다... 결국 sds 특강 강사님의 설명을 듣고 풀었다. 굳이 색에 집착하지 않아도 되었던 것, 그리고 구간을 나누는 것도 n이 200이기 때문에 다 해봐도 되는 것이었다... 아이디어가 완벽하진 않았지만 큰 흐름은 잡았다는데 위안을 삼고 있다 ㅠ dp는 역시 어렵다. 심지어 KOI 초등학교 문제다. 나는 언제쯤 초등학교를 졸업할 수 있을까? #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using names..

혼내주기 2021. 7. 21. 10:55

2차원 배열에서 시작점부터 도착점으로 가는 최소 충격량을 구하는 문제인데, 매번 이동마다 움직일 수 있는 방향이 다르다. 때문에 다잌스트라 dist 배열에 몇번째 이동인지 정보를 추가로 넣어서 돌리면 된다. https://www.acmicpc.net/contest/view/666 5문제 중에서 쓱 읽고 1번과 3번은 풀이가 안떠올라서 스킵하고 2, 4, 5번을 풀었는데, 전부 첫 트라이에 accept되서 기분이 좋다!@ #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx..

혼내주기 2021. 7. 21. 10:05

n개의 선물을 x시간 안에 제작하는데 걸리는 최소 공정의 갯수를 구하는 문제. 선물이 최대 100000개 이기 때문에 1과 100000사이의 공정 갯수를 parametric search로 찾으면 된다. 해당 공정 갯수로 가능한지 확인은 공정 갯수만큼 우큐(minheap)를 만든 뒤 n개의 선물을 다 넣었을 때의 최댓값이 x보다 작거나 같은지 확인하면 된다. 원래 파라메트릭 서치 나오면 항상 +1 -1 하는게 헷갈려서 삽질하는데, 한번에 풀었다. ㅋㅋ #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(..

혼내주기 2021. 7. 21. 09:59

문제 설명에 아주 귀여운 고릴라가 있다. 각 고릴라 이름이 대응하는 정보 우선순위 큐를 해쉬맵으로 만들고, 1번 쿼리의 경우 해당 우큐에 k개의 정보를 넣고 2번 쿼리의 경우 b개 만큼 꺼내면 된다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; unordered_map um; int n; void input() { cin >> n;..

혼내주기 2021. 7. 21. 09:54

사전테스트 후기는 여기에서 볼 수 있습니다. 2주간의 삼성 sds 알고리즘 특강이 끝났다. 요런 주제를 보통 하루에 하나씩 배웠다. 1주차와 2주차의 강사님이 달랐는데, 나는 문제를 풀 때 생각할 시간이 좀 필요한 편이어서 시간을 넉넉하게 주시는 2주차 강사님이 개인적으로 더 좋았다. 일하면서 겪은 썰들이나 사회생활 꿀팁도 주셨다. ㅋㅋ 나는 70~80%는 이미 푼 문제들이어서 안 풀려있는 문제들 위주로 풀고 시간이 남으면 해당 카테고리의 다른 문제들을 찾아서 풀었다. 후반으로 갈수록 플레티넘 문제가 많아서 조금씩 못 따라가긴 했지만, 어거지로 풀고 싶진 않아서 그냥 내 페이스대로 풀었다. 이미 공부한 알고리즘을 복습하거나 생각이 필요한 응용문제를 푸는 시간, 그리고 새로운 알고리즘을 배우는 시간이어서 ..

후기 2021. 7. 19. 21:31