본문 바로가기

플래티넘17

[백준 11375] 열혈강호 [Python] 풀이 두 그룹이 있을 때, 모든 간선이 가중치가 1이고 다른 그룹으로만 향하는 그래프를 Bipartite Graph 라고 한다. 이 때, 간선을 통해 다른 정점을 점유한 상태를 matching한다고 하며 Bipartite Graph에 대한 matching을 Bipartite Matching이라고 한다. 즉, 간선의 가중치가 전부 1인 Bipartitle Graph에서 maximun flow을 구해주는 문제는 maximun matching을 구해주는 문제와 동일하다. 때문에 간단하게 DFS를 이용해 O(VE), O((N+M)E) 안에 구현하는 방법을 사용할 수 있다. 최종적으로 연결된 정점을 기록할 match 배열과, 바로 매칭이 되지 않은 경우(다른 정점과 이미 매칭된 경우) 현재 정점을 최종적으로 매칭.. 2023. 6. 14.
[백준 17408] 수열과 쿼리 24 [C++] 풀이 type = 2인 query에 대해 l, r 이 주어지면 l ~ r 범위의 node에 대해 A(i) + A(j)의 결과가 최댓값인 경우를 출력하면 된다. i, j은 문제에서 주어진 l 2023. 5. 26.
[백준 14003] 가장 긴 증가하는 부분 수열 5 [C] 풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"에서 부분 수열의 최대 길이를 lower bound방식으로 빠르게 구했지만, 이렇게 만들어진 임의의 수열들의 요소가 최대 길이를 이루는 요소들이 아님을 예시를 통해 알 수 있었다. 한마디 더 붙이자면, 임시로 생성하는 수열의 최댓값보다 작은 경우에는 lower bound으로 찾은 index위치에 덮어쓰기 때문에 최대 길이를 이루는 요소가 아님을 알 수 있다. 만약 입력받은 요소들이 몇 번째 index에서 덮어쓰기가 되는지 알 수 있다면, 이전의 방법으로 구한 부분 수열의 최대 길이와, 입력받은 요소의 개수 N을 조건에 따라 줄여가면, 요소들을 구할 수 있다. 소스코드 #include #define MAX 1000001 int arr[MAX], te.. 2021. 9. 4.
[백준 14927] 전구 끄기 [C] 풀이 "백준 14939, 불 끄기"와 비슷하지만 행렬의 크기가 다른 문제다. 소스코드 #include #define min(a, b) a = 0 && ny >= 0 && nx < N && ny < N) temp[nx][ny] = (temp[nx][ny] == '1' ? '0' : '1'); } } int main(){ scanf("%d", &N); for (.. 2021. 9. 2.
[백준 14939] 불 끄기 [C] 풀이 주어진 예제는 직관적으로 풀이가 가능하지만 주어질 Test Case들을 고려하면 순차적으로 탐색하면서 풀이해야 한다. 우선 첫 번째 행에서 시도해볼 수 있는 모든 경우의 수를 시도한다면, 2~N번째 행에서는 이전 행의 불을 끄면 된다. N번째 행을 검사해서 불이 전부 다 꺼졌다면 입력된 예제가 모두 불이 꺼진 경우이므로 그때 누른 스위치의 개수들의 최솟값을 저장해 출력해주면 된다. 소스코드 #include #include #include #define min(a, b) a < b ? a : b char bulb[10][10], temp[10][10]; const char* lRow = "##########"; int dx[5] = {0, -1, 1}, dy[5] = {0, 0, 0, -1, 1}; .. 2021. 9. 2.
[백준 11790] Primorial vs LCM [C] 풀이 1부터 N까지의 LCM을 N이하인 소수들의 곱들로 나누면 되는 문제다. N LCM facter result 1 1 1 1 2 2 2 1 3 6 2 1 4 12 2 * 3 2 5 60 2^2 * 3 2 6 60 2^2 * 3 * 5 2 7 420 2^2 * 3 * 5 * 7 2 8 840 2^3 * 3 * 5 * 7 4 9 2520 2^3 * 3^2 * 5 * 7 12 10 2520 2^3 * 3^2 * 5 * 7 12 1~N의 LCM을 구할 때, N이하인 소수들의 거듭제곱으로 구하고 이를, N이하의 소수들로 나누어야 하므로 차수가 2이상인 소수들의 곱이 답이 된다. 때문에, result는 N이하인 소수의 거듭제곱으로 구할 수 있다. 다음과 같은 표를 생각해보자. mol prime 4 2 8 2 9 .. 2021. 8. 31.

티스토리툴바