프알문
[백준] 11266번 - 단절점 (Articulation Point)
이 문제의 유형은 깊이 유형 탐색을 통해 절단점을 찾는 것이다. 절단점이란? - 무향그래프에서 어떠한 점의 인접한 간선들을 모두 지웠을 때 -> 해당 Component가 2개로 나뉠때의 어떤한 점이 절단점 ● 어떠한 점이 절단점이 될 수 있을 조건 - 2가지 1) 기준점이 u일때 자손 v들이 역방향 간선을 통해 u의 선조들로 올라갈 수 있을 때 if (!root && subtree >= discovered[here]) { isCutVertex[here] = true; } subtree = isCutVertexDfs(there, false) 의 의미는 현재 점의 역행 간선이 존재 할 때 자신의 선조 어느 곳까지 올라 갈 수 있는지 보여준다. 따라서 subtree는 discovered를 저장하기 때문에 su..
[백준] 1725번 히스토그램 & [프알문] 울타리 잘라내기
이번 문제는 1725번 히스토그램인데, 프알문의 울타리 잘라내기 문제와 풀이 방식이 똑같아 포스팅하였습니다. 울타리 잘라내기와 마찬가지로 이 문제를 브루트포스로 접근하게 되면 시간복잡도가 너무 높으므로 분할 정복으로 접근하였습니다. 지금부터 울타리를 반으로 쪼개며, 확장을 하면서 분할 정복을 할 것입니다. 먼저 기저사례를 기본적인 분할 정복에서의 기저사례와 같은 left==right일시 기본 높이 값을 반환해주며, 그 후 left~mid, mid+1~right로 나누어 계산을 할 것입니다. 먼저 반으로 쪼개가며 확장을 시키면 모든 케이스를 확인 할 수 있습니다. 그렇기 때문에 반으로 쪼개가는 것이고, 확장을 시킬 때 왼쪽으로 갈지 오른쪽으로 갈지는 더 높은 케이스를 찾아가도록 설정을 해주었습니다. #in..