https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제이해 첫 번째 입력으로 N M 이 주어지고 N 은 총과목수를 뜻하고, M은 (특정과목을 듣기 위한 선수과목 번호 , 특정과목 번호) 순서쌍의 개수를 뜻한다. 예를 들어 3 2 2 4 1 2 와 같이 입력이 주어진다면, 들어야 할 과목은 총 3과목이며, 특정과목을 듣기 위한 선수과목 번호 , 특정과목 번호) 순서쌍의 개수는 2개이다. 첫 번째 행에서 2 4의 뜻은 4번 과목을 듣기 위해서는 2번 과목을 먼저 들어야 한다는..
https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제이해 해당 문제는 위상정렬 알고리즘을 사용하는 대표적인 문제이다. 첫 번째 행에서 주어진 N은 가수팀의 개수이며, M 은 보조 PD 인원수이다. 두 번째 행 이상부터는 첫 번째 열은 해당 보조 PD 가 담당한 팀의 개수를 의미하고, 두 번째 열 이상부터는 가수들의 출연순서가 나오게 된다. 알고리즘 분석 해당 문제도 다른 위상정렬 문제처럼 아래와 같은 순서를 따라 풀이하면 된..
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제이해 해당 문제는 위상정렬 알고리즘을 사용하는 대표적인 문제이다. 첫 번째 행에서 주어진 N 은 줄을 세워줄 총 학생수이다. 첫 번째 행에서 주어진 M 은 키를 비교할 횟수를 의미한다. 위의 예제처럼 첫 번째 행에 3 2 가 주어지면, 줄 세울 학생은 총 3명이며, 비교할 횟수는 2회이다. 두 번째 행부터는 비교를 수행한다. A B -> 이런 식으로 ..
https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 이해 첫 번째 행은 N 개의 건물을 지정해 주는 숫자이다. 두 번째 행부터는 첫 번째 열은 해당 건물을 만들기 위해 걸리는 시간을 뜻한다. 그리고, 두번째 이상 열부터는 해당 건물을 만들기 위해 선행되어야 하는 건물 번호이다. 위의 예제에서 보면 2번째 건물의 행을 보면 10 1 -1 로 되어있다. (-1은 입력이 끝났다는 표시로 이해하면 된다.) 2번째 건물을 짓기 위해서는 최소..
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 이해 주어진 2-dimension array에서 가장 큰 정사각형의 넓이를 구해주는 문제이다. 문제에서 주어진 예시에서 가장 큰 정사각형의 넓이는 2 x 2 = 4라고 할 수 있다. 그럼 과연, 알고리즘적으로 어떻게 설계해야 가장 큰 정사각형을 찾을 수 있을까? 일단 아래와 같이 해당 이중배열에서, 특정 원소를 M(i, j) 라고 해주자. 그럼 아래와 같은 점화식을 통해서, 가장 큰 정사각형의 한 변의 길이를 찾을 수 있다. [ 단, 아래의 점화식은 M(i,j)..
https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 어떤 시간에 어떤 위치에 있어야 자두를 최대한 많이 받을 수 있는지 계산하는 문제이다. 해당 문제도 동적계획법 문제로 풀면 해결이 된다. 일단 예제에서 제시한 예시를 기준으로 어떻게 6개라는 숫자가 나오는지 확인해보자. 여러가지 경우의 수가 있겠지만 대표적으로 두개의 경우의 수가 있다. 다른 경우의 수를 조합해봐도 최대 6개 초과의 자두를 받을수는 없으므로 최대 자두 획득 개수는 6개가 된다고 할 수 있다..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 합분해 문제이다. 해당 문제를 이해하기 위해서 간단한 예시를 들어보자. 만약 N = 4, K= 2 인 경우를 생각해보자. 그럼 숫자 4를 0~4 의 숫자로 두개를 합해서 만들어야 하는 경우의 수를 구하면 된다. 그럼 아래와 같은 순서쌍이 나오게 된다. (0,4), (4,0), (3,1), (1,3), (2,2) 위와 같이 5개의 순서쌍이 나와서 5개가 답이된다. 그럼 이제 일반화 가정을 거쳐보자. (0,4), (4,0), (3,1), (1,3), (2,2) 위와 같이 순서쌍을 뽑는다고 가정했을 경우에 4 = x + r 이라..
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 해당 문제는 다이나믹 프로그램을 사용하는 대표적인 문제이다. 일단 문제의 핵심은 아래와 같이 요약할 수 있다. 1. 판다는 상,하,좌,우 로 이동이 가능. 2. 지금 자리보다 숫자가 클때만 이동이 가능. 3. 어떤 지역부터 판다를 풀어놔야 최대한 많은 타일을 이동하는지 알고싶음 (첫번째 타일에 풀어놓는 순간 count는 1이 됨) 이해를 위해 아래 그림을 참고하자. 아래와 같은 숲이 있..
https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 해당 문제는 다익스트라 알고리즘을 사용하여 해결하는 문제이다. 일단 문제는 아래와 같이 두 분류로 나눌 수 있다. 1. 첫째 노드로 시작해서 V번째 노드로 끝나는 최단거리 D1 2. 첫째노드로 시작해서 P 노드를 지나서 V 번째 노드에 도착하는 최단거리 D2 그런데 여기서 D2 의 경로는 두개의 경로로 나눌 수 있다. D2_1 = 첫째노드로 시작..
https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 해당 문제는 다익스트라 알고리즘을 사용하는 문제이다. 아래의 그림을 보며 이해해보자. 1 노드를 시작해서 4 노드로 가는 방법은 총 3가지 방법이 존재한다. 1) 1-> 4 로 바로 이동하는 방법이 존재한다. 해당 길을 이용하면 distance 는 15가 된다. 2) 1-> 2 -> 4 로 이동 하는 방법이 존재한다. 해당 경로를 이용하면 ..
