https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 난이도 : 골드 5 태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 설명 한 시간대에 동시에 진행중인 강의가 몇 개인지 체크하는 문제입니다. 가장 처음 든 생각은 아무래도 int 배열을 체크해놓고 하나씩 체크해볼까? 생각했지만, 시작, 끝 시간의 범위 (0 ≤ Si < Ti ≤ 109)를 보고 바로 다른 방법을 고민하였습니다. 아무래도 우선순위 큐를 사용해 그리디적으로 풀 수 있을 것 같네요. 위와 같이 그림으로 그려 나타내면 쉬울 ..

https://www.acmicpc.net/problem/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net 난이도 : 골드 1 태그 : 그리디, 기하학 설명 다소 삽질을 좀 했던 문제였습니다. 가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균이 최소가 되는 좌표 가장 먼 편의시설까지의 거리는 잘 모르겠지만, 가장 가까운 편의시설까지의 거리는 사실 계산을 하는 로직이 필요하지 않습니다. 바로 편..

https://www.acmicpc.net/problem/17142 난이도 : 골드 3 태그 : 그래프 이론, 브루트 포스, 그래프 탐색, 너비 우선 탐색 설명 연구소 시리즈 3번째 문제입니다. 해당 문제는 크게 1. 입력 2. 바이러스 m개를 고르는 조합 (DFS를 사용한 브루트포스) 3. 바이러스 퍼뜨리기 (BFS) 으로 나눌 수 있겠습니다. 입력값을 받을 때, 바이러스의 위치를 저장 및 빈 공간을 카운트 한 뒤, 이를 DFS을 사용해 바이러스를 m개 고르고, bfs로 바이러스를 퍼뜨립니다. 소스코드 값 입력 import java.util.* import kotlin.collections.ArrayList data class Virus(val x: Int, val y: Int) lateinit var..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 그래프 탐색, 너비우선탐색, 시뮬레이션, 깊이우선탐색 설명 삼성 기출 문제로 유명한 마법사 상어 시리즈 중 '마법사 상어와 파이어스톰' 문제입니다. 시뮬레이션 문제로써, 1. 파이어스톰을 n번 시전 2. 모든 파이어스톰 시전 후 가장 큰 덩어리 찾기 크게 두 파트로 나눌 수 있습니다. 파이어스톰 시전 과정은 단순 구현이지만 모든..

https://www.acmicpc.net/problem/2355 2355번: 시그마 첫째 줄에 두 정수 A, B가 주어진다. (-2,147,483,648 ≤ A, B ≤ 2,147,483,647) www.acmicpc.net 난이도 : 브론즈 2 태그 : 수학, 사칙연산 설명 A 부터 B 까지의 합을 구하는 문제이지만, 단순히 for문을 사용해 구할 경우 시간초과가 납니다. (-2,147,483,648 ≤ A, B ≤ 2,147,483,647) A, B의 범위가 매우 크기 때문이죠. for문을 사용해 구하게 될 경우 매우 많은 연산을 수행하게 될 수 있습니다. 그렇다면 어떻게 해야 할까요? 힌트는 문제 제목에 있습니다. 1부터 n까지의 합을 구하는 유명한 공식이 하나 있습니다. 위 공식을 사용한다면 적..

https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 난이도 : 브론즈 3 태그 : 수학, 구현 설명 매 입력을 받을 때 마다 최대, 최솟값을 업데이트하는게 핵심입니다. 단, 입력 범위가 -1,000,000 ~ 1,000,000 까지 주어지므로, 최솟값의 초기값을 1,000,000으로, 최댓값의 초기값을 -1,000,000으로 지정하는게 포인트입니다. 각각의 경계값으로 설정하면 최소한 한 번은 갱신이 일어나기 때문..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 난이도 : 골드 3 태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 설명 과제는 마감일이 있고, 과제 하나를 끝내는 데에는 하루가 걸립니다. 과제를 풀 때마다 각기 다른 점수를 얻을 수 있을 때, 점수의 최댓값을 구하는 문제입니다. 어려운 것 같지만 천천히 접근해봅시다. 최댓값을 구하려면, 어떤 숙제를 해야 할까요? 바로 점수가 높은 숙제부터 하는 것입니다. 그럼 숙제를 언제 해야 할까요? 각 숙제는 마감일 안에 언제든지 하면 됩..

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 이름 처럼 깊이 우선 탐색 (DFS, Depth First Search)의 연습문제 입니다. 그래프를 탐색하는데는 여러 방법이 있습니다. 그 중 꽤 유명한 탐색방법인 DFS를 연습해봅시다. DFS는 트리 or 그래프에서 최대한 깊이 탐색한 ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 깊이 우선 탐색 설명 첫째 열에서 시작해 서로 교차하거나 중첩되지 않으면서 마지막 열로 가는 경로를 찾는 문제입니다. 1번 예제 같은 경우는 최대 두 가지 경로를 그릴 수 있습니다. 2번 예제 같은 경우는 아래와 같이 최대 5개의 경로(파이프 라인)이 있습니다. 파이프라인은 왼쪽에서 오른쪽 방향으로 놓을 수 있으며, 오른쪽 대각선 위, 오..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 난이도 : 실버 2 태그 : 이분 탐색, 매개 변수 탐색 설명 절단기를 H 높이로 했을 때, 그 위의 나무는 모두 잘립니다. 꼭 필요한 만큼의 나무만 가져가되, 적어도 M미터의 나무를 집에 가져가고 싶을 때, 절단기의 높이의 최댓값을 구하는 문제입니다. 이진 탐색(이분 탐색)을 응용할 수 있겠는데, 이진 탐색에 기반한 매개 변수 탐색(Parametric Se..