dynamic programming

이 문제를 풀기 위해서는 후위 순회(postorder traversal)와 트리 DP에 대해서 알아야 한다.각 노드에서 자식들이 만들어 둔 최적의 값을 받아 현재 노드의 값을 계산한다. 다만 이 문제에서는 부모에게 넘길 값과 전체 정답 후보가 서로 다르다는 점이 핵심이다.0. 필요한 개념 먼저 정리하기0-1. 경로와 후위 순회트리의 경로는 인접한 노드를 간선으로 이어 만든 노드의 나열이다. 같은 노드를 두 번 지날 수 없고, 루트를 반드시 포함할 필요도 없다. 따라서 어떤 노드에서 왼쪽 자식으로 내려갔다가 다시 그 노드를 거쳐 오른쪽 자식으로 내려가는 형태도 하나의 유효한 경로다.현재 노드에서 최선의 값을 계산하려면 왼쪽과 오른쪽 서브트리의 결과가 먼저 필요하다. 자식을 먼저 처리하고 부모를 나중에 처리..

이 문제를 풀기 위해서는 비트마스크 DP에 대해서 알아야 한다.배열의 길이가 최대 16이기 때문에, 각 원소를 썼는지 안 썼는지를 하나의 비트마스크로 표현할 수 있다. 그리고 어떤 원소들을 이미 사용했는지 알 수 있으면, 지금 만들고 있는 부분집합의 합이 목표값에서 어디까지 차 있는지도 계산할 수 있다.0. 필요한 개념 먼저 정리하기먼저 이 문제의 목표는 k개의 부분집합을 만드는 것이다. 모든 부분집합의 합이 같아야 하므로, 전체 합을 k로 나눈 값이 각 부분집합의 목표 합이 된다.예를 들어 nums = [4,3,2,3,5,2,1], k = 4라면 전체 합은 20이고 각 부분집합의 목표 합은 5다. 따라서 (5), (4,1), (3,2), (3,2)처럼 모든 그룹이 합 5로 끝나야 한다.여기서 중요한 전..

이 문제를 풀기 위해서는 비트마스크 DP에 대해서 알아야 한다.비트마스크는 여러 개의 참/거짓 상태를 하나의 정수로 압축하는 방법이다. 이 문제에서는 필요한 스킬의 개수가 최대 16개이므로, 각 스킬을 비트 하나에 대응시키면 어떤 팀이 가진 스킬 조합을 숫자 하나로 표현할 수 있다. 그리고 그 숫자를 DP의 상태로 쓰면, "이 스킬 조합을 만들 수 있는 가장 작은 팀"을 차근차근 갱신할 수 있다.0. 필요한 개념 먼저 정리하기먼저 비트마스크부터 보자. 예를 들어 필요한 스킬이 ["java", "nodejs", "reactjs"]라면 다음처럼 위치를 정할 수 있다.java -> 0번 비트nodejs -> 1번 비트reactjs -> 2번 비트그러면 ["nodejs", "reactjs"]를 가진 사람은 11..