답은 알고리즘 뿐이야!

문제 출처 : www.acmicpc.net/problem/1525 풀이 : BFS 문제입니다. 메모리 제한이 24메가로 작습니다 그렇기에 9개의 칸을 0~8의 값인지 9차원 배열로 판단할 시에 메모리 초과가 뜨게 됩니다. 그렇기에 [3][3] 배열을 long long 형 변수에 매핑시켜 그 값을 중복 체크 하시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/16978 풀이 : 세그먼트 트리 문제입니다. K번째 1번 쿼리가 진행 되었을때의 A[i] ~ A[j] 구간합을 구하는 문제인데, 세그먼트 트리 자체에 K번째 까지의 진행사항을 저장하기에는 너무 많은 메모리를 요구하기 때문에 다른 방안을 찾아야 합니다. 그래서 우리는 쿼리를 모두 받아놓고 K번째 1번쿼리

문제 출처 : https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 �� www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 아래의 그림처럼 격자를 체스판처럼 나눠서 Source -> 빨간색 영역 -> 사방의 하얀색 영역 -> Sink 이런식으로 모델링 해 주시면 가로 세로 블럭에 대한 모델링은 완성입니다. 그 다음 최소 연산 횟수를 구해야 하는데 위의 모델링으로 구할 수 있는 연산 횟수는 " 둘다 양수인 격자에 대한 최소 ..

문제 출처 : https://www.acmicpc.net/problem/2365 2365번: 숫자판 만들기 입력의 첫째 줄에는 행(열)의 크기 N이 주어진다(1≤N≤50). 둘째 줄에는 N개의 정수가 주어진다. 주어지는 정수는 1행부터 N행까지의 합을 차례대로 나타낸다. 셋째 줄에는 N개의 정수가 주어진다 www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 아래의 그림 처럼 행과 열을 각 각 묶어서 모델링 하여 1번행 3번열을 묶으면 (1,1), 1번행 4번열을 묶으면 (1,2) 이런식으로 표현 될 수 있도록 모델링 합니다. 그 후 문제 조건에 따라 최대 숫자의 값을 최소로 하는 형태를 찾아야합니다. 이는 모든 엣지의 Capacity에 대해 Limit을 1 ~ 1000까지 걸어 ..

문제 출처 : https://www.acmicpc.net/problem/1760 1760번: N-Rook 첫째 줄에 격자의 크기를 나타내는 두 자연수 N, M이 주어진다. 격자가 N행 M열로 이루어져 있다는 의미이다. (1 ≤ N, M ≤ 100) 둘째 줄부터는 격자의 모양을 나타내는 정보가 한 줄에 한 행씩 주어 www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 0 : 빈 격자 1: 구덩이가 파인 격자 2: 벽이 놓인 격자 2020/09/03 - [알고리즘/백준문제풀이] - [BOJ 2414] 게시판 구멍 막기 [BOJ 2414] 게시판 구멍 막기 문제 출처 : https://www.acmicpc.net/problem/2414 2414번: 게시판 구멍 막기 첫째 줄에 N, M..

문제 출처 : https://www.acmicpc.net/problem/2414 2414번: 게시판 구멍 막기 첫째 줄에 N, M(1 ≤ N, M ≤ 50)이 주어진다. 다음 N개의 줄에는 M개의 문자로 게시판의 모양이 주어진다. 각각의 문자는 붙어 있으며, 구멍이 없는 부분은 '.', 구멍이 있는 부분은 '*'으로 주어진다. www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 구멍이 없는 부분에는 테이프를 붙이면 안되므로 행과 열에 대해 구멍이 연속적으로 있는 부분을 묶어서 인덱스를 만들어 주시고 구멍이 있는 부분의 좌표(y,x)에 대해 행과 열의 인덱스를 Capacity가 1로 이어 주시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/5651 5651번: 완전 중요한 간선 입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1

문제 출처 : https://www.acmicpc.net/problem/10319 10319번: 좀비 아포칼립스 문제 때는 2020년, 당신과 그 일행은 좀비로 황폐화된 대도시의 어느 마을 안에 갇혔다. 당신들 또한 바이러스에 감염되었기 때문에 좀비가 되기 전에 빨리 병원을 찾아 치료해야 한다. 당신들은 www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 소스와 싱크를 만들어 소스 -> 시작장소, 병원 -> 싱크로 연결해 줍시다. 각 엣지 별로 단위 시간에 통과할 수 있는 사람 수, 걸리는 시간에 대한 정보를 추가적으로 활용해야합니다. 저는 Flow에 대한 정보를 단위시간별로 쪼개서 단위 시간에 통과할 수 있는 사람 수와 현재 시각에 통과한 사람 수를 계산하여 경로를 탐색하였습니..

문제 출처 : https://www.acmicpc.net/problem/13505 문제 풀이 : Trie 문제입니다. 각 수를 비트로 쪼갠뒤 비트가 0인지 1인지에 대해 판단을 하여 높은 자리 수 부터 Trie를 구성하시면 됩니다. 아래는 예제 1번을 간략하게 Trie로 구성한 그림입니다. 위의 그림은 간략히 그린 것이고 실제로는 31자리 부터 시작해야 합니다. Trie를 구성했으면 이제 가장 큰 XOR 값을 구해야합니다. XOR값이 가장 크기 위해서는 이러한 생각을 할 수 있습니다. 어떠한 수에 대해 Trie 에서 제일 큰 자릿수 부터 반대 비트를 찾아 내려 간다면 그 수에 대해 가장 큰 XOR값을 가진 수를 찾을수 있다! 위의 그림에 색깔펜으로 그린 부분이 위의 로직을 1과 2에 대해 실행했을때의 결..

문제 출처 : https://www.acmicpc.net/problem/2449 문제 풀이 : DP 문제입니다. cache[L][R] : L번째 전구부터 R번째 전구까지 통일 시키는데 색을 바꾼 최소횟수 양쪽 구간의 색을 통일 시킬때 변수를 하나 두시고 양쪽 구간의 시작 색깔이 같다면 바꾸는 비용을 0으로, 다르다면 바꾸는 비용을 1로 계산하여 쌓아가시면 됩니다.