1. 문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 2. 풀이 생각보다 굉장히 어려웠던 문제였다. 이 문제의 핵심은 "현재 탐색중인 수업의 시작 시간이 다음 수업 시작 시간보다 작거나 같으면 같은 강의실을 배정할 수 있다" 이다. 주요 자료 구조 PriorityQueue pq : 배정한 수업이 들어가있는 우선순위 큐 List lessonList : 수업 리스트 우선 수업을 리스트에 넣고 수업 시작 시간을 기준으로 오름 차순 정렬하고 수업 시작 시간이 같다면 종료 시간을 기준으로 오름 ..
1. 문제 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 2. 풀이 주어지는 카드 순열의 값이 양수만 주어지기 때문에 "큰 수 + 큰 수"를 하면 큰 수가 나올 수 밖에 없다. 따라서 작은 수 + 작은 수를 해야 최소가 나온다. 만약 일반 배열 및 리스트를 활용하여 문제를 해결한다면 카드를 오름차순 정렬한다. 앞에서 2개를 제거하고 이 두 개의 카드를 더한 값을 2번 add 한다. 이 두 과정을 반복해야 ..
1. 문제 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 2. 풀이 문제에서 주어진 행동은 총 3가지이다. 주식 하나를 산다. 원하는 만큼 주식을 판매한다. 아무것도 하지 않는다. 이 문제를 틀리는 대부분의 경우는 그리디적인 접근을 해서 틀리는 경우일 것이다. 그리디적인 접근 방법은 주가의 최대치에서 다음날 떨어진다면 현재 날짜에 기존에 구입했던 주식을 판매하는 것이다. 그러나 이는 최대 이익을 볼 수 있는 방법이 아니다. 올바른..
1. 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 풀이 간선의 가중치가 10이하인 자연수이고 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제이기 때문에 다익스트라로 문제를 해결할 수 있다. 만약 다익스트라 코드를 작성하는 것이 아직 어렵다면 "최소 비용 구하기" 문제를 먼저 풀어보자 https://sorryday.tistory.com/84 [BOJ] 백준 1916 - 최소비용 구하기..
1. 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 2. 풀이 기본적인 다익스트라 알고리즘에 한 가지 아이디어를 추가하면 해결할 수 있는 문제이다. 이 문제의 핵심 포인트는 주어지는 입력의 마지막 줄인 반드시 거쳐야 하는 정점 v1, v2이다. 그렇다면 생각해볼 수 있는 것은 2가지가 있다. 1번 노드 -> v1 노드, v1 노드 -> v2 노드, v2 노드 -> N번 노드 1번 노드 -> v..
1. 문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 2. 풀이 DP + 트리 + DFS로 해결할 수 있는 문제. 그래프에 속한 사람은 얼리어답터일수도 있고 아닐 수도 있으며, 얼리어답터가 아닌 사람은 바로 인접한 노드 모두가 얼리어답터일때 아이디어를 받아드릴 수 있다. 이를 바탕으로 DP 식을 작성할 수 있다. dp[i][j] = r (0
1. 문제 https://www.acmicpc.net/problem/1937 2. 풀이 모든 좌표에서 DFS를 실행하면 $O(N^2)$ x $O(N^2)$ -> $O(N^4)$ 으로 시간 초과가 발생 DFS + DP를 이용하여 시간 복잡도를 줄일 수 있다. dp[i][j] = r map의 (i, j)에서 출발했을 때 최대 이동할 수 있는 칸의 개수 = r 판다가 어디에서 처음 풀어놔야 하는지도 정해야 하기 때문에 모든 좌표에서 DFS 함수를 출발시켜야 한다.($O(N^2)$) DFS 함수에서는 다음과 같은 로직을 수행한다. 출발하는 것도 움직인 것으로 보기 때문에 DFS 함수를 실행하면 dp[x][y] = 1을 통하여 움직임을 더해준다. 4방 탐색으로 좌표를 찾고 현재 내 위치의 대나무의 양보다 다음 위..
1. 문제 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 2. 풀이 자두는 현재 1번 자두나무 아래에 위치해있다. 1번 움직인다면 2번 자두나무 아래에 위치하고, 2번 움직이면 1번 자두나무 아래에 위치할 것이다. 이를 일반화한다면 다음과 같다. 짝수번 움직일 경우 : 1번 자두나무 홀수번 움직일 경우 : 2번 자두나무 입력으로 자두가 떨어지는 자두나무의 번호가 주어질 때 나올 수 경우의 수는 어떻게 될까?? 내가 짝수번 움직였을 때 떨어지는 자두의 ..
