개구리의 개발 블로그 개구리의 개발 블로그

백준 11375번 열혈강호 파이썬, 네트워크 플로우 출처 - https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 네트워크 플로우 연습하고 싶어서 푼 문제였지만 에드몬드 카프로 풀면 시간 초과가 나온다. 덕분에(?) 이분 매칭을 공부할 수 있었다. 네트워크 플로우에 대한 개념을 알고 있었기 때문에 약간의 힌트만 보고 풀 수 있었다. 1. 풀이 sink 노드와 source 노드 없이 직원과 일 노드만 그래프로 표현한다. match 배열을 통해 ..

백준 2213번 트리의 독립집합 파이썬 출처 - https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 트리에서 DP를 사용하는 문제였다. 독립집합의 크기를 구하는 것은 쉽게 생각할 수 있었다. 백준 트리DP 알고리즘 분류에서 가장 위에 있는 SNS 문제와 거의 유사했다. 경로를 구하기 위해서 따로 추적을 하는 함수를 작성했는데 간단하게 만드는 방법도 존재할 것 같다. 1. 풀이 1. 최대값 구하기 트리의 독립집합에 포..

백준 2208번 보석줍기 파이썬 출처 - https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 까다로운 DP를 풀어보고 싶어서 검색해서 풀었는데 생각보다 쉽게 풀렸다. 투 포인터 생각도 났는데 최댓값을 구해야 되는 문제이기 때문에 일단 구간합부터 구하고 시작했다. 1. 풀이 보석은 반드시 M개 이상 연속해서 주워야 한다. 즉 길이가 M이상인 구간합 중 최대를 찾으면 된다. dp[i][0]에는 현재 보석을 선택하지 않았을 때 최대 구간합을 ..

백준 10211번 Maximum Subarray 파이썬 문제 출처 - https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 쉽고 재밌는 문제다. 흔히들 알고 있는 카데인 알고리즘으로 간단하게 풀 수 있다. 1. 코드 def kadaneSolution(): N = int(input()) A = list(map(int,input().split())) #dp 배열을 따로 만들지 않고 수열에 그대로 덮..

백준 1504번 특정한 다익스트라 파이썬 문제 링크 - https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 특정한 다익스트라 문제다. 1. 풀이 1번 정점에서 N번 정점까지의 최단 경로를 구한다. 이 때 반드시 거쳐야 하는 두 개의 정점이 있다. 해당 정점을 v1,v2라고 하자. 경로의 방향은 1번 정점 → (v1,v2) → N번 정점으로 주어졌으므로 v1을 먼저 방문할 지 ,v2를 먼저 방문할 지만 결..

백준 13549번 숨바꼭질 3 파이썬 BFS 문제 링크 - https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 당연히 백트래킹이겠거니 생각하고 풀었다. 시간 초과에 재귀 오류까지 났지만 가지치기를 조금 더 효율적으로 바꾸는 시도만 계속해서 반복했다. 결국 BFS로 푸는 것을 보고 시도했다. 백트래킹을 항상 쓰려고 하면 안된다. 똑같은 지점에 방문하는 걸 처리하는 것이 까다롭기 때문이다. 1-1. 백트래킹 풀이(오답..

백준 2473번 세 용액 파이썬 투포인터 문제 링크 - https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 다양한 방법으로 풀 수 있다. 2470번 두 용액 문제의 풀이를 활용했다. 다른 테크닉 없이 모든 용액을 하나씩 고정해두고 해당 용액 다음으로 등장하는 용액들만 사용하여 투 포인터를 사용해서 풀면 된다. 1. 풀이 우선 주어진 A 리스트를 오름차순으로 정렬한다. 투 포인터를 처음과 끝에서 시작하여 중간에서 만나면 탐색을 ..

백준 21757번 나누기 파이썬 문제 링크 - https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net 누적합과 dp를 활용하여 풀어야 했는데 dp 점화식을 세우는 것이 생각보다 쉽게 떠오르지 않아서 당황했다. 현재 풀이보다 dp부분을 좀 더 깔끔한 코드로 작성할 수 있을 것 같다. 처음 시도할 때는 구간합 배열에서 크기가 같은 구간이 되도록 나누어주는 divide 함수를 구현하여 풀고자 했다. 즉, 구간합 배열을 2등분..