본문 바로가기

알고리즘

 (138)
[시간 복잡도][Python] 리스트와 딕셔너리의 시간 복잡도 정리 자료는 아래 링크를 들어가면 된다. 초보몽키님 자료 파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그 파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) 14 Jun 2017 | 들어가기 알고리즘 문제를 풀다 보면 시간복잡도를 생각해야 하는 경우가 종종 생긴다. 특히 codility는 문제마다 시간복잡도 기준 wayhome25.github.io insert, delete, remove 등 몇몇 부분에서는 list보다 dict이 더 빠르다. list는 dict과 다르게 각 index를 가지고 있고, 이벤트 발생 시 값마다 index가 변동돼야 할 수도 있기 때문이다. 시간 복잡도를 생각하며 문제를 풀자 !
[최단 경로 트리] 다익스트라 알고리즘[Dijkstra] 다익스트라 알고리즘을 설명하기 전에, 최단 신장 트리에 대해 설명해보자. 신장 트리란 그래프 내의 모든 정점이 연결되어 있으면서 사이클이 존재하지 않는 트리이다. 따라서 신장 트리는 N개의 정점을 정확히 N-1개의 간선으로 연결하게 된다. 다익스트라 알고리즘은 출발 지점을 정하여, 다른 모든 지점까지의 최단 경로를 찾는 것이다. 예를 들어보면, A를 출발 지점으로 두고 시작해보자. A의 최단 거리값은 0으로, 나머지 최단 거리값은 무한으로 설정한다. 이제 A와 연결된 B, C의 거리 값을 조정하자. 여기서, 시작점 거리값 + 아크 값 < 도착점 거리값이라면, 도착점 거리값을 더한 값으로 낮춘다. 방금 했던 것을 무한 반복할껀데, 이번에는 B를 기준으로 한다. 최종적으로, 이런 결과가 나오게 된다. 거리가..
[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))

티스토리툴바