문제 링크 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 주어진 조건에서 B의 크기가 매우 크기 때문에 단순히 구현을 할 경우 시간 초과가 난다. 이럴 경우 연산을 쪼개는 분할 정복 알고리즘을 활용해야 한다. def square(matrix, n): if n == 1: return matrix temp = square(matrix, n // 2) if n % 2 == 0 : return multi(temp, temp) else : return m..
알고리즘
문제 링크 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 풀이 음의 가중치가 존재하는 그래프 문제이므로 다익스트라보다는 벨만 포드를 사용해야합니다. 이 문제는 벨만 포드 알고리즘의 기초 개념만을 담은 문제입니다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불..
문제 링크 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 문제처럼 route 배열을 따로 두고 이동경로를 매번 저장하는 방식이었습니다. route를 갱신하며 할당하기 때문에 문제가 없을 줄 알았으나 메모리 초과로 인해 실패했습니..
문제 링크 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 풀이 최소비용 구하기 문제가 최소 비용만을 출력하는 것이었다면, 이 문제에서는 최소 비용으로 도착점에 가는 루트에 있는 모든 노드를 출력해야 합니다. 이를 위해, 이동 경로에 있는 노드들을 저장할 route라는 2차원 배열을 선언하였습니다. route배열에서 현재 노드에 대한 인덱스값은 현재 노드까지 이동하기 위한 최소 비용 루트에 포함된 노드 배..
문제 링크 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이 한 지점에서 다른 특정 지점까지의 최단 거리를 구하는 문제로 heapq를 통한 다익스트라 알고리즘을 구현하여 풀이했습니다. from heapq import heappush, heappop import sys input = sys.stdin.readline def dijkstra(start): q = [] distance[start - 1] =..
문제 링크 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 풀이 처음에는 단순히 진실을 아는 사람과 참석 인원 중 교집합이 없는 파티를 구하면 되는 것 아닌가 하고 간단히 생각했습니다. 하지만 그렇게 생각하면 예제 입력 4번부터 출력이 다르게 됩니다. 문제에서 주어진 조건은 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수를 구하는 것이었습니다. 만약, 1번 친구가 진실을 모른다고 1번 친구만 있는 파티에서 거짓말을 했..
문제 링크 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 문제 풀이 한 노드와 다른 노드 사이의 usado가 그 사이의 usado의 최솟값이라는 조건을 보고 처음에는 해당 조건을 활용해서 usado들을 모두 저장해놓고 결과를 구해야하나 했습니다. 그것보다는 bfs를 활용하여 노드를 하나씩 이동하며 usado를 최솟값으로 갱신하고 k보다 usado가 클 경우 결괏값을 1씩 증가시키는 것이 효율..
문제 링크 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 풀이 fun main() = with(System.`in`.bufferedReader()) { val (n, k) = readLine().split(" ").map { it.toInt() } val temperature = readLine().split(" ").map { it.toInt() }.toIntArray() var sum = temperature.slice(..
