1. 문제https://www.acmicpc.net/problem/1028입력으로 주어진 $R \times C$ 크기의 2차원 격자에서, 가장 큰 다이아몬드 광산의 크기를 구하는 문제이다. 2. 접근지난 번 해결한 백준 1641번과 접근이 비슷하다는 느낌을 받았다.따라서 풀이는 다음의 순서로 진행했다.격자의 각 칸마다 좌상-우하 대각선 방향으로 1이 얼마나 연속되는지 저장한다. 우상-좌하 대각선 방향에 대해서도 저장한다.격자의 모든 칸에 대해, 해당 칸이 다이아몬드 광산의 아래쪽 꼭짓점이 될 때 만들 수 있는 다이아몬드 광산의 최대 크기를 구한다. (1) 대각선 방향으로 연속한 1의 개수 세기1번 단계를 수행하기 위해 $R \times C$ 크기의 2차원 배열 lu 를 선언하여, lu[x][y] 를 $(..
baekjoon
1. 문제https://www.acmicpc.net/problem/1641알파벳 대문자로 이루어진 $N \times N$ 크기의 행렬이 주어지면, 직각 이등변 삼각형과 이등변 삼각형의 총 개수를 출력하는 문제이다. 2. 접근 1 - 이등변 삼각형 (a)의 개수(a) 모양에 해당하는 이등변 삼각형은 방향에 따라 다음 4가지로 구분할 수 있다. A A AAA AAA AA AA AA AA AAA AAA A A 이 중에서 첫 번째 모양을 어떻게 구할지 생각해보자.memo1[x][y] 를 $(x, y)$ 위치가 우하단 꼭짓점인 첫 번째 모양 삼각형의 개수로 정의하자. 간단한 예시들을 통해 살펴보면 다음과 같은 사실을 차례대로 발견할 수 있다.$(x, y)$ 위치, $(..
1. 문제https://www.acmicpc.net/problem/2673평면 위에 있는 원의 둘레에 100개의 점이 일정한 간격으로 존재한다. 각 점은 1번부터 100번까지 시계 방향으로 번호가 붙어 있다.이 점들을 끝점으로 하는 N개의 현이 주어질 때, 서로 교차하지 않는 것들을 최대한 많이 찾아서 그 개수를 출력해야 한다.단, 각 점은 많아야 한 현의 끝점이 될 수 있다. 2. 접근 및 풀이주어진 원에서 1번 점과 100번 점 사이를 잘라서 직선으로 평평하게 보니까, 문제를 해결하기가 더 쉬워졌다.결국 얼마 전에 올린 백준 3012번 올바른 괄호 문자열 문제와 접근법이 유사하다는 생각이 들었다. memo[j][i] 를 j 번부터 i 번까지의 구간에서 가능한 최대 개수로 정의한 다음, 길이가 짧은 구..
1. 문제https://www.acmicpc.net/problem/3012소괄호, 중괄호, 대괄호, 물음표로만 이루어진 문자열이 입력으로 주어진다. 이때 해당 문자열의 물음표를 괄호로 적절하게 바꿔서 만들 수 있는 올바른 괄호 문자열의 수를 출력해야 한다.단, 개수가 다섯 자리를 넘어가는 경우에는 마지막 다섯 자리만 출력해야 한다. 2. 접근가장 먼저 n 이 홀수라면 올바른 괄호 문자열을 만들 수 없으므로 이 경우에는 0을 출력하고 바로 종료해주었다.int main() { FASTIO; int n; string s; cin >> n >> s; if (n % 2 == 1) { cout 이제 모든 [시작 인덱스, 종료 인덱스] 구간에 대해 올바른 괄호 문자열의 개수를..
0. 들어가기 전에공부한 내용을 간략하게 정리하는 느낌으로 작성한 글이다. 1. 디닉 알고리즘 (Dinic's Algorithm)최대 유량 문제를 더 빠르게 해결하기 위해 등장한 알고리즘이다.에드몬드-카프 알고리즘의 시간 복잡도가 $O(VE^2)$이었다면, 디닉 알고리즘은 $O(V^2 E)$로 동작한다고 한다. 그러면 어떻게 더 빠르게 동작할 수 있었을까?핵심 아이디어는 다음과 같다.현재 그래프에서 BFS를 통해 각 정점의 레벨을 구한다. 이를 통해 레벨 그래프를 만들어서, 레벨이 증가하는 모든 흐름을 찾을 수 있게 한다.레벨이 증가하는 방향으로만 DFS를 수행하면서, 가능한 모든 유량을 추가한다. 에드몬드-카프 알고리즘에서는 증가 경로를 한 번 찾을 때마다 BFS를 수행한다. 반면 디닉 알고리즘에서는 ..
0. 들어가기 전에최대 유량 문제, 포드-풀커슨 알고리즘, 에드몬드-카프 알고리즘에 대해서는 이미 잘 설명된 글들이 많기 때문에, 공부한 내용을 간략하게 정리한다는 느낌으로 남겨보려고 한다. 1. 최대 유량 문제 (Maximum Flow Problem)소스 정점과 싱크 정점이 정해진 방향 그래프가 주어지는 상황에서, 소스 정점에서 싱크 정점으로 흐를 수 있는 최대 유량을 구하는 문제이다. 여기서 소스(source), 싱크(sink), 용량(capacity), 유량(flow)라는 개념이 등장한다.소스(source) 정점은 유량을 발생시킬 수 있는 정점이고, 싱크(sink) 정점은 유량을 흡수하는 정점을 의미한다. 그 외 정점들에서는 유량을 발생시키거나 흡수할 수 없으며, 자신이 받은 유량만큼 다시 흘려보내..
1. 파도반 수열 2 문제파도반 수열 2 문제는 다음의 링크에서 확인할 수 있다.https://www.acmicpc.net/problem/27435 파도반 수열 1 문제와 비교했을 때, 입력으로 주어지는 $N$의 최댓값이 $10^{18}$로 늘어났다는 차이가 있다. 제한이 커지면서 정답도 모듈러 연산을 적용하여 구하도록 변경되었다. 2. 문제 풀이(1) 파도반 수열의 점화식파도반 수열의 점화식은 다음과 같다.$P_i = P_{i - 2} + P_{i - 3}\ (i \ge 4),\ P_1 = P_2 = P_3 = 1$$P_i = P_{i - 1} + P_{i - 5}\ (i \ge 6),\ P_1 = P_2 = P_3 = 1,\ P_4 = P_5 = 2$ 이 두 점화식이 왜 같은지는 이전 글에서 간단하게..
1. 파도반 수열 문제예전에 풀었던 백준 파도반 수열 문제의 다른 풀이를 듣게 되어서 다시 한번 살펴봤다. 백준 파도반 수열 문제는 다음 링크에서 확인할 수 있다.https://www.acmicpc.net/problem/9461 2. 파도반 수열의 점화식주어진 그림을 뚫어지게 쳐다보면 다음과 같은 점화식을 발견할 수 있다. 둘 중 하나만 발견해도 문제를 해결하기에는 충분하다.$P_i = P_{i - 1} + P_{i - 5}\ (i \ge 6),\ P_1 = P_2 = P_3 = 1,\ P_4 = P_5 = 2$$P_i = P_{i - 2} + P_{i - 3}\ (i \ge 4),\ P_1 = P_2 = P_3 = 1$ 3. 두 점화식이 진짜로 같은가?그런데 위의 두 점화식이 같다는 것이 신기하게 느껴..
1. 펜윅 트리(Fenwick Tree)펜윅 트리(Fenwick Tree)는 주로 수열의 구간 합을 빠르게 구하기 위해 사용되는 자료 구조이다.바이너리 인덱스 트리(Binary Index Tree)라고도 불리며, 줄여서 BIT라고도 한다. 2. 누적 합 VS 펜윅 트리예를 들어, 주어진 정수 배열 arr 에 대해 arr[i] 부터 arr[j] 까지의 구간 합을 반복적으로 구하는 문제를 가정하자.누적 합을 이용하면 주어진 정수 배열 arr 로 누적 합 배열 prefix_sum 을 미리 구해놓은 후, 각각의 쿼리에 대해 단 1번의 연산만으로 답을 구할 수 있다. ( prefix_sum[j] - prefix_sum[i - 1] ) 그러나 기존 정수 배열에서 구간 합을 구하는 쿼리가 들어오면서, 중간중간 기존 ..
1. 문제 링크https://www.acmicpc.net/problem/17242 2. 문제 요약가중치가 2종류인 그래프가 주어질 때, 0번 정점에서 N-1번 정점까지 지나는 경로 중 (지나는 모든 간선의 가중치 1의 합) * (지나는 모든 간선의 가중치 2의 합)의 최솟값을 찾는 문제였다.단, 가중치의 합은 각각 1000 이하여야 한다는 조건이 있다. 3. 풀이 접근우선 다익스트라 알고리즘을 활용했는데, 가중치 1을 기준으로 두어서 더 작은 가중치 1로 방문할 수 있는 정점부터 차례대로 탐색해주었다. 이때 같은 정점에 대해 더 큰 가중치 1과 더 작은 가중치 2로 방문하여 최솟값이 갱신되는 경우가 누락될 수 있다는 문제가 있다. 따라서 이미 탐색이 이루어진 정점에 대해서는, 가중치 2가 더 작아지는 경..
