본문 바로가기

알고리즘/🥇 골드

 (72)
백준 11779 최소비용 구하기 2 파이썬 풀이 난이도 : 골드3 풀이일 : 2401173 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 import sys, heapq def djikstra(num): visited[num] = [0, f'{num}'] queue = [] heapq.heappush(queue, [visited[num], num]) while queue: load, now = h..
백준 1753 최단경로 파이썬 풀이 난이도 : 골드4 풀이일 : 2401162 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 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys, heapq def dijkstra(n): visited[n] = 0 queue = [] heapq.heappush(queue, [visited[n], n]) while queue: distance, now = heapq.heappop(que..
백준 1916 최소비용 구하기 파이썬 풀이, 시간초과, heapq vs deque 난이도 : 골드5 풀이일 : 2401151 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 - 시간초과 import sys from collections import deque N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) load = [[] for _ in range(N+1)] resul..
백준 1717 집합의 표현 파이썬 풀이 난이도 : 골드5 풀이일 : 2401147 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys N, M = list(map(int, sys.stdin.readline().split())) parent = [i for i in range(N+1)] # 부모 노드 찾기 def find(n): if parent[n] == n: return ..
백준 1111 IQ Test 파이썬 풀이 난이도 : 골드3 풀이일 : 07204 https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 링크로 이동하시면 더 많은 예제가 있습니다. 풀이 코드 import sys # 조건 외 항 검사 def check(x, y): for i in range(N-1): if num[i] * x + y != num[i+1]: return print('B') return print(num[-1] * x + y) N = int(sys.stdin.readline().strip()) num ..
백준 4386 별자리 만들기 파이썬 풀이 난이도 : 골드3 풀이일 : 07097 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys # 연결 확인 함수 def check(m): if m != parent[m]: parent[m] = check(parent[m]) return parent[m] n = int(sys.stdin.readline().strip()) star = [] road = [] result = 0 ..
백준 13418 학교 탐방하기 파이썬 풀이, 반례 난이도 : 골드3 풀이일 : 07086 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys # 연결 확인 함수 def check(parent, n): if parent[n] != n: parent[n] = check(parent, parent[n]) return parent[n] # 오르막길 더하기 함수 def count(temp): p..
백준 1197 최소 스패닝 트리 파이썬 풀이 난이도 : 골드4 풀이일 : 07075 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 -> 3% 틀렸습니다 import sys def check(num): if parent[num] != num: parent[num] = check(parent[num]) return parent[num] V, E = map(int, sys.stdin...
백준 2146 다리 만들기 파이썬 풀이 난이도 : 골드3 풀이일 : 07053 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys from collections import deque # 섬 고유번호 설정 함수 def islandnum(a, b, num): queue = deque() queue.append((a, b)) while queue: i, j = queue.popleft() for k in range(4)..
백준 2638 치즈 파이썬 풀이 반례 난이도 : 골드3 풀이일 : 05151 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 -> 런타임에러(최대 재귀횟수 초과) import sys from collections import deque def air(x, y): # 외부 공간 숫자 변경 space = deque() space.append((x, y)) visited = [[0] * M for _ in ran..
백준 2206 벽 부수고 이동하기 파이썬 풀이 난이도 : 골드3 풀이일 : 05125 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys from collections import deque N, M = map(int, sys.stdin.readline().split()) arr = [sys.stdin.readline().strip() for _ in range(N)] visited = [[[..
백준 1600 말이 되고픈 원숭이 파이썬 풀이 난이도 : 골드3 풀이일 : 05127 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 # 1차 시도 -> 런타임 에러 visited 숫자가 커서 방문할 수 없지만, 벽으로 가로 막혀 나중에 말처럼 이동해야 하는 경우 import sys from collections import deque K = int(sys.stdin.readline().strip()) W, H = m..
백준 1918 후위 표기식 파이썬 풀이 난이도 : 골드2 풀이일 : 03057 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 import sys w = sys.stdin.readline() result = '' stack = [] for i in w: if i in '+-*/()': if i in '+-': if i == '+': while stack and stack[-1] in '-*/': result += st..
백준 1238 파티 파이썬 풀이, 반례 난이도 : 골드3 풀이일 : 05092 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 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 -> 시간초과 import sys from collections import deque N, M, X = map(int, sys.stdin.readline().split()) load = deque([] for _ in range(N+1)) for _ in range..
백준 12851 숨바꼭질2 파이썬 풀이, 반례 난이도 : 골드4 풀이일 : 05092 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐1차 시도 오답 -> 76% 틀렸습니다import sys from collections import deque N, K = map(int, sys.stdin.readline().split()) visited = [100001] * 100001 count = 0 mini = 1000..
백준 3665 최종순위 파이썬 풀이 난이도 : 골드1 풀이일 : 05081 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 import sys from collections import deque T = int(sys.stdin.readline().strip()) for _ in range(T): n = int(sys.stdin.readline().strip()) # 팀 수 last = list(map(int,..
백준 9470 Strahler 순서 파이썬 풀이 난이도 : 골드3 풀이일 : 05077 https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 오답 코드 import sys from collections import deque T = int(sys.stdin.readline().strip()) for _ in range(T): K, M, P = map(int, sys.stdin.readline().split()) node = [0] * (M + 1)..
백준 1516 게임개발 파이썬 풀이 난이도 : 골드3 풀이일 : 05066 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys from collections import deque N = int(sys.stdin.readline().strip()) time = [0] * N # 개별 건물 건설 시간 total = [0] * N # 개별 건물 누적 시간 count = [0] * N # 선행 건물 개..
백준 2056 작업 파이썬 풀이 난이도 : 골드4 풀이일 : 05055 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 # 입력 시, temp 리스트 활용으로 project 삽입 # 새 누적 시간과 현재 누적 시간을 비교, 큰 값 저장 # 선행 작업 완료할 때 마다 count - 1 # count 0 되면 작업 시작 -> queue 추가 # 최종 누적 시간 중 가장 큰 값 출력 import sys from col..
백준 2252 줄세우기 파이썬 풀이 난이도 : 골드3 풀이일 : 05044 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 : deque 두 개 사용, 최초풀이 import sys from collections import deque N, M = map(int, sys.stdin.readline().split()) people = [[] for _ in range(N+1)] min..

티스토리툴바