1. 문제 출처 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 풀이 Dynamic Programming 방법 중 botton up 방법을 사용하여 문제를 해결하였다. # 입력받기 import sys n = int(sys.stdin.readline()) # 미리값을 저장할 배열 dp = [0] * (n+2) # 1~3까지는 바로 출력한다. if n==1: print(0) elif n==2 | n==3: print(1) else: dp[2] = 1 dp[3] = 1 for i in range(4, n+1): # 숫자가 i일 때 # 3가지 방법 중 최소 횟..
1. 문제 출처 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이 기본적인 데이크스트라 알고리즘을 사용하는 문제이다. 변형된 점은 인접한 노드를 구할 때 리스트나 메트릭스를 이용하는 것이 아닌 , 해당 좌표의 상하 좌우를 가지고 온다는 것이다. # 데이크스트라 알고리즘을 위한 힙 모듈 불러오기 import heapq # 입력 result = [] n = int(input()) while n!=0: #입력 graph =..
1. 문제 출처 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 풀이 BFS를 이용하지만 벽을 부수는 경우가 있기 때문에 데이크스트라 알고리즘도 같이 이용해야 한다. 벽부시는 것을 가중치로 두고 만약 벽을 부수지 않고 이동한다면, 가중치를 더해주지 않는 것이 필요하다. 다음과 같이 진행된다. 1. 상하좌우 중 범위를 나가지 않는 곳으로 이동 2. 해당 이동좌표에 벽이 있다면 전 가중치+1 을 해주고 append를 통..
1. 문제 출처 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 풀이 각 노드를 시작점으로 경로를 구해줘야 한다. import heapq # 입력 n,m,x = map(int, input().split()) graph = [[] for _ in range(n+1)] distance = [[float('inf')] * (n+1) for _ in range(n+1)] # 입력 for _ in range(m): s..
1. 문제 출처 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 풀이 데이크스트라 알고리즘을 이용한 문제이다... 여기서 주의 할점은 그래프 배열의 사이즈를 max(n,k)로 하는 것이아니라 100000로 해야한다. 왜냐하면 max 를 사용해서 지정 할경우 해당 범위를 지나서 도착하는 것이 더빠를 수 있는데 그것을 계산하지 못하기 때문이다. import heapq #입력 n,k = map(int, inpu..
1. 문제 출처 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 풀이 단순 데이크스트라 알고리즘을 이용하는 문제이다. import sys input = sys.stdin.readline import heapq # 최대값 정의 INF = float('inf') # 입력 n = int(input()) m = int(input()) # 그래프와 거리 초기화 graph = [[] for _ in range(n+1..
1. 문제 출처 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 풀이 데이크스트라를 사용하는 문제이다. 데이크스트라 알고리즘은 별로 사용한 적이 없어서 많이 해멘던 것 같다. 그래프 자료 구조를 사용하여 weights ,node, edge 를 구현 하였고 해당 구조를 사용하여 데이크스트라 알고리즘 을 사용하기 위해 우선순위큐를 구현해야 했다. 이 우선순위 큐를 구현하기 위해 heap 구조를 사용하였다...
1. 문제 출처 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2. 풀이 DFS 와 BFS 에 대한 기초적인 문제를 확인 할 수 있었다. # 필요 라이브러리 불러오가 import copy from collections import deque # 입력 n, m, v = map(int, input().split()) # 그래프 값 초기화 graph = [[0 for _ in range(n)] for _ in ..
