본문 바로가기
728x90
반응형

# Coding

 (78)
[백준 / 11779] 최소비용 구하기 2 - Python https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net import sys import heapq def route(graph, start): distances = {} nodes = {} for i in graph: distances[i] = float('inf') nodes[i] = [] distances[start] = 0 queue = [[0, start]] while queue: now_distance, now..
[백준 / 14503] 로봇 청소기 - Python https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net import sys N, M = map(int, sys.stdin.readline().split()) r, c, d = map(int, sys.stdin.readline().split()) # 0 북, 1 동, 2 남, 3 서 graph = [] for _ in range(N): graph.append(list(map(int, sys.stdin.readline().split()))) now_ro..
[백준 / 1912] 연속합 - Python https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 맨 앞의 수부터 현재수와 지금까지의 수를 비교하여 더 큰 수를 temp에 저장한다. 그리고 temp의 수와 현재 수를 더한 수와 현재수를 비교하여 더 큰 수를 temp에 다시 저장한다. n = int(input()) num = list(map(int, input().split())) temp = [0 for _ in range(n)] for i in range(n): temp[i] = max(temp[i-1..
[백준 / 10422] 괄호 - Python https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 카탈란 수를 이용하여 풀었다. 괄호 문자열의 길이가 홀수이면 카탈란 수가 될 수 없다. import math def catalan(n): return math.factorial(2*n)//(math.factorial(n)*math.factorial(n+1)) for _ in range(int(input())): n = int(input()) if n == 0: break if n % 2 == 1..
[백준 / 4811] 알약 - Python https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 해당 문제는 카탈란 수를 이용하여 풀었다. 공식 : Cn = (2*n)! / n! * (n+1)! import math def catalan(n): return math.factorial(2*n)//(math.factorial(n)*math.factorial(n+1)) while True: n = int(input()) if n == 0: break print(catalan(n))
[백준 / 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 import sys def visit_tree(graph, visit, start): queue = [start] while queue: node = queue.pop() if node in visit: continue else: visit.append(node) queue.extend(graph[node]) n, m = map(int..
[백준 / 11725] 트리의 부모 찾기 - Python https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net import sys graph = {} top = {} n = int(sys.stdin.readline()) for _ in range(n-1): x, y = map(int, sys.stdin.readline().split()) if x not in graph: graph[x] = [y] else: graph[x].append(y) if y not in graph: graph[y] = [x] else: graph[y].append(x) queue = [1] w..
[백준 / 19238] 스타트 택시 - Python https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 어렵다. 해당 문제는 '다익스트라 알고리즘(Dijkstra)'을 응용하여 풀었다. 2021.03.18 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python [보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python '다익스트라(Dijkstra) 알고리즘..
728x90
반응형

티스토리툴바