문제 링크 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 전체 예제 테케에서는 무게가 무거운 보석이 더 비싼 가격이지만, 무게가 가벼운 보석이 더 비쌀 수도 있습니다. 간단한 예를 들어, 가방의 수용 무게 : 10 20 보석의 무게/가격 : 10/40 20/30 단순하게 넣을 수 있는 보석 중 최대 가격을 가지는 보석부터 순차적으로 넣는다고 해봅시다. 이 경우에 어떤 가방..
전체 글
문제 링크 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 풀이 from collections import deque def bfs(x, y): queue = deque() queue.append((x, y)) while queue: now_x, now_y = queue.popleft() for dir in range(4): next_x, next_y = now_x + dx[dir], now_y + dy[dir] if 0
문제 링크 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 풀이 import sys input = sys.stdin.readline from collections import deque n, k = map(int, input().split()) queue = deque([n]) cnt = 0 result = 0 visited = [0] * 100001 while queue: now = queue.pop..
문제 링크 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] =..