728x90 그래프12 [1516] 게임 개발 (JAVA) # 문제 설명 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다. 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는.. 2024. 4. 14. [2252] 줄 세우기 (JAVA) # 문제 설명 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. 출력 첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. .. 2024. 4. 14. [1916] 최소비용 구하기 (JAVA) # 문제 설명 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. .. 2024. 4. 14. [1753] 최단경로 (JAVA) # 문제 설명 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.. 2024. 4. 12. Day-17 다익스트라 1. 다익스트라 알고리즘 그래프에서 출발 노드와 모든 노드 간의 최단 거리를 구하는 알고리즘이다. 시간 복잡도는 O(에지 수 * log 노드 수)이다. 2. 다익스트라 과정 인접 리스트로 그래프 구현 최단 거리 배열을 만들고 출발 노드는 0, 그 외 노드는 무한으로 초기화 최단 거리 배열에서 값이 가장 작은 노드 선택 선택한 노드에 연결된 노드의 값을 Min(선택 노드 최단 거리 값 + 에지 가중치, 연결 노드 최단 거리 값)으로 업데이트 모든 노드가 선택될 때까지 과정 3, 4를 반복 3. 예제 문제 [1753] 최단경로 (JAVA) # 문제 설명 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. .. 2024. 4. 12. [1446] 지름길 (JAVA) # 문제 설명 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오. 입력 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다. 출력 세준이가 운전해.. 2024. 4. 12. Day-16 위상 정렬 1. 위상 정렬 위상 정렬(topology sort)는 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 시간 복잡도는 O(노드 수 + 에지 수)이다. 항상 같은 값으로 정렬되지 않는다. (결과가 다를 수 있음) 2. 위상 정렬 과정 자기 자신을 가리키는 에지의 개수를 나타낸 진입 차수 배열을 생성 진입 차수가 0인 노드를 선택하고 정렬 배열에 저장 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 감소 모든 노드가 정렬 배열에 저장될 때까지 과정 2, 3을 반복 3. 예제 문제 [2252] 줄 세우기 (JAVA) # 문제 설명 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방.. 2024. 4. 12. [1766] 문제집 (JAVA) # 문제 설명 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는.. 2024. 4. 12. Day-15 유니온 파인드 1. Union, Find 연산 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B이다. 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산 노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다. 위 두 연산으로 구성되어 있는 알고리즘이 유니온 파인드이다. 2. 유니온 구현 1차원 배열을 이용하여 유니온 파인드를 표현한다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 2개의 노드를 선택해 union 연산을 수행한다. union(1, 4)의 경우, 4번 노드의 대표 노드를 1번 노드로 하여 연결한다. union(4, 6)의 경우, 6번 노드.. 2024. 4. 10. 이전 1 2 다음 728x90
