결국 오고야 마는 것들

아이디어를 못 떠올려서 sds 알고리즘 특강 강사님의 아이디어를 보고 구현했다. 투 포인터로 모든 집을 방문할 수 있는 구간의 피로도 최솟값을 구하면 된다. 고도는 1 ~ 1000000의 수이지만 총 지역이 최대 2500개 이므로 해당 고도 내에서만 투 포인터로 찾으면 된다. 시간복잡도는 bfs가 O(n2)이고 투 포인터가 O(n2)으로 총 O(n4)가 된다. 이런 문제는 몇번만 더 풀어보면 점점 아이디어가 보일 것 같다. #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 ..

혼내주기 2021. 7. 22. 10:48

처음에 무지성 완탐으로 시도했다가 TLE. 이리저리 식을 써보다가 n, m이 주어졌을 때 만들수 있는 단어가 n+m+1​Cm​개임을 발견해서 풀었다! 좀 더 똑똑했으면 문제 특성을 보고 떠올렸을텐데, 무작정 쓰다가 발견해서 운이 좋았던 것 같기도 하다. #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}; ll cache[205][205];..

혼내주기 2021. 7. 22. 10:47

어이없게 홀짝으로 해당 칸을 몇번 방문했는지 계산하는 것 까지 다 해놓고, N번째를 도착점을 어떻게 계산할지 몰라서 찾아봤다... (x, y)번째 칸은 (x-1, y)칸과 (x, y+1)칸의 방문 횟수의 합인걸 이용해 dp로 n-1번 산책했을 때의 상태를 저장해놓고 n번째는 경로에 맞게 따라가면 된다. dp문제를 별로 안좋아하는데 이번 문제는 뭔가 재미있었다. 나 의외로 dp를 좋아할지도??... #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, ..

혼내주기 2021. 7. 22. 10:44

오랜기간 못 푼 상태로 외면하다가 결국 풀었다. 아무리 봐도 우선순위 큐를 쓰지 않고 풀 수 있는데, 계속 틀려서 삽질을 굉장히 오래했다. pq로도 바꿔보고 여러가지 삽질을 하다가 결국 인접행렬이 잘못 된것을 찾아서 인접리스트로 바꾸고 통과했다!@ 뭔가 오래된 때를 벗겨낸 기분이라 기분이 좋다!@ #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,..

혼내주기 2021. 7. 22. 10:43

이번 카카오 인턴 코테 4번 문제랑 비슷하다고 추천받았던 문제. 풀면서 그때 못푼게 너무 아쉽게 느껴진다. 충분히 풀 수 있었는데... 비트마스크로 어떤 열쇠를 들고있는 상태인지를 포함해서 bfs를 돌리면 된다. 비트마스크가 뭔지 모른다면 이 글을 참고해보자!! #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}; struct state {..

혼내주기 2021. 7. 22. 10:42

2021 카카오톡 채용연계형 인턴쉽 코딩테스트 3번 문제. doubly linked list 클래스를 구현하고 스택을 이용해 복구하는 부분을 넣어줘서 풀었다. 그땐 세그먼트 트리를 몰라서 이렇게 풀었는데, 지금 다시 풀게 된다면 k번째 수 세그로 풀 것 같다. #include #include #include #include #include using namespace std; struct node { int idx; node* prev; node* next; node(int i) { idx = i; next = NULL; prev = NULL; } }; struct doublyLinkedList { node* head; node* tail; stack history; doublyLinkedList() {..

혼내주기 2021. 7. 22. 10:40

2021 카카오톡 채용연계형 인턴쉽 코딩테스트 4번 문제. 비트마스크 + 다잌스트라로 풀면 된다. 함정 상태에 따라서 어떤 경우를 pq에 넣을지 조금 헷갈렸는데, 정방향인 경우 0번이나 2번 함정이 발동된 경우, 역방향인 경우 1번만 함정이 발동된 경우에만 다잌스트라를 이어가면 된다. 분기 때문에 생각보다 다시 풀어도 헷갈렸다... 그래도 뭔가 맺힌 한을 푼 기분! 5번은 아직도 어려워서 더 강해지면 풀어야겠다. #include using namespace std; using pii = pair; struct state { int from, dist, bit; state(int ff, int dd, int b) { from = ff, dist = dd, bit = b; } bool operator s.d..

혼내주기 2021. 7. 22. 10:39

끔찍한 구현 문제. 최대 깊이가 10이기 때문에 총 경우의 수가 410으로 완전탐색으로 풀 수 있다. 물론 캐쉬를 적용하면 훨씬 빨리 답을 구해낸다. #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}; struct state { pii R, B; int d; state(pii r, pii b, int dd) {R = r, B = b, d ..

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