본문 바로가기
반응형

Problem Solving232

[분할 정복/ 파이썬] 백준 11444번 : 피보나치 수 6 / 골드 3 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net dp로 잘 알려진 피보나치 문제지만, 이 문제에선 n이 정말 큰 수로 주어지기 때문에 조금 다른 방법을 써야한다. 도가뉴 항등식이라고 있다. n번째 피보나치 수를 a(n)이라 하면, a(2n) = a(n)[a(n) + 2a(n-1)] a(2n-1) = a(n)**2 + a(n-1)**2 가 성립한다. 따라서 n이 아무리 커도 log(n) 시간에 문제를 해결할 수 있기 때문에 이 문제를 풀 수가 있다. import collections n = int(input()) m = 1.. 2021. 12. 6.
[최단 경로] 백준 11779번 : 최소비용 구하기 2 / 골드 3 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 + 경로 직접 구하기 문제이다. 힙에 cost + w, next 뿐만 아니라 cur 노드도 넣어준다. 그리고 힙에서 하나씩 꺼내면서 처음 방문한 노드에 도착하면 딕셔너리 구조에 이전 노드, 현재 노드를 저장해준다. 다익스트라가 끝난 후 딕셔너리를 이용해 목적지부터 역순으로 경로를 추적하면 된다. 웰노운 문젠데 좀 오래 걸렸다.. 정신차리자. import .. 2021. 12. 3.
[다이나믹 프로그래밍] 백준 11054번: 가장 긴 바이토닉 부분 수열 / 골드 3 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net well-known problem인 LIS를 조금 응용하면 풀 수 있는 문제! n = int(input()) nums = list(map(int, input().split())) dp_asc = [0 for _ in range(n)] dp_desc = [0 for _ in range(n)] for i in range(n): max_val = 0 for j in range(i): if nums[j] < nums[i]:.. 2021. 12. 3.
[구현] 백준 1918번 : 후위 표기식 / 골드 3 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net string = [x for x in input()] opers = [] dct = {} dct['*'] = 1 dct['/'] = 1 dct['+'] = 2 dct['-'] = 2 result = '' count = 0 while string: elem = string.pop(0) if elem.isalpha(): result += elem else: if not opers: if elem .. 2021. 11. 26.
[구현] 백준 17144번: 미세먼지 안녕! / 골드 4 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net x_lim, y_lim, t = map(int, input().split()) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] table = [] air_x = -1 for i in range(x_lim): row = list(map(int, input().split())) if row[0] == -1: air_x = i table.append(row) assistant = .. 2021. 11. 16.
[재귀] 백준 2448번 : 별 찍기 - 11 / 골드 4 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net n = int(input()) def star(k): if k == 3: return [[' ', ' ', '*', ' ', ' '], [' ', '*', ' ', '*', ' '], ['*', '*', '*', '*', '*']] output = [] unit = star(k // 2) k = k//2 for i in range(2*k): if i < k: output.append([' ']*k + unit[i] + [' ']*k) else: ou.. 2021. 11. 16.
반응형

티스토리툴바