1516번: 게임 개발첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부www.acmicpc.net- 208ms- 위상정렬선행관계 + 사이클이 없는 방향그래프 ➜ 위상정렬 !!어떤 작업을 수행하기 전 반드시 선행되어야 하는 작업이 존재한다. 작업의 시간과 선행관계가 주어졌을 때, 모든 작업을 완료하기 위해 필요한 최소시간을 구하는 문제이다. ( 비슷한 문제 : BOJ 작업 ) 진입차수 즉, 선행관계가 없거나 모두 완료되어 시작해도 되는 작업들을 우선순위 큐에 넣는다. # 소스코드import java.util.*;imp..
2056번: 작업수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해www.acmicpc.net592ms위상정렬어떤 작업을 수행하기 전 반드시 선행되어야 하는 작업이 존재한다. 작업의 시간과 선행관계가 주어졌을 때, 모든 작업을 완료하기 위해 필요한 최소시간을 구하는 문제이다.선행관계 + 사이클이 없는 방향그래프 ➜ 위상정렬 !!큐를 이용한 위상 정렬 알고리즘진입차수가 0인 모든 노드를 큐에 넣는다.큐가 빌 때까지 다음의 과정 반복큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거진입차수가 0이 된..
1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 144ms 투포인터 단순히 이중 for문으로 풀었을 때, 시간초과가 발생했다. 두 수를 선택해서 푸는 문제이므로 투포인터가 떠올랐다. 1부터 n까지 좋은 수인지 투포인터를 통해 합이 되는 경우가 있는지 탐색한다. left = 0, right = n - 1 을 초기값으로 잡은 후, 1. left 가 arr[i] 이면 오른쪽으로 한 칸 이동 left++ 2. right 가 arr[i]이면 왼쪽으로 한 칸 이동 right-- 3. arr[left] + arr[right] == arr[i] 이면 ..
18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 132ms DP, knapsack N명의 학생들이 가지고 있는 블록으로 H 높이를 만들 수 있는 경우의 수를 계산하는 문제이다. 이 문제의 핵심은 다음과 같다 한 학생당 최대 1개의 블록만 사용가능 블록을 사용하지 않아도 됨 3명의 학생이 다음과 같은 높이의 블록을 가지고 있을 때 높이 1부터 h=5까지 만들 수 있는 경우의수를 생각해보자 2 3 5 3 5 1 2 3 1 2 3 4 5 1 0 1 1 0 1 2 3 첫 번째 학..
9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1484ms # 접근방식 1부터 n까지 팀을 만들 수 있는지 판단한다 핵심은 1 → 2 → 3 → 4 → 5 → 2 가 되면 1은 팀이 될수 없고 2, 3, 4, 5 는 팀이 될 수 있다. 따라서 팀을 만들기 위해 함께 하고 싶은 학생들을 꼬리를 물고 탐색할 때, list에 추가하면서 탐색한다. 1. 다음 확인하는 학생이 list에 포함된다면 그 학생의 index부터는 팀을 만들 수 있다는 의미이다. 따라서 그 전 index 수만큼 팀을 못 만드는 학생이 추가된다. ..
2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 725ms bfs dfs로는 시간초과가 나고 단순 bfs 로 해결할 수 없는 문제이다. 디버깅을 통해 벽을 부수고 이동했을 경우 방문체크와 벽을 부수지 않고 이동했을 경우의 방문체크를 다르게 해줘야 정답이 나온다는 것을 깨달았고 방문체크 배열을 3차원 배열로 선언하여 체크했다. 다음과 같이 벽을 부순 경우와 부수지 않은 경우를 나눠 방문체크 해준다. 벽을 부수지 않고 이동한 경로는 visited[][][0] 벽을 부수고 이동한 경로는 v..
252ms DP 동전은 쪼갤 수 없으므로 0/1 Knapsack 문제로 DP를 이용하여 해결할 수 있다. 입력받은 돈의 합(sum)을 구한 뒤, sum 이 홀수이면 반으로 나누지 못하므로 0 출력. 짝수이면 mid = sum / 2의 값을 동전들로 표현할 수 있는지 확인하면 된다. dp[i][x] : i번째 동전을 사용할 때, x원을 표현하기 위해 사용한 동전의 최소 개수 먼저 사용한 동전의 최소 개수를 구할 것으로 모든 값들을 INF 로 초기화 해준다. i번째 동전으로 x원을 만들 수 있을 때, 사용한 동전의 개수를 저장하고, i+1번째 동전으로 x원을 만드는 dp[i+1][x] 을 0으로 만들어준다. 그렇게 하면 dp 값이 INF 이면 pass , INF가 아니라면 이전 동전 index에서 x원을 만..
11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 532ms 다익스트라 특정노드에서 다른노드까지의 최소 비용을 구하는 문제로 다익스트라 알고리즘을 사용했다. 단, 이 문제에서는 최소 비용뿐만 아니라 출발노드에서 도착노드까지의 최단 경로에 포함되는 노드 또한 출력해줘야 한다. 다익스트라는 많이 해봐서 빠르게 최소비용을 구할 수 있었지만 최단 경로에 포함되어 있는 노드를 찾는 데 어려움이 있었다. 다익스트라 알고리즘에 이전의 노드를 저장해주는 코드를 추가한 후, 경로를 역추적하며 해결..
1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 504ms 그리디 한 개의 회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제로 그리디 알고리즘의 대표적인 문제이다. # 접근 방식 1. 일찍 끝나야 다음 회의를 진행하므로 끝나는 시간을 기준으로 오름차순 정렬한다. 2. 회의 끝나는 시간이 다음 회의 시작 시간보다 작거나 같아야한다. Comparable 인터페이스를 통해 끝나는 시간을 기준으로 오름차순 정렬하며 끝나는 시간이 같을 때는 시작 시간 기준으로 오름차순 정렬을 해준다. import java.io.*; import java.util.*; public class Main { static class Node impl..
그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코테에서의 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다. 거스름 돈 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단 N은 항상 10의 배수입니다. 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면..
1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 192ms 다익스트라 특정 노드에서 모든 노드까지의 최단 경로 계산문제로 다익스트라 구현 구해야 하는 것 go : 1번부터 n번 마을에서 x번 마을로 가는 최단 시간 back : x번 마을에서 1번~n번 마을로 되돌아가는 최단 시간 여기서 1~n번 마을에서 x번 마을로 가는 최단 시간(go)은 입력으로 주어진 to 와 from 을 반대로 저장한 그래프에서 x번을 출발노드로 하고 1번부터 n번노드까지 가는 최단 경로를 계산하는 것과 ..
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 640ms 다익스트라 1부터 N까지 u와 v를 반드시 거치면서 최단 경로를 구해야 하는 문제이다. 다음과 같은 두 가지 경로 중 더 짧은 경로를 선택하면 된다. 1 → u → v → n 1 → v → u → n 입력이 양방향 그래프로 주어지므로 u가 시작노드일 때의 다익스트라, v가 시작노드일 때의 다익스트라를 실행해준다. dijkstra(u); // u를 출발노드로 1, v, n의 최단경로 구하기 startU = d..
