Victoree's Blog

Concept & Idea 이 문제는 트리의 노드가 중간에 사라지면, 그 트리 하단부를 제외한 나머지 노드의 리프노드 수를 구하는 문제이다. 처음에 생각을 잘못해서 전체 노드의 리프 노드 수를 구하고, 사라진 노드의 리프노드 수의 차로 결과를 냈는데, 그렇게 하면 문제가 있다. 만약 특정 노드가 사라졌을 때, 루트노드도 리프 노드가 되는경우! 이다 그 부분만 수정해서 풀까 했는데,, 사실 deleted_node 자체를 탐색하지 않음으로 Dfs 함수 한번으로 해결 할 수 있는 문제였다. 인접 행렬에서 deleted_node가 들어있으면, 해당 노드는 탐색하지 않고, 나머지 리프 노드들의 수를 누적해서 해결할 수 있다. Dfs 를 Void 함수로 작성해서 많이 풀곤 하는데, Int 를 반환하는 함수로 누적합..

Concept & Idea 간단히 재귀함수로 구현할 수 있는 문제였다. 완전 이진 트리이기 때문에 입력은 당연히 2^k-1만큼 들어올것이다. 전체 리스트의 left, right의 중간 지점 녀석이 현재 depth의 루트인 녀석이다. 재귀함수를 구현할 때, 가장 먼저 해야할 점은 해당 함수의 인자와 종료 조건을 결정하는 것이다. 종료조건은 보통의 이진탐색 로직의 모습과 거의 유사하다. 그 이후엔 어떤 순서로 이 함수를 다시 호출할지 적어주면 된다. 이 문제에서는 트리의 출력이 좌측부터이기 때문에 그냥 왼쪽부터 재귀하도록 구현했다. Code #include #include #include using namespace std; vector result[10], input; void make_tree(int d..

Concept & Idea 나무자르기 문제를 내가 직접 풀어냈다는 느낌이 약해서 리뷰를 쓰지 않았다. 이 문제는 이분탐색으로 가장 인접한 두 공유기의 최댓값을 찾는 문제였다. 처음에는 이분탐색으로 설치를 하는 방식을 짜야한다고 생각했고, 어떻게 적절한 위치에 설치를 할지 우선순위를 잡아야하나 고민하였다. 하지만 그 어떤 우선순위에도 확실한 과정이 없어서, 질문검색을 통해 아이디어를 찾았다. 중요한 점은 내가 직접 구간을 설정해서 이 구간이 가능한지 여부를 판단하고, 이분탐색으로 이 구간을 정해나가는 것이다. mid라는 구간만큼 공유기를 설치했을 때, 설치가 가능하면 mid값을 더 키우고 불가능하면 더 줄여서 최적의 값을 이분탐색으로 찾아나가는 것이다. 여기서 가능한지의 여부는 그냥 count를 세면 됬었..

Concept & Idea 문제 접근을 어떻게 할까 하다가 앞에 요소를 체크하려 했는데, 결국 과거의 값을 되돌아 생각해보는 것으로 생각해보니 해결되었다. row가 0일 경우에, row가 1이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다.row가 1일 경우에, row가 0이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다. DP배열에는 누적으로 최대값을 쌓아가고, 최종적으로 마지막 col의 최댓값을 출력하면 해결되는 문제였다. Code #include using namespace std; int t; int map[2][100001]; int cnt=0; int dp[2][100001]; int main() { cin>>t; for(int i=0; i..