dh_0e

오아시스 재결합 (백준 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 큐로 분리되어 있다.. 오..

비숍 (백준 1799번) N-Queen 문제와 동일하게 백트래킹으로 해결해야 하는 문제지만 런타임을 더 줄여야 한다.모든 경우의 수를 탐색하면, k를 nxn 체스판에서 최대로 들어갈 수 있는 비숍의 개수라 놓고 시간 복잡도가 $O(2^k)$가 나올 것이라 예상했다. 10x10 체스판에 최대로 놓을 수 있는 비숍의 수(k)가 18개라 $2^{18}$은 10억을 넘지 않기 때문에 10초 안에 풀 수 있을 것 같았지만 발상 오류였다. 실제론 $O(2^{n*n})$ 풀이 과정결국 정해를 찾아보고 문제를 해결했다. 시간을 줄일 수 있는 방법은 $n$x$n$ 체스판을 흑, 백 2개의 $(n/2)$x$(n/2)$ 체스판으로 분할하여 각각 백트래킹을 수행하여 구한 최대로 놓을 수 있는 비숍의 개수를 합치는 것이었다. ..