본문 바로가기

알고리즘/백준

 (64)
[BOJ] [Python] 18352번 : 특정 거리의 도시 찾기 다익스트라 알고리즘을 이용하여 풀었다. 처음에는 시간 초과가 났다. 통과하기 위한 과정을 아래에 적어놓았다. 아래는 통과한 코드이다. import sys import heapq input = sys.stdin.readline n, m, k, x = map(int, input().split()) route = [] val = [10000000] * (n+1) val[x] = 0 for n_c in range(n+1): route.append([]) for m_c in range(m): num = list(map(int, input().split())) route[num[0]].append(num[1]) order = [] # 순서 리스트 heapq.heappush(order, (0, x)) # (거리, 위..
[BOJ] [Python] 11053번 : 가장 긴 증가하는 부분 수열 앞에서부터, 각 값에 해당하는 최대 수열 위치를 저장하면 된다. 예를 들어, 50의 위치 최댓값을 고려할 때 1. 30의 3번 뒤 2. 25의 6번 뒤 당연히 2번을 선택해야 한다. 둘 다 값이 50보다 작기 때문에, 더 큰 수열 위치를 선택한 것이다. num = int(input()) li = list(map(int, input().split())) dp = [0] * len(li) for i in range(num): tmp = 0 for j in range(i): if li[j] < li[i] and tmp < dp[j]: tmp = dp[j] dp[i] = tmp dp[i] += 1 # self print(max(dp))
[BOJ] [Python] 1932번 : 정수 삼각형 li 리스트와 동일한 위치의 dp 리스트 위치에는, 그 위치까지 계산된 값을 넣었다. num = int(input()) li = [] dp = [] for n in range(num): li.append(list(map(int, input().split()))) if(n != num-1): dp.append([0] * len(li)) dp.append(li[-1]) li.reverse() dp.reverse() for i in range(num): for j in range(len(li[i])-1): dp[i+1][j] = max(dp[i][j], dp[i][j+1]) + li[i+1][j] print(dp[-1][0])
[BOJ] [Python] 2579번 : 계단 오르기 어느 계단이든지, 그 계단을 밟기 위한 방법은 2가지이다. n번째 계단을 예시로 생각해보자. 1. n-2번째와 n번째 밟기 2. n-3번째와 n-1번째, n번째 밟기 첫 번째 방법에서는 n-2번째 계단이, 두 번째 방법에서는 n-3번째 계단이 첫 계단이다. 이 계단들은 그 자리에 오기까지의 값을 dp 리스트에 저장하고 있어야 하고, 계산할 때, 계단의 값이 아닌 dp 값을 더해야 한다. 방법1과 방법2 중 더 큰 값을 골라, n번째 dp에 저장한다. num = int(input()) li = [0] dp = [0] * (num + 1) for n in range(num): li.append(int(input())) for i in range(1, num+1): if(i == 1): dp[1] = li[1..
[BOJ] [Python] 9625번 : BABBA 1) 규칙을 찾아보자 문제에 나온 예시를 그대로 적어보면, F(n) = F(n - 1) + F(n - 2) (n >= 2) 라는 규칙이 보인다. 즉, 피보나치 수열이다. 2) A와 B 관계를 보자 n의 A 개수는 n-1의 B 개수이다. (n >= 1) 피보나치 수열을 재귀함수를 이용했을 때와는 달리, 리스트에 값을 저장하는 식[Memoization]으로 풀었다. num = int(input()) # 피보나치 # [0, 1, ... ] dp = [0] * (num + 1) dp[1] = 1 for i in range(2, num+1): dp[i] = dp[i-1] + dp[i-2] print(dp[num-1], dp[num]) + 추가) 재귀함수를 이용하면 했던 연산을 또 하게 된다.
[BOJ] [Python] 3079번 : 입국심사 이진탐색을 이용하여 풀었다. 이 문제의 난관은 'mid값의 중복' 이었다. 만약 mid가 8이라면, T(k) = 2, 4, 8 모두 8초까지 작업을 수행할 수 있다. 하지만 이 예제의 인원은 5명으로 제한되어 있기 때문에 T(k) = 2만 8초까지 수행한다. 이를 어떻게 해결해야 할까? '입국 심사를 통과해야 하는 인원[입력값] == 입국 심사를 통과할 예상 인원'이 아니라, '입국 심사를 통과해야 하는 인원[입력값]
[BOJ] [Python] 2805번 : 나무 자르기 이진탐색을 이용하여 풀었다. mid가 작을수록 더 많은 나무를 가져간다. num = list(map(int, input().split())) n = num[0] # 나무 수 m = num[1] # 가져가야 할 나무 길이 tree = sorted(list(map(int, input().split()))) # 나무 길이 def BSearch(li, target): low = 1 # 자를 나무 최소 높이 -> 더 많이 가져감 high = li[-1] #자를 나무 최대 높이 -> 더 조금 가져감 result = 0 while(low
[BOJ] [Python] 10870번 : 피보나치 수 5 피보나치 수열은 F(n) = F(n-1) + F(n-2) ( n >= 2 ) 이다. F(2) = F(1) + F(0)일 때, F(1) = 0, F(0) = 0으로 잡아준다. num = int(input()) def fibN(n): if n == 0: return 0 elif n == 1: return 1 else: return fibN(n-1) + fibN(n-2) print(fibN(num))
[BOJ] [Python] 10872번 : 팩토리얼 팩토리얼은 n! = n * n -1 * ... * 1 이다. ( 0! = 1 ) num = int(input()) def recursion(n): if n == 0 or n == 1: return 1 else: return n * recursion(n - 1) print(recursion(num))
[BOJ] [Python] 2110번 : 공유기 설치 이진탐색을 이용하여 풀었다. low는 '공유기와 집' 사이의 최소 간격, high는 최대 간격으로 잡았다. ※ 현재 mid 값에 설치된 공유기 개수 찾기 '집 위치 - 공유기가 설치된 지점'가 mid보다 크다면 설치가 가능하다. n개의 집에 몇 개의 공유기가 설치될 수 있는 가? => 현재 mid 값으로 설치된 공유기 개수 >= 설치해야 할 공유기 개수라면? : mid값이 작은 것이다. 즉, 간격이 좁은 것이다. 간격을 더 늘려도 된다. (만약, 개수가 같아서 혹은 개수를 더 줄일 수 없다면 result값에 저장해놓은 값을 출력한다.) => 현재 mid 값에 설치된 공유기 개수 < 설치해야 할 공유기 개수라면? : mid값이 큰 것이다. 즉, 간격이 넓은 것이다. 간격을 더 좁혀도 된다. num = li..

티스토리툴바