세리프 따라잡기

피보나치 수열 문제를 예시로, def fibo(s): if s ==1 or s == 2: return 1 if dp[s] != 0: return dp[s] dp[s] = fibo(s-1)+fibo(s-2) return dp[s] print(fibo(n)) 아래와 같이. from collections import defaultdict import sys input = sys.stdin.readline n = int(input()) dp = defaultdict(int) def fibo(n): if n

다이나믹 프로그래밍(Dynamic Programming)이란? - 메모리를 적절히 사용해 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장해두었다가 나중에 해당 결과가 필요할 때 메모리 영역에 기록되어 있던 정보를 그대로 사용하도록 한다. 즉, 한 번 계산해서 해결한 문제는 다시 해결하지 않도록 함 └> 굉장히 비효율적인 시간 복잡도를 가진 문제여도, DP를 이용해서 시간 복잡도를 줄일 수 있는 경우가 많다! - DP의 구현은 일반적으로 탑다운(하향식), 바텀업(상향식)의 두 가지 방식으로 구성된다. - DP는 동적 계획법이라고도 부른다. └> 여기서의 동적(Dynamic)의 의미는, 별다른 의미가 없다..! 더보기 ex. 자료구조에서 동적 할당..

위상정렬이란? - 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 진입차수와 진출차수 - 진입차수(indegree): 특정한 노드로 들어오는 간선의 개수 - 진출차수(outdegree): 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 동작 과정 1. 진입차수가 0인 모든 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음 과정을 반복한다. -1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 -2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. → 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같음! 위상 정렬의 특징 - 위상 정렬은 순환하지 않는 방향 그래프(DAG)에서만 수행할 수 있다. - 위상 정렬에..

플로이드 워셜(Floyd-Warshall)이란? -모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산 -플로이드 워설 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행 →다만 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요X -플로이드 워셜은 2차원 테이블에 최단 거리 정보 저장 -다이나믹 프로그래밍 유형에 속한다. 노드의 개수가 적은 상태에서 효과적으로 사용하고, 노드의 개수와 간선이 많은 경우는 다익스트라를 더 많이 사용한다. 점화식 : 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인 → a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사 # 점화식에 따라 플로이드 워셜 알고리즘을 수..

다익스트라(Dijkstra) 알고리즘이란? 1. 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 2. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. [but, 음수일 땐 사용 불가능] 3. 다익스트라는 다이나믹 프로그래밍 or 그리디 알고리즘으로 분류되기도 한다. = 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다. [작은 문제가 큰 문제에 속해있는 다이나믹 유형] 4. 기본적으로 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용 5. 다익스트라는 정렬 사용 - 정렬 이후에 가장 적은 것을 하나씩 선택하는 게 알고리즘에 포함 [그리디 알고리즘] 다익스트라 작동 과정 1. 출발 노드를 설정 2. 출발 노드를 기준으로 각 노드의 최소 ..

DFS 기본 구현 1. 시작 노드에서 방문하지 않았으면 노드를 삽입해준다 == 방문 표시 2. 더 이상 방문이 불가능하다면, 탐색 중단하고 이전으로 돌아옴 *특징 1. 스택 or 재귀함수 사용 2. 한 방향으로 깊게 탐색 3. 깊이 제한 횟수를 늘려주자! sys.setrecursionlimit(10**8) #깊이 제한 def dfs(arr, cur, visited): visited[cur] = True for i in arr[cur]: if not visited[i]: dfs(arr, cur, visited) # 나는 dfs(arr, cur, visited) 부분을 defaultdict를 이용해 graph에 담아서 사용 def dfs(v): visited[v]=1 print(v,end=' ') for i..

최소 신장(스패닝) 트리 (minimum spanning tree) = 전체 요소들을 연결할 때 사용한다. kruskal 알고리즘, prim 알고리즘이 있다. 스패닝 트리란? - 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 조건? - 본래의 그래프의 모든 노드를 포함해야 함 - 모든 노드가 서로 연결 - 트리의 속성을 만족시킴(사이클이 존재하지 않음) ☞ 사이클이란? 그래프가 서로 연결되어 사이클을 형성하는 경우. 최소 비용 스패닝 트리에서는 사이클이 발생하면 안 된다! 애초에 모든 노드를 이어붙이기만 하면 되는데 사이클이 발생할 이유가 없다고 한다! ==> 이러면 안됩니다~ 크루스칼 kruskal 1. 간선들을 정렬 2. 간선이 잇는 두 정점의 root 찾기 3. 다르면..

알고리즘 스피드는 완료까지 걸리는 절차의 수로 결정이 된다. → 따라서 같은 작업을 수행하는데 5단계만 수행하면 되는 알고리즘이 10단계를 수행하는 알고리즘보다 좋은 알고리즘이다. 1. 상수 시간(constant time) ex. 선형 탐색 알고리즘은 1개씩 차례대로 다 검사를 해보는데, 만약 데이터가 무수히 많다면...........? 무수히 많은 단계를 거쳐야 한다~ [ n=input()이라면 n단계를 거쳐야 함 ] → 선형 탐색은 O(N)의 시간 복잡도를 가짐 빠르다/느리다 라고 표현하는 것보다 더 직관적으로 빠르게 설명할 수 있다 == BigO BigO를 이해한다면? = 알고리즘 분석을 더 빠르게 할 수 있고, 언제 무엇을 쓸지 파악이 가능하며, 자신의 코드를 평가할 수 있다. (이 코드가 미래에..

- 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. - 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex. 어떤 물건 데이터를 자료구조에 넣었다가 가치가 높을 물건부터 꺼내서 확인해야 하는 경우, 우선순위 큐에 각각의 물건 정보를 가치 데이터와 함께 우선순위 큐에 넣었다가 꺼낼 때 자료구조 추출되는 데이터 스택 (stack) 가장 나중에 삽입된 데이터 큐 (queue) 가장 먼저 삽입된 데이터 우선순위 큐 (priority queue) 가장 우선순위가 높은 데이터 - 우선순위 큐를 구현하는 방법 1. 단순히 리스트를 이용해 구현 = 리스트에 차례대로 데이터를 연달아 넣고, 꺼낼 때는 리스트에서 각각의 데이터를 확인한 다음에 값이 가장 큰 데이터를 뽑아 추출..

'스택' 자료구조는 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출-먼저 입력되는 데이터가 나중에 출력된다)의 자료구조이다. → 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. - 대표적 예시: 박스 쌓기 = 여러 개의 박스를 쌓아야할 때(스택하고자 할 때) 아래쪽에서부터 박스를 차례대로 올려놓는다. 쌓아놓은 박스를 다시 내리고자 할 때는 가장 위쪽에 있는 박스부터 차례대로 내리게 된다. 스택 자료구조 기억은 박스 쌓기 예시로 기억하면 좋다!! 다양한 알고리즘에서 사용되기에, 스택 자료구조의 동작 방법과 사용 방법에 대해 꼭 알아야 한다! - 스택 자료구조는 삽입과 삭제 두 연산으로 구성된다. 삽입 과정이 차례대로 쌓이다, 삭제 연산을 만나면 가장 마지막에 들어왔던 7이 우선적으로 나가게 된다..