devbelly

문제 https://www.acmicpc.net/problem/1028 알고리즘 DP 풀이 2차원 광산이 주어질 때, 광산의 최대 크기를 구하는 문제입니다. 단순하게 브루트포스로 접근한다면 임의의 점을 광산의 최상단으로 잡은 후 네 변이 만들어 질 수 있나 검사를 해보면 됩니다. 모든 점을 최상단으로 검사하기 위해서는 $O(RC)$ 의 시간복잡도가 필요하고 추가적으로 네 변을 검사하기 위해서 선형시간만큼의 복잡도가 더 필요합니다. 위 계산법에서 낭비되는 부분을 줄여야합니다. 최상단 점 (i, j)에서 len 길이를 만들 때 오른쪽 상단변을 계산하는 과정은 (i+1,j+1)에서 len-1 길이를 만들 때 오른쪽 상단변을 계산하는 과정과 겹치게 됩니다. 즉 DP를 이용합시다. $lcache[i][j]$ : ..

문제 https://www.acmicpc.net/problem/3078 알고리즘 구현 풀이 위치가 K+1이상 벗어나지 않으면서 이름의 길이가 같은 쌍의 갯수를 찾는 문제입니다. $N$제한이 30만이므로 $O(N^2)$을 사용해서 순서쌍을 찾기는 어렵습니다. 스택과 비슷한 느낌으로 현재 자신과 같은 길이가 이전에 몇개 있었는지를 기록하여 $O(N)$에 풀도록 합시다. 단 이것을 기록한 배열은 유효한(서로 친구)값만을 유지하기 위해서 위치 차이가 K가 넘어가면 해당 정보를 지우는 업데이트를 하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> K; rep(i, N) {..

문제 https://www.acmicpc.net/problem/2832 알고리즘 fenwick 풀이 감소하는 연속 부분 수열을 reverse를 몇번 해야 오름차순으로 만들 수 있는지 묻는 문제입니다. 주어진 순열중에서 연속한 내림차순이 있다면 해당 부분을 reverse함수를 통해 오름차순으로 만듭니다. 연속 부분 오름차순들이 여러개 만들어졌다면 이들 사이의 경계값은 길이가 2인 내림차순이 존재하게 됩니다. 길이가 2인 내림차순을 reverse하여 오름차순으로 정렬하는 것은 inversion을 counting하는 것과 일치합니다. $N$제한이 10만이므로 펜윅트리를 통해 빠르게 inversion을 세면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ..

문제 https://www.acmicpc.net/problem/2831 알고리즘 sorting 풀이 자신이 선호하는 조건에 따라 매칭할 수 있는 최대 남녀쌍을 묻는 문제입니다. 만일 키가 양수라면 이성의 키의 값이 음수인 사람과 매칭해야하고 반대로 키가 음수라면 이성의 키가 양수인 사람을 매칭해야합니다. 두 경우 모두 동일하므로 남성의 키가 양수, 여성의 키가 음수인 경우만 보겠습니다. 남성의 키가 양수인 배열과 여성의 키가 음수인 배열을 정렬을 합니다. 배열의 앞에서부터 매칭을 시작합니다. 만일 조건이 만족한다면 다음 남녀쌍이 조건을 만족하는지 검사하면 됩니다. 단 조건을 만족하지 않는다면, 현재 매칭되지 않은 남성은 그대로 두고 여성은 다음 여성과 매칭되는지 확인해야합니다. 조건을 만족하지 않는다는 ..

문제 https://www.acmicpc.net/problem/23034 알고리즘 MST 풀이 MST에서 간선을 끊는 문제입니다. 조장끼리는 연락을 할 필요가 없으므로 MST에서 각 조장을 잇는 최대 간선을 끊는 문제입니다. 쿼리가 1만 개 주어지므로 미리 $N$명의 사람마다 $i$에서 $j$로 연락할 때 사용하는 최대 간선을 저장해놓으면 됩니다. 이는 $N^2$에 해결 가능하므로 쿼리마다 MST를 구성하기 위한 최소 cost에서 $dist[i][j]$를 빼주면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i > M; rep(i, M) { cin >> arr[i].u >>..

문제 https://www.acmicpc.net/problem/5899 알고리즘 sweeping 풀이 사각형의 총 넓이를 구하는 문제입니다. 대표적인 스위핑문제입니다. 골드문제여서 $N^2$에 해결할 수 있는 문제입니다. 사각형을 두 개의 선분, 오른쪽 선분과 왼쪽 선분으로 나눕니다. 이후 x좌표를 기준으로 정렬합니다. 왼쪽 선분에 해당하면 set에 넣고 오른쪽 선분에 해당하면 set에서 해당 선분을 제외합니다. set은 지금까지 본 선분들 중에서 아직 넓이를 계산 해야하는 선분들 입니다. 현재 선분과 지금까지 가지고 있는 선분들을 통해 겹치는 y좌표들을 제거하면 중복된 사각형을 제외한 총 넓이를 구할 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i <..

문제 https://www.acmicpc.net/problem/5867 알고리즘 Sorting 풀이 뒤섞인 문장의 가능한 높은 등수와 낮은 등수를 찾는 문제입니다. 가장 높은 등수는 다른 문장들이 거꾸로 정렬되어있을 때, 자신은 정렬된 문장을 통해 순서를 찾는 것이고 가장 낮은 등수는 다른 문장들이 올바르게 정렬되어있을 때, 자신은 거꾸로 정렬된 문장을 통해 순서를 찾는 것입니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { string s; cin >> s; arr.emplace_back(s); sort(s.begin(), s.end()); fi.em..

문제 https://www.acmicpc.net/problem/5909 알고리즘 DP 풀이 주어진 건초더미를 세 개 공평하게 나누는 문제입니다. 이 문제와 매우 매우 유사합니다. $cache[k][i][j]$를 k번째 건초더미까지 분배했을때 i가 B_1, j가 B_2라고 해석하여 가능하다면 1, 불가능하다면 0을 저장하여 풀면 됩니다. 나머지 세 번째 곳간에 저장될 양은 $psum-i-j$를 통해 알아 낼 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { cin >> arr[i]; sum += arr[i]; } cache[0][0][0] = 1..