백준

문제 링크 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 풀이 입력이 [1, 2, 3]의 형태로 들어오기 때문에, 이를 파싱해서 deque에 넣어 사용했습니다. nums = deque(input().rstrip()[1:-1].split(',')) 단순한 구현으로 풀면 풀리는 문제이지만, 정답률이 낮은 이유는 시간 초과에 있었습니다. 본 문제는 시간제한이 1초입니다. 파이썬에서는 1초에 약 2000만번의 연산이 가능합니다. pop 연산은 O(1)의 시간복잡도이므로 큰 문제가 없지만, revers..

문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 풀이 import heapq n, m = map(int, input().split()) indegree = [0] * (n + 1) graph = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) indegree[b] += 1 ..

문제 링크 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 풀이 import heapq nums = [] result = 0 n = int(input()) for _ in range(n): heapq.heappush(nums, int(input())) while len(nums) > 1: n1 = heapq.heappop(nums) n2 = heapq.heappop(nums) heapq.heappush(nums, n1 + n..

문제 링크 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 문제 풀이 음의 가중치가 존재하는 그래프 문제이므로 다익스트라보다는 벨만 포드를 사용해야합니다. 이 문제는 벨만 포드 알고리즘의 기초 개념만을 담은 문제입니다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불..