본문 바로가기

3. 알고리즘 공부

 (47)
[446] 느리게 갱신되는 세그먼트 트리(lazy propagation) 1. 세그먼트 트리 동작 과정세그먼트 트리는 루트 노드에서 리프 노드까지 범위를 나누어 가며 통일된 연산값을 유지해야 합니다.따라서 자식 노드에서 부모 노드로 올라가더라도 더 넓어진 범위에 대해 연산 결과를 유지할 수 있어야합니다.이게 가능한 연산은 최대, 최소, 덧셈, 곱셈 등 일부의 결과로 전체 범위에 적용이 가능한 연산을 세그먼트 트리에 적용할 수 있습니다. 8 크기의 배열에서 3, 2, 5, 3, 5, 2, 3, 4의 값을 가지고 있고, 구간합을 관리하는 세그먼트 트리는 다음과 같습니다. 이 세그먼트 트리에서 2 ~ 8 범위의 구간합을 구하고 싶다면 다음과 같이 구합니다. 찾고자 하는 범위 안에 포함될 때까지 자식으로 내려가며 합을 구하면, 2+8+14로 24라는 것을 알 수 있습니다.다음으로 세..
[445] 다익스트라 알고리즘으로 최단경로의 모든 정점 찾기 1. 다익스트라 알고리즘다익스트라 알고리즘을 순서대로 나타내면 다음과 같습니다.단순한 최단경로 찾기는 위와 같이 풀 수 있습니다.하지만 최단경로 상의 모든 정점을 찾고 싶을 때는 위의 과정 중에 추가적인 알고리즘이 필요합니다.2. 다익스트라 알고리즘으로 최단경로의 정점 찾기우선순위 큐에 다음 정점에 대한 정보를 추가할 때, 가중치를 더 작은 값으로 하는 간선 정보를 저장합니다.최단경로 탐색이 종료되면, 간선 정보를 담은 표를 가지고 역으로 거슬러 올라가며 최단경로 상의 모든 정점을 순서대로 확인할 수 있습니다.
[443] 순열, 조합, 중복순열, 중복조합 구현하기(파이썬 코드) - itertools 없이 1. 순열arr = [1, 2, 3]used = [False] * len(arr)def perm(arr, r): for i in range(len(arr)): if not used[i]: used[i] = True if r == 1: yield [arr[i]] else: for nxt in perm(arr, r-1): yield [arr[i]] + nxt used[i] = False print(*perm(arr, 3), sep="\n")# [1, 2, 3]# [1, 3, 2]# [2, 1, 3]# [2,..
[442] 백준 1979번 - 극적인 곱셈 1.  문제https://www.acmicpc.net/problem/19792. 문제 이해n, k 가 주어졌을 때, 위 그림과 같이 k로 끝나는 어떤 수에 n을 곱한 결과가 그 어떤 수를 오른쪽으로 한 칸씩만 옮겨진 수와 같은 결과가 되도록 하는 어떤 수를 구하는 문제입니다.3. 해결 방법찾고자 하는 수의 일의 자리 숫자는 무조건 k입니다.따라서 n을 곱한 값의 일의 자리 숫자는 (k*n)%10이고, 구하고자 하는 어떤 수의 십의 자리도 (k*n)%10이 됩니다.이제 구한 수를 a라고 하면 n을 곱한 값의 십의 자리 숫자는 (a*n)%10 에 (k*n)//10을 더한 값이 됩니다.그리고 그 수는 구하고자 하는 수의 백의 자리 값이 됩니다.이제는 이 과정을, 곱한 값에 다시 k가 나올 때까지 반복합니다.4..
[441] PS에서 C++의 빠른 입출력 방법 빠른 입출력 코드// 1#include using namespace std; // 2int main() { ios_base::sync_with_stdio(false); // 3 (중요) cin.tie(nullptr); // 4 (중요) int a, b; cin >> a >> b; cout 1. #include C++에서 #을 사용하는 키워드를 전처리기 지시문(Preprocessor Directives)이라고 합니다.전처리기 지시문은 컴파일 되기 전에 수행할 작업들을 정의합니다.#include는 파이썬의 import와 같은 역할을 합니다.그리고 파이썬에서 import의 대상을 모듈이라고 했던 것과 비슷하게, C++에서는 #include의 대상을 헤더파일이라고 합니다. iostre..
[440] 조합(combination) 큰 수 계산하기(모듈러) - 파이썬 1. 조합 계산 코드(파이썬)n = 1000000r = 500000MOD = 1000000007facto = [1]*(n+1)inv_facto = [1]*(n+1)for i in range(2, n+1): facto[i] = facto[i-1] * i % MODinv_facto[n] = pow(facto[n], MOD-2, MOD) # 페르마의 소정리for i in range(n-1, -1, -1): inv_facto[i] = inv_facto[i+1] * (i+1) % MODdef nCr(n, r): return facto[n] * inv_facto[r] % MOD * inv_facto[n-r] % MODprint(nCr(5, 3))# 10print(nCr(10, 4))# 210prin..
[439] 모듈러 연산의 나눗셈(확장 유클리드 알고리즘, 페르마 소정리) 1. 모듈러 연산의 기초예전에  모듈러 연산과 관련된 포스팅을 올린 적이 있습니다.모듈러 연산의 분배 법칙을 알아보았지만, 나눗셈의 분배 법칙은 키워드 정도만 안내하고 넘어갔습니다.\((a+b) \text{ mod } c  = \big((a \text{ mod }{c}) + (b \text{ mod }{c})\big) \text{ mod }{c} \)\((a-b) \text{ mod }{ c } = \big((a \text{ mod }{c}) - (b \text{ mod }{c})\big) \text{ mod }{c} \)\((a \times b) \text{ mod }{ c } = \big((a \text{ mod }{c}) \times (b \text{ mod }{c})\big) \text{ mod ..
[438] 팰린드롬 부분 문자열(Manacher's algorithm)(파이썬 코드) 1. Manacher's algorithm우리말로는 마나커, 마나허, 매내처 등으로 불리는 알고리즘입니다.어떤 문자열에서 팰린드롬인 모든 부분 문자열을 \(\mathbf{O(n)}\)만에 찾을 수 있는 알고리즘입니다.코드는 다음과 같습니다.def manacher(S: str): S = "*"+ "".join([c+"*" for c in S]) length = len(S) radius = [0] * length old_center = 0 old_radius = 0 for center in range(length): if old_center+old_radius = 0 and \ center+radius[center]+1 2. 동작 원리먼저 팰린..

티스토리툴바