본문 바로가기

PS/Algorithm6

[Algorithm] 이중 포문 조정 - 구간합 개요 시간복잡도 줄이는 법을 학습하면서 해본 정리 코드트리를 참고하였다! 어떤 배열에서 특정 합을 만족하며 가장 크기가 큰 구간의 크기를 찾기 위해 완전탐색을 하면 다음과 같다. 완전탐색 - O(N**3) # 이 배열에서 특정 구간을 골라서, # 합이 10이 넘지 않아야 하고, # 배열의 크기가 가장 커야 한다. 이때의 배열 크기는? arr = [0,6,3,2,4,9,1] n = len(arr) target=10 # 무식하게 구해보기 for i in range(1, n+1): for j in range(i, n+1): total = 0 for k in range(i, j+1): total += arr[k] if total target : break ans = max(ans, j-i+1) *이 경우, j는.. 2024. 4. 17.
[알고리즘] 다익스트라_Prim's algorithm 복습용.. 다익스트라 다익스트라는 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. bfs, dfs처럼 원리를 통해 특정 경로, 비용 등을 계산하는 알고리즘이다. 최단경로(출발, 도착, 비용) **이때 cost는 양의 가중치, 유향 그래프 특징 1. 시작점이 주어진다. 2. 시작점을 출발지로 [INF] * (n+1)로 초기화된 node의 가중치 정보를 갱신하며 그래프 탐색을 한다. 3. 이때 노드들을 방문하면서 python heapq를 사용하여 노드 번호와 가중치를 체크하면 최단거리를 찾을 수 있다. 4. graph는 i번째 노드에서 j번째 가는 가중치(w)를 저장해야 하므로 이차원 리스트로 구현한다. 구현은 python heapq를 활용한다. python의 우선순위 큐. 원.. 2023. 6. 7.
[알고리즘] convex hull(컨벡스 헐) 계산 기하 2/3차원 공간상에서 점, 선, 도형 간의 관계를 다루는 문제 실생활에 매우 밀접하게 응용된다. 일단 2차원 공간/정수 좌표/정수 연산으로 가정한다. → 가급적 +,-,*,>,=, 2023. 5. 2.
[알고리즘] Segment Tree 1. 구간 l,r의 합 구하기(O(N)) 2. i 번째 수를 v로 바꾸기(O(1)) ⇒ 총 시간 복잡도는 O(NM) + O(M) = O(NM) segment tree를 써야 하는 이유 이때 구간합 알고리즘 사용해서 앞에서부터 차례대로 합을 구해놓는 방식으로 풀 수 있음. 여기서 2번 연산을 하려면 수가 바뀔 때 마다 prefix_sum 배열을 변경해줘야 한다. 가장 앞에 있는 0번째 수가 바뀐다면 모든 prefix_sum 배열을 변경해야 하기 때문에 시간 복잡도는 O(N) 따라서, M과 N이 매우 큰 경우에는 결국..! 시간 초과. 세그먼트 트리를 사용하면 O(N) → O(lg N), O(M) → O(lg N) 정의 리프 노드를 제외한 다른 모든 노드는 항상 2개의 자식을 가진다. ⇒ Full Binar.. 2023. 4. 28.
[알고리즘] 헷갈려서 정리해보는 DP 🙀 | 재귀 - Memoization | for 배열 - Tabulation | Top-down & Bottom-up | 문제 유형 피보나치 수와 파도반 수열 동적계획법 알고리즘 마인드를 떠올리기 힘들면 피보나치 수열, 파도반 수열을 떠올려 보자. 재귀함수와 dp의 관계: Memoization Top-down 재귀함수와 dp의 관계는 "비교 대상이자 구현법"이다. 따라서 dp의 특성을 파악하기 위해 먼저 재귀함수에 대한 이해가 필요하다. 재귀함수는 아래와 같은 그림을 기억해두면 이해하기 훨씬 수월하다! 한동안 재귀, 백트레킹 이해를 힘들어 하고 있었는데 재귀 작동 방식과 아래 그림을 연결해서 생각해보니 훨씬 이해가 잘됐다. 재귀 구현 코드는 다음과 같다. n = int(input()) def fibo(n) : if n memoization if m[n] != -1: return m[n] elif n 오 형태로) 바텀업 방식이다. dp.. 2023. 4. 17.
[알고리즘] 이진탐색 Lower/Upper Bound | Python bisect 개요 이진탐색을 하는데 만약 배열에 target 값이 여러 개 존재한다면, 정확한 위치의 값을 도출하는 데에 어려움을 겪을 것이다. 이를 해결하기 위한 알고리즘이 Upper Bound와 Lower Bound이다. Python에서는 bisect라는 도구를 제공한다. Lower Bound target 이상의 값이 최초로 나오는 위치다. 즉, target보다 같거나 큰 원소 중 가장 작은 값의 위치다. 예를 들어서 아래와 같이 정렬된 배열이 존재한다고 가정하자. 1 5 5 5 10 11 100 이 배열의 lower_bound(5) = 5다. 또한 lower_bound(4) = 5다. 가장 작은 값을 구하기 위해서 min_idx 변수를 활용하여 초기값으로 답이 될 수 없는 최댓값을 넣어놓고 문제를 해결한다. l.. 2023. 2. 20.

티스토리툴바