[Silver I] 곱셈 - 1629문제 링크성능 요약메모리: 11512 KB, 시간: 68 ms분류분할 정복을 이용한 거듭제곱, 수학제출 일자2024년 11월 20일 05:17:50문제 설명자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.입력첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.출력첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.  제출 코드이 문제는 A, B, C의 숫자가 굉장히 클 수 있다는 점을 고려해야한다.시간제한은 0.5초인데 for문을 그냥 사용하면 최악의 경우 2,147,483,647번 돌아야 하므..

[Gold V] 최소비용 구하기 - 1916문제 링크성능 요약메모리: 56844 KB, 시간: 512 ms분류데이크스트라, 그래프 이론, 최단 경로제출 일자2024년 11월 19일 03:29:38문제 설명N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.입력첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 ..

[Gold IV] 최단경로 - 1753문제 링크성능 요약메모리: 124632 KB, 시간: 768 ms분류데이크스트라, 그래프 이론, 최단 경로제출 일자2024년 11월 19일 02:54:46문제 설명방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 ..

[Gold IV] 거짓말 - 1043문제 링크성능 요약메모리: 18832 KB, 시간: 196 ms분류자료 구조, 분리 집합, 그래프 이론, 그래프 탐색제출 일자2024년 11월 16일 04:39:32문제 설명지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히,..

[Silver II] 알고리즘 수업 - 깊이 우선 탐색 1 - 24479문제 링크성능 요약메모리: 168284 KB, 시간: 1148 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색, 정렬제출 일자2024년 11월 14일 20:40:17문제 설명오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.df..

[Silver II] 알고리즘 수업 - 너비 우선 탐색 1 - 24444문제 링크성능 요약메모리: 172676 KB, 시간: 1188 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색, 정렬제출 일자2024년 11월 14일 20:55:56문제 설명오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.bf..

[Gold IV] 여행 가자 - 1976문제 링크성능 요약메모리: 22312 KB, 시간: 248 ms분류자료 구조, 분리 집합, 그래프 이론, 그래프 탐색제출 일자2024년 11월 14일 04:14:09문제 설명동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.도시들의 개수와 도시들 간의 연..

[Gold IV] 수들의 합 4 - 2015문제 링크성능 요약메모리: 40288 KB, 시간: 420 ms분류자료 구조, 해시를 사용한 집합과 맵, 누적 합, 트리를 사용한 집합과 맵제출 일자2024년 11월 14일 03:51:00문제 설명A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N..

[Gold V] 집합의 표현 - 1717문제 링크성능 요약메모리: 91408 KB, 시간: 3024 ms분류자료 구조, 분리 집합제출 일자2024년 11월 12일 03:42:39문제 설명초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.입력첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가..