LeetCode

이 문제를 풀기 위해서는 비트마스크 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..

이 문제를 풀기 위해서는 이분 그래프 최대 매칭(Bipartite Matching), 그중에서도 Kuhn Algorithm에 대해서 알아야 한다.Kuhn Algorithm은 이분 그래프에서 매칭의 수를 하나씩 늘려 가는 알고리즘이다. 핵심은 단순히 "빈 자리를 찾는다"가 아니라, 이미 누군가 차지한 자리라도 기존 매칭을 다른 곳으로 옮길 수 있다면 전체 매칭 수를 늘릴 수 있다는 점이다.이 문제에서 남학생과 여학생은 자연스럽게 두 그룹으로 나뉜다.왼쪽 그룹: 남학생오른쪽 그룹: 여학생grid[i][j] === 1: i번 남학생이 j번 여학생을 초대할 수 있음따라서 문제는 "가능한 초대 관계들 중 서로 겹치지 않게 최대 몇 쌍을 만들 수 있는가?"로 바뀐다.1. 접근 : 문제를 단순화 하기문제에서는 m x..

이 문제를 풀기 위해서는 MST(Minimum Spanning Tree, 최소 신장 트리)에 대해서 알아야 한다.Spanning Tree(신장 트리)는 그래프 내의 모든 정점을 포함하는 트리이다.스패닝 트리는 사이클을 만들면 안 되고 n개의 노드를 (n-1)개의 간선으로 연결한다.그리고 이 스패닝 트리를 연결하는 간선에 가중치(strength)가 있을 때 그 가중치의 값을 최소로 구하는 경우가 바로 MST이다.1. 접근 : 문제를 단순화 하기이 문제에서는 노드가 n개 주어지고 각각의 간선이 edges[i]로 주어진다고 했다. edges[i] = [u, v, s, must] 인데 u - v 이어지는 무방향 간선이며 여기에 가중치가 s, 그리고 must가 1이면 필수, 0이면 한 번까지 업그레이드가 가능하다..