1. 문제 설명 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 이게 원래 플래4였나..? 문제는 기억나는데 등급이 이렇게 높았다는 게 당황스럽다. 2. 아이디어 최대 유량 문제를 풀 듯이 풀 수도 있지만 난 그냥 dfs를 사용해서 풀었었다. 솔직히 지금까지도 최대 유량 알고리즘은 유령 간선 개념을 이해했다는 확신이 안 생겨서 껄끄럽다. dfs를 이용한 풀이는 제법 단순하다. 한 번에 최적의 경우를 탐색하기 보다는 일단 소를 차례로 배정할 수 있는..

1. 문제 설명 https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 아이디어를 떠올리지 못 해서 구글링하긴 했었지만, 이 문제를 풀 때가 전역한지 얼마 안 된 때라 행렬의 개념을 다 잊어먹어서 더 고생했었다. 2. 아이디어 행렬을 이해해야 한다. 그러면 dp와 분할 정복으로 풀이할 수 있다. (다르게 풀이한 사람이 있을까 싶어 찾아봤는데 못 찾겠다.) 입력 정보를 받은 행렬과 단위 행렬을 각각 하나씩 만든다. a1 a2 a1 a11 a12 a2 a21 a22 여기서 행렬은 이동 횟수라는 개념으로 쓸 수 있다. 위의 표와 같은 어떤 정점과 간선 정보를 담은 행렬 ..

1. 문제 설명 https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 진짜 처음 보는 알고리즘이었는데 너무너무너무 어려웠다. 하루 온종일 이것만 보다가 너무 화나서 그냥 알고리즘과 흐름을 전부 외워버렸더니 오히려 좀 이해가 되는 기분. 2. 아이디어 에드몬드 카프 알고리즘이라고 최대 유량에서 곧잘 쓰이는 유명한 알고리즘이다. 정점을 알파벳으로 주기 때문에 ASCII 코드값을 참조해 값을 다루어야 한다. (man ascii) 그러면 일단..

1. 문제 설명 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 아이디어 내 방법이 너무 노가다가 심해서 다른 풀이를 찾아봤더니 피사노 주기라는 게 존재한다고 한다. 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. www.acmicpc.net 하지만 코테 도중에 이렇게 모르는 개념 나온다고 서칭할 수 있는 것도 아니니 모르는 개념이 나왔을 때 해결할 수 있는 방법을 연구하는 것도 중요하..