Byeo

목차 개요 설명 코드 개요 어떤 tree가 주어졌을 때, 임의의 node에서 자신 혹은 자식 노드들 중에서 하나만 선택하면서 그 선택의 비용의 최솟값은 얼마인가를 구하는 문제입니다. 이 문제는 Tree DP인데, 특정 노드를 선택하는 Tree DP 특징 중에 하나로는 자신의 노드가 선택 되었는지, 안되었는지 구분해서 구하는 문제가 많습니다. 각각의 배열을 dpYes (dpYes[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택 되었을 때 그 비용) dpNo (dpNo[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택되지 않았을 때 그 비용) 로 구분하여 구하면 되겠습니다. 이 때, dpYes는 자식들을 순회하면서 min(dpYes[child], d..

목차 개요 설명 한계 코드 개요 해당 문제는 배열이 주어져 있을 때, 특정 부분의 구간 합을 구하는 문제입니다. 눈여겨 볼 것은 배열이 주어지고 난 뒤, 배열 값이 변하지 않는다는 사실입니다. 이 문제는 첫 index부터 마지막 index까지 부분합을 모두 계산한 뒤, 결과를 저장해서 빼기 연산으로 쉽게 풀 수 있습니다. 즉, DP 문제입니다. 설명 5 3 5 4 3 2 1 1 3 2 4 5 5 백준 예제로 방법을 간단하게 보겠습니다. 배열의 원소 5, 4, 3, 2, 1로 들어온 값을 arr에 저장해 둡시다. 그리고 0번 ~ i번 까지의 배열 합을 sum[i]에 저장해 놓도록 하죠. 처음 sum[0] 은 단순히 arr[0]이 되겠죠. 이제 다음부터 sum[1]은 arr[1] + sum[0], ... s..