문제 : https://www.acmicpc.net/problem/1916   문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.입력첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스..

문제 :  https://www.acmicpc.net/problem/11659  문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.제한1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N예제 입력 1 5 35 4 3 2 11 32 45 5예제 출력 11291나의 풀이import sysinput = sys.stdin.readlinen, m = ma..

문제 : https://www.acmicpc.net/problem/1987   나의 풀이 (시간 초과)import sysinput = sys.stdin.readlineR, C = map(int, input().split())board = [[_ for _ in range(C)] for _ in range(R)]for i in range(R): alp = input() for j in range(C): board[i][j] = alp[j]dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def DFS(x, y, visited, count): global max_count max_count = max(max_count, count) for i in ra..

문제 : https://www.acmicpc.net/problem/16953     나의 풀이import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(a, b): q = deque([(a, 1)]) while q: n, cnt = q.popleft() if n == b: return cnt if n * 2  큐를 이용하여 풀 수 있는 문제이다. 가능한 연산을 수행한 값과 연산 횟수를 모두 큐에 저장하여 먼저 리턴되는 값을 답으로 연산의 최솟값을 구할 수 있다.

문제 : https://www.acmicpc.net/problem/1927   나의 풀이import sysimport heapqinput = sys.stdin.readlinen = int(input())heap = []for i in range(n): x = int(input()) if x == 0: if len(heap): print(heapq.heappop(heap)) else: print(0) else: heapq.heappush(heap, x) 시간 초과가 발생해서 sys 모듈을 사용하여 재제출하니 통과하였다.

문제 : https://www.acmicpc.net/problem/1766  나의 풀이import heapqimport sysinput = sys.stdin.readlinen, m = map(int, input().split())first = [[] for _ in range(n+1)]link = [0] * (n+1)for _ in range(m): a, b = map(int, input().split()) first[a].append(b) link[b] += 1hq = []for i in range(1, n+1): if link[i] == 0: heapq.heappush(hq, i)while hq: node = heapq.heappop(hq) print(no..

문제 : https://www.acmicpc.net/problem/12865  DP 점화식을 세우는 것이 어려워서 최근에 DP 문제만 풀고 있는데 아직 접근법을 떠올리기 힘든 것 같다. dp[i]는 배낭의 최대 용량이 i일 때 얻을 수 있는 최대 가치를 의미한다. dp[i - w] + v 은 무게 w인 아이템을 추가하여 무게 i가 되었을 때 새로운 최대 가치를 계산하는 부분이다.max(dp[i], dp[i - w] + v)를 계산해, 현재 아이템을 넣었을 때와 넣지 않았을 때 중 최대 가치를 선택해 dp[i]를 갱신한다.  예를 들어 배낭의 최대 용량이 7일 때, 무게와 가치가 각각 (3, 4), (4, 5), (2, 3)인 아이템들이 있다면  1. dp 테이블을 dp = [0] * (K + 1) # [..

문제 : https://www.acmicpc.net/problem/2156  처음에 제출한 코드는 런타임 에러가 발생하였다.n = int(input())lst = [int(input()) for _ in range(n)]dp = [0] * 10000dp[0] = lst[0]dp[1] = lst[0] + lst[1]dp[2] = max(lst[0] + lst[2], lst[1] + lst[2], dp[1])for i in range(3, n): dp[i] = max(dp[i-3] + lst[i-1] + lst[i], dp[i-2] + lst[i], dp[i-1])print(max(dp[-1]))   n이 3보다 작을 때의 예외 처리를 하여 다시 제출했더니 통과하였다. 나의 풀이n = int(input..