728x90 전체 글654 백준 1916번: 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄.. 2022. 7. 27. 최단 경로 알고리즘 예제: 미래 도시 n개의 회사가 있고 m쌍의 회사가 연결되어있다 (양방향으로 연결되어있다) 1번회사에서 출발해 k번 회사를 거쳐 x번 회사까지 가는데 걸리는 최단시간은? 나는 다익스트라 알고리즘을 이용해 풀었다 1에서 출발하여 k까지 가는 최단거리 + k에서 출발하여 x까지 가는 최단거리 라고 생각할 수 있고 다익스트라를 두 번 실행하면 답을 얻을 수 있다 import sys, heapq input=sys.stdin.readline n,m=map(int,input().split()) #노드의 개수n, 간선개수m graph=[[]for i in range(n+1)] for i in range(m): a,b=map(int,input().split()) #서로 연결된 두 회사 a,b graph[a].append(b) graph.. 2022. 7. 27. 최단 경로 알고리즘 예제: 전보 도시가 n개 있고 통로가 m개 있다. c도시에서 메세지를 보낼 건데, 총 몇 개의 도시에 메세지를 보낼 수 있으며 메세지가 도달하는데 걸릴 시간은 어떻게 되겠는가? 노드개수n, 간선개수m, 출발지점 c를 입력받고 c에서 출발하는 모든 최단거리를 계산하고, 최단거리가 INF가 아닌 값들의 개수, 최단거리 중 가장 큰 값을 찾아 출력하면 된다 import sys, heapq input=sys.stdin.readline INF=int(1e9) n,m,c=map(int,input().split()) #노드개수 n, 간선개수 m, 출발지점c graph=[[]for i in range(n+1)] #노드 연결정보를 저장할 그래프 for i in range(m): x,y,z=map(int,input().split()).. 2022. 7. 27. 최단 경로 알고리즘: 플로이드 워셜 모든 지점에서 다른 모든 지점까지의 최단거리를 구해야 하는 경우에 사용하는 알고리즘 graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b]) graph[a][b]는 a에서 b까지 가는 최단거리를 의미한다 a에서 b까지의 최단거리와, a에서k까지 갔다가 k에서 b 까지 가는 (k를 거쳐가는)최단거리를 비교해, 더 짧은 경로를 graph에 갱신시키는 방법이다 """ 시간복잡도가 O(N^3)이므로 간선의개수가 500개 이하일 때만 사용해야겠다 """ INF=int(1e9) n=int(input()) #노드개수 m=int(input()) #간선개수 graph = [[INF]*(n+1) for _ in range(n+1)] #2차원 거리리스트 for a in range(1,n.. 2022. 7. 27. 백준 13549번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net from collections import deque n,k=map(int,input().split()) INF=int(1e9) dist=[INF]*100001 def bfs(): queue=deque() queue.append(n) dist[n]=0 while queue: x=queue.popleft() if x==k: return dist[x] for nx i.. 2022. 7. 27. 백준 2589번: 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두.. 2022. 7. 26. 최단 경로 알고리즘: 다익스트라(Dijkstra) 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 볼 수 있다.. 다익스트라 알고리즘의 원리 1. 출발 노드를 설정한다 2. 최단 거리 테이블을 초기화한다 (자기자신=0, 다른노드=무한으로 설정함) 3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 과정에서 3번과 4번을 반복한다. 간단한 ver 파이썬 코드 import sys input = sys.stdin.readline INF = int(1e9) n,m = map(int,inpu.. 2022. 7. 26. 백준 1149번: RGB 거리 """ 1번집: rgb중 가장 싼거 2번집: (1번집에서 안한색 中 가장싼거 + 1번집가격) or (2번집 중 가장싼거 + 2번집에서 안한 색 중 1번집 가장싼거) 둘 중 더 싼거 """ n=int(input()) #집의 수 r=[]#빨간집을 칠하는 비용들 g=[]#초록집을 칠하는 비용들 b=[]#파란집을 칠하는 비용들 for i in range(n): R,G,B=map(int,input().split()) r.append((R,0)) g.append((G,1)) b.append((B,2)) #각 행의 1번 인덱스는 색을 표현함 data=[[0]*2 for i in range(n)] def C_rgb(i): if r[i][0] < g[i][0]: if r[i][0] 2022. 7. 26. 백준 16234번: 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에.. 2022. 7. 26. 백준 1654번: 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예.. 2022. 7. 25. 백준 16236번: 아기상어 from collections import deque n=int(input()) graph=[] for i in range(n): graph.append(list(map(int,input().split()))) for i in range(n): for j in range(n): if graph[i][j]==9: #아기상어의 위치 shark_x,shark_y=i,j #아기상어의 위치 저장 graph[i][j]=0 #빈칸으로 변경 level=2 dx=[1,-1,0,0] dy=[0,0,1,-1] def bfs(x,y,level): visited=[[0]*n for i in range(n)] dist=[[0]*n for i in range(n)] queue=deque() queue.append((x,y)) vi.. 2022. 7. 25. 백준 16236번: 아기상어 (실패) from collections import deque n=int(input()) field=[] for i in range(n): field.append(list(map(int,input().split()))) for i in range(n): for j in range(n): if field[i][j]==9: baby_shark=(i,j,2) #좌표와 크기 visited=[[0]*n for i in range(n)] dx=[-1,0,0,1] dy=[0,-1,1,0] def bfs(): global visited exp=0 queue=deque() queue.append(baby_shark) x1,y1,z=baby_shark visited[x1][y1]=1 #방문표시 time=0 while queue: .. 2022. 7. 25. 백준 2470번: 두 용액 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 .. 2022. 7. 21. 백준 11726번: 2xN 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. n=int(input()) d=[0]*1001 d[0]=0 d[1]=1 d[2]=2 #n.. 2022. 7. 21. 백준 9095번: 1,2,3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 숫자 n을 1,2,3으로 만들기 위해서 1+(n-1) 2+(n-2) 3+(n-3) 을 할 수 있다. t=int(input()) d=[0]*11 d[1]=1 #1 d[2]=2 #1+1, 2 d[3]=4 .. 2022. 7. 21. 백준 2206번: 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한.. 2022. 7. 21. 백준 10816번: 숫자 카드2 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다... 2022. 7. 20. 백준 1920번: 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에.. 2022. 7. 20. 다이나믹 프로그래밍: 바닥 공사 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하라. n=int(input()) d=[0]*1000000 d[1]=1 d[2]=3 for i in range(3,n+1): d[i]=d[i-1] + d[i-2]*2 print(d[n]) d [i]=가로가 i일 때 바닥을 채우는 모든 경우의 수 d [i]=d [i-1] + d [i-2]*2 가로가 i일 때.. "i-1까지의 것" + "2x1 짜리 타일 1개"로 구성할 수도 있고 "i-2까지의 것" + "2x2 짜리 타일 1개"로 구성할 수도 있고 "i-2까지의 것" + "1x2 짜리 타일 2개"로 구성할 수도 .. 2022. 7. 20. 다이나믹 프로그래밍: 효율적인 화폐 구성 n종류의 화폐가 있다. 이 화폐들을 최소한으로 이용해서 m원을 만들 때 필요한 화폐의 개수는? 앞서 배운 다이내믹 프로그래밍 예제들처럼 보텀업 방식을 이용했다. 반복문을 이용하여 0원~m원까지 필요한 화폐 수를 차근차근 구하고, 이미 구했던 화폐 수를 이용하여 다음 값을 찾는 식으로 구성했다. n,m=map(int,input().split()) #화폐종류 n개, 목표 M원 list_coin=[] for i in range(n): list_coin.append(int(input())) d=[-1]*10001 for i in list_coin: d[i]=1 #동전 1개로 사용가능한 것 초기화함 for i in range(min(list_coin)+1,m+1): count=0 for coin in list_c.. 2022. 7. 19. 이전 1 ··· 28 29 30 31 32 33 다음 728x90
