본문 바로가기

🔅코딩테스트 공부🔅/❗백준138

[백준] 1916번 최소비용 구하기(python) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 1. 난이도 골드5 (🥇) 2. 내가 작성한 코드 한 지점에서 한 지점까지의 최단경로 + 가중치가 모두 음이 아님을 만족하기 때문에 다익스트라 알고리즘을 이용하면 된다. import heapq import sys n = int(input().rstrip()) #도시의 개수 m = int(input().rstrip()) #버스의 개수 INF = int(1e9) gr.. 2023. 2. 24.
[백준] 1753번 최단경로(python) 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 1. 난이도 골드4 (🥇) 2. 내가 작성한 코드 import heapq import sys input = sys.stdin.readline INF = int(1e9) v,e = map(int,input().rstrip().split()) #v는 정점, e는 간선 start = int(input().rstrip()) #시작 정점 번호 distance = [IN.. 2023. 2. 24.
[백준] 2206번 벽 부수고 이동하기(python) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 난이도 골드3 (🥇) 아 진짜 넘나리 어려웠는데 막상 이해하니 해볼만 한 것 같다. 3차원 list를 이용해서 벽을 부순적이 있는 지 없는 지를 확인해주면 된다. 2. 코드 분석 1. n,m, maps는 다른 문제와 동일하게 입력을 받는다. 2. 방문 여부를 확인하기 위해 visit 리스트를 만든다. 이때, 같은 행과 열의 크기를 가진 2층짜리 3차원 리스트를 만든다.. 2023. 2. 23.
[백준] 1874번 스택수열(python) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1. 난이도 실버2 (🥈) 도대체 이게 무슨 문제인가 한참을 고민하다가 풀었다. 결론적으로 말하자면 stack을 적절하게 이용해서 input 의 순서와 같은 수열을 만들어 내는 것이다! 예제 입력 1을 보면 4-3-6-8-7-5-2-1 순서로 입력되는데, stack에서 pop한 값이 이 순서대로 나오면 된다. 2. .. 2023. 2. 23.
[백준] 4963번 섬의 개수(python) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 내가 작성한 코드 from collections import deque import sys input = sys.stdin.readline def bfs(k): queue.append(k) visit[k[0]][k[1]] = 1 dx = [1, 1, 0, -1, -1, -1, 0, 1] dy = [0, 1, 1, 1, 0, -1, -1, -1] while qu.. 2023. 2. 22.
[백준] 11724번 연결 요소의 개수(python) https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 내가 작성한 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n, m = map(int, input().rstrip().split()) graph = [[] for _ in range(n+1)] for _ in range(m):.. 2023. 2. 20.
[백준] 13023번 ABCDE(python) https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 내가 작성한 코드(틀림) import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline def dfs(v): for i in relation[v]: if visit[i] == 0: visit[i] = visit[v] + 1 dfs(i) n,m = map(int, input().rstrip().split()) #n=친구수 m=관계수 relation = [[] for _ in range(n)] for i in range(m): a,b = map.. 2023. 2. 19.
[백준] 11725번 트리의 부모 찾기(python) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 내가 작성한 코드 import sys sys.setrecursionlimit(10**9) n = int(input()) #노드의 개수 tree = [[] for _ in range(n+1)] #tree parent = [0] * (n+1) #parent 저장 for i in range(n-1): a,b = map(int, input().split()) tree[a].append(b) tree[b].append(a) def dfs(num): for j in.. 2023. 2. 18.
[백준] 카드 정렬하기 (python) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 내가 작성한 코드 import heapq import sys input = sys.stdin.readline n = int(input().rstrip()) #입력 횟수 heap = [] for i in range(n): heapq.heappush(heap,int(input().rstrip())) #heap에 모든 값 push answer = 0 while True: if len.. 2023. 2. 18.

티스토리툴바