4Legs_Archives

문제 링크 : www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 그리디 알고리즘으로 해결이 가능한 활동 선택 문제이다. 핵심은 각 문제들을 어떤 기준으로 정렬할 것인지(즉, 어떤 문제의 우선순위를 높게 잡을 것인지)이다. ① 우선 당연히 받을 수 있는 컵라면의 갯수가 많은 문제를 우선적으로 풀어야 할 것이다. 하지만 위와 같은 상황에서, 보상이 8개인 문제를 먼저 풀게 된다면 데드라인이 1인 문제 하나를 풀 수 없게 된다. 보상이 8인 문제는 데드라인이 3이기 때문에 ..

문제 링크 : www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 평소에 전공지식 공부를 병행한 사람이라면 무언가 번뜩할 것이다. 이 문제는 페이지 교체 알고리즘에 빗대어 설명할 수 있기 때문이다. [OS/운영체제] 페이지 교체 (Page Replacement) - (2) FIFO (First-In, First-Out) Page Replacement FIFO는 가장 단순한 페이지 교체 알고리즘으로, 메모리에 옮겨진 메모리들 중 가장 오래된 페이지를 Victim으..

문제 링크 : www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 이 문제가 그리디 알고리즘으로 해결할 수 있다는 것을 캐치한다면, 일반적으로는 더 자릿수가 큰 수의 앞 자리 알파벳부터 큰 수를 부여하는 식의 접근을 할 것이다. 하지만 이러한 접근의 경우 각종 예외 케이스들을 관통하는 하나의 코드를 구현하기 매우 까다롭다. 예를 들어 ABC와 BB 9개, 총 10개의 단어에 대해 A = 9, B = 8, C = 7 이라면 987 + 88 * 9 = 1,77..

문제 링크 : www.acmicpc.net/problem/1602 1602번: 도망자 원숭이 첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다. 그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴 www.acmicpc.net 문제에서 쿼리 형식으로 출발, 도착 노드에 대한 최소 시간을 묻고 있으므로, 모든 노드에 대해 다른 모든 노드까지의 최단경로를 구하는 플로이드-와샬 알고리즘이 적절할 것이다. 다만 도시 별 괴롭힘 시간이라는 별도의 가중치가 존재하는데, 멍멍이는 원숭이가 지나는 경로 중 가장 괴롭힘 시간이 긴 도시에서 괴롭히게 된다. 다만, 플로이드-와샬 알고리즘을..

문제 링크 : www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 문제를 그래프의 관점에서 이해하면 다음과 같다. ① 서로 연결된 사람은 같은 위원회에 참석한다 = 그래프에서 연결된 노드들은 같은 위원회(그룹)로 취급한다. ② 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다. = 그래프의 모든 정점에 대해 그룹화한다. 즉 그래프의 모든 정점에 대해 연결된 노드끼리 그룹(위원회)으로 묶은 후, 그룹의 대표 노드에 대해 다른 모든 노드에 대한 전파 시..

문제 링크 : www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 플로이드-와샬 문제라는 것을 캐치하는 것이 문제 해결의 80%는 되는 것 같은 문제이다. 각 물건들의 무게 관계를 그래프의 형태로 이해하고, 문제에서 요구하는 것이 그래프의 각 노드에서 도달할 수 없는 노드들의 갯수이므로 모든 노드에서 다른 모든 노드로의 최단거리를 구하는 플로이드-와샬 알고리즘이 적절함을 캐치해야 한다. 플로이드-와샬 알고리즘(Floyd-Warshall ..

문제 링크 : www.acmicpc.net/problem/2593 2593번: 엘리베이터 첫째 줄에는 N과 M이 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 M줄에 걸쳐 엘리베이터 번호 순서대로 Xi와 Yi가 빈 칸을 사이에 두고 주어지며, 마지막 줄에는 A와 B가 주어진다. N은 100,000이하, M www.acmicpc.net 문제를 그래프의 관점에서 이해하는 것이 중요한 문제이다. 문제에서 층은 최대 10만개, 엘리베이터의 갯수는 최대 100개이므로 BFS를 적용할 때 층이 아닌 엘리베이터를 기준으로 해야 함을 캐치할 수 있다. (BFS의 시간복잡도는 일반적으로 O(V^2)이다.) 문제에서 제시된 예제를 통해 설명하자면, 아래와 같은 엘리베이터 상황을 4층에서 7층으로 이동 가능, 7층에서 12층..

문제 링크 : www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 벨만-포드 알고리즘에 대한 전반적인 이해가 필요한 문제이다. 이 문제를 막힘없이 해결할 수 있다면 벨만-포드를 잘 이해했다고 볼 수 있을 것이다. 기본적으로는 (도로를 지나며 사용하는 비용 - 도시에 도착해서 벌 수 있는 비용) 을 간선의 비용으로 두는 그래프에 대해 벨만-포드 알고리즘을 적용해 문제를 풀면 된다. (즉 수익의 최대화는 가중치의 최소화가 된다.) 하지만 문제의 조건에서 gg는 오..

문제 링크 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만-포드 알고리즘을 이해하고 연습해볼 수 있는 문제이다. 벨만-포드 알고리즘에 대해서는 다음 포스트를 참조하자. 벨만-포드 알고리즘(Bellman-Ford Algorithm) [서론] 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 출발하여, 다른 모든 정점에 대한 최단경로를 구하는 알고리즘이다. (다익스트라 알고리즘..

문제 링크 : 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 다익스트라 알고리즘을 적용해 각 정점에 대한 K번째 최단경로의 가중치 합을 구하는 문제이다. 일반적인 다익스트라 알고리즘에서는 우선순위 큐(최소 힙)에서 pop되는 순간 그 정점에 대한 최소 가중치 합은 고정된다. (다익스트라 알고리즘 참조 : 4legs-study.tistory.com/21) 다익스트라 알고리즘은 기본적으로 최단거리를 구하..