본문 바로가기

Algorithm/By Python

 (15)
[Python] 백준 1003번 피보나치 함수 https://www.acmicpc.net/problem/1003t = int(input())dp = [[1,0], [0,1]]for i in range(2, 41): dp.append([dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1]])for _ in range(t): test_case = int(input()) print(dp[test_case][0], dp[test_case][1]) fibo(0) = [1, 0] fibo(1) = [0, 1] fibo(2) = [1, 1] fibo(3) = [1, 2] fibo(4) = [2, 3] ... 이런 식으로 fibo(n) = [fibo(n-1)의 0의 개수 + fibo(n-2)의 0의 개수, fibo..
[Python] 백준 2644번 촌수계산 https://www.acmicpc.net/problem/2644from collections import dequen = int(input())p1, p2 = map(int, input().split())m = int(input())family = dict()visited = [0] * (n+1)for _ in range(m): n1, n2 = map(int, input().split()) if n1 not in family: family[n1] = [n2] else: family[n1].append(n2) if n2 not in family: family[n2] = [n1] else: family[n2].append(n1)#..
[Python] 백준 2302번 극장 좌석 https://www.acmicpc.net/problem/2302 문제 해결 시간 : 35분 요새 백준 푸는 게 재밌어지고 있는 중이다. 전에는 그냥 문제만 봐도 스트레스였는데...아무튼 이 문제는 처음 봤을 때 이게 뭐지 싶었다.뭔가 조합으로 구하는 문제인가? 하고 살펴봤지만 번호에서 해당 자리 포함 양옆까지만 되기 때문에 조합으로 구하는 문제는 아닌 거 같았다.1234이렇게 있을 때 1은 1, 22는 1,2,33은 2,3,44는 3,4이런 식으로 앉을 수 있다는 게 이 문제의 내용이다. 여기에 더해 VIP 좌석이라는 개념이 있는데 VIP는 지정석으로 해당 자리에만 앉을 수 있다.말 그대로 고정 좌석이었다. 예시를 살펴보면 9개의 좌석이 있고 4와 7번의 자리가 VIP 좌석으로 고정되어 있다.이때 4와..
[Python] 백준 14503 로봇청소기 https://www.acmicpc.net/problem/14503전에 풀어보려다가 한 번 실패하고 오랜만에 다시 풀어보는 문제였다. 이게 처음에 문제를 봤을 때는 문항이 다음과 같이 되어 있어서 왜 숫자가 저런 식으로 되어 있나 하고 의아했는데 2번 다음에 나오는 123의 경우 2-1, 2-2, 2-3이고 3번 다음에 나오는 123의 경우 3-1, 3-2, 3-3이라고 생각하면 된다.from collections import dequen, m = map(int, input().split())r, c, d = map(int, input().split())room = []for i in range(n): room.append(list(map(int, input().split())))# 북 동 남 서d..
[Python] 백준 2493번 탑 https://www.acmicpc.net/problem/2493처음에는 O(n^2)으로 풀고 계속 시간초과가 나서 어떻게 풀어야되나 많은 고민을 했다. 이 문제의 키 포인트는 현재 위치로부터 왼쪽에 더 큰 탑이 있어야 한다는 것이다.예제에서는 69574인데 위에서는 69754를 예시로 해서 풀었다.(혹시라도 이 글을 읽고 계신 분들은 참고해주세요) 위 풀이를 코드로 옮기면 다음과 같다.n = int(input().rstrip())top_arr = list(map(int, input().split()))def solution(top_arr): answer = [0] * len(top_arr) stack = [(0, top_arr[0])] for i in range(1, len(top_ar..
[Python] 백준 2470번 두 용액 메모리 초과...# 조합def comb(arr, n): result = [] if n==1: return [[i] for i in arr] for i in range(len(arr)): elem = arr[i] for rest in comb(arr[i+1:], n-1): result.append([elem] + rest) return resultn = int(input())solution = list(map(int, input().split()))# 조합 하기 전 정렬solution.sort()# 만들 수 있는 조합solution_combination = comb(solution, 2)# 0으로부터 거리를 키 값으로 한 조합을..

티스토리툴바