Algorithms

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

지금까지 백준만 풀다가 올해 남은 기간동안에는 구글 킥스타트 문제들을 좀 풀어보기로 했다. 구글 킥스타트는 구글에서 매년 개최하는 알고리즘 대회이다. 전 세계의 수만명이 참가하여 코딩 실력을 겨룬다. 1년에 여러 차례 대회가 열리는데(2020년 기준 한 달에 한 번꼴) 매번 대회가 끝나면 등수가 공개되어서, 객관적인 나의 수준도 판단할 수 있다. 매년 조금씩 바뀌지만 올해는 각 라운드당 3시간동안 네 문제를 푸는 형식으로 진행이 되고 있다. 나는 올해 중반부터 시작했고, 처음이다보니 아직 문제를 막 잘 풀지는 못했다. 그래서 2020년에 출제된 기출문제를 하나씩 풀어보면서 연습하고 그 내용을 블로그에 정리해 보려고 한다. 총 4문제 중에 4번 문제는 못 풀었고, 1~3번 문제만 풀어서 이에 대한 간단한 ..

오늘은 오랜만에 BFS 문제를 풀어보려 한다. 백준 2146번 다리 만들기 문제이다.https://www.acmicpc.net/problem/21462146번: 다리 만들기여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다www.acmicpc.net 이 문제는 엄청 어렵게 느껴지진 않았다. BFS를 익숙하게 쓸 수 있으면 큰 문제 없이 풀 수 있는 문제로 보인다. 다만 BFS를 여러 차례 써야 하는 풀이가 있어서 조금 복잡하게 느껴질 수도 있을 것 같다.BFS에 대해서 간단하게 설명을 하면, 너비 우선 탐색 방법으로 그래프나 트리를 완전 탐색할 수 있는 방법 중 하나이다..