dh_0e

임계경로 (백준 1948번) DAG(방향 비순환 그래프)를 항상 만족하는 상황에서 최장거리를 구하는 문제. 풀이 과정처음엔 다익스트라 스타일로 최장 거리를 구하는 스타일로 풀어서 AC를 받았지만, 분명 $O(MlogN)$인데 시간이 너무 오래 걸렸다.다익스트라 느낌으로 prique를 써서 역방향 탐색하며 역추적을 위해 _next 벡터에 다음 node를 저장하면서 진행했는데, 생각해보니 어짜피 모든 간선을 탐색해야 하는데 굳이 prique를 써서 사용해야 하나 싶었다.이후, 위상정렬을 이용해 dp로 풀었더니 $O(M+N)$으로 시간을 많이 단축시킬 수 있었다. 다익스트라 스타일 ($O(MlogN)$)#include#include#include#includeusing namespace std;struct d..

오아시스 재결합 (백준 3015번) 보자마자 히스토그램 문제가 생각나서 스택으로 풀어보려다가 너무 뻔한 것 같아서 정렬, 이분 탐색으로 풀어봤다. 시간 초과 코드($O(n^2)$)vector의 insert 연산이 $O(n)$이라는 것을 까먹고 짰다가 시간 초과를 받은 코드키 순서대로 정렬한 다음 벡터에 이진 탐색으로 키와 index를 삽입하면서 좌, 우에 나보다 더 큰 수가 있으면 dap++ 해준다.똑같은 수가 연속적으로 삽입될 경우, 개수를 세어 "$kC2$ + $k$(왼쪽에 나보다 큰 수가 존재할 경우) + $k$(오른쪽에 나보다 큰 수가 존재할 경우)"를 더해주었다.제미나이를 사용해 이를 세그먼트 트리로 구현하여 $O(nlog^2n)$으로 줄여서 제출해 봤지만 시간 초과가 나왔다.n이 최대 500,..

전설 (백준 19585번) 총 13번의 오답을 받으며 오랜만에 머리 터질 정도로 시간 복잡도, 공간 복잡도 둘 다 생각하게 하는 문제였다. 풀이 과정Trie 자체를 최적화(재귀 >> 동적으로)하여 시간을 줄이면서, 동시에 Trie와 unordered_set을 함께 사용해서 시간, 메모리 둘 다 잡아 AC를 받을 수 있다. Trie를 잘 구현하여 최적화하고 set만 적절하게 사용하면 쉽게 풀리는 문제인데, 그 과정까지 시행 착오가 필요하다. 메모리 초과 코드 (Double Trie)#include#include#include#include#includeusing namespace std;stack st;struct Trie { bool finish; Trie* next[26]; Trie() :finish(..

벽 부수고 이동하기 4 (백준 16946번) dfs/bfs 기반으로 발상만 잘하면 쉽게 풀 수 있는 문제 풀이 과정먼저 빈 공간들을 분리하여 크기를 구한다(find 함수).vi 배열로 visit 체크해주는 동시에, 각 빈 공간들이 어떤 집합에 속했는지(set_num) 저장set_cnt 배열에 각 집합마다 빈 공간의 크기를 저장이후, 벽마다 상하좌우에 빈 공간이 있다면 해당 공간이 속한 집합의 빈 공간 크기(set_cnt)를 불러와 해당 벽이 부서졌을 때 만들어질 공간 크기(hap)에 저장한 후 출력한다(get 함수).빈 공간끼리 같은 집합에 속할 수 있기 때문에, set_vi 배열로 집합끼리 visit 체크를 해주어야 함hap % 10으로 출력할 것#include#include#includeusing n..

전깃줄-2 (백준 2568번) A or B 전봇대 중 하나를 기준으로 선택하여 정렬하고, 나머지 전봇대 배열의 LIS(가장 긴 증가하는 부분 수열)를 구하면 되는 문제. 발상이 생각보다 쉬워서 가장 긴 증가하는 부분 수열 5(백준 14003번)를 풀어봤다면 금방 해결 가능하다. 풀이 과정우선, n이 100,000 이하의 자연수이므로 LIS를 이분 탐색을 사용하여 $O(nlogn)$로 구현하여야 한다.if (vec[vec.size() - 1] vector를 만들어 다음 수가 vector에 들어있는 모든 값보다 크다면 수열의 맨 뒤에 추가해 준다.else{ .. }while(st그렇지 않다면 이분 탐색으로 해당 수보다 작은 수의 바로 다음 순서를 찾는다.vec[en]=d[i].first;다음 순서로 수열에..

아기상어 (백준 16236번) 오랜만에 푸는 생구현 문제(시뮬레이션). BFS로 탐색하면서 문제 조건을 모두 충족시켜야 한다.처음에 접근을 잘못해서 cost 값을 안 넣고 distance() 함수를 만들어 각 좌표의 거리 차이만큼을 cost로 이용하다가 잠깐 잊고 있던 "자신보다 큰 물고기는 지나가지 못한다는 조건"이 생각나서 2000자 이상 되는 코드에서 꾸역꾸역 cost를 집어넣어 수정했다. 역시 접근을 애초에 잘하거나 코드를 읽기 쉽게 짜지 않으면 디버깅이나 수정할 상황이 올 때 고생이다. bfs 돌리면서 문제 조건만 잘 구현해준다면 n 최댓값도 20이기 때문에 어렵지 않게 풀 수 있다.pair 남용을 하다가 이후에 구조체를 집어넣은 코드라 queue가 좌표 큐와 cost 큐로 분리되어 있다.. 오..