본문 바로가기

3. 알고리즘 공부

 (49)
[451] 백준 2240번 - 자두나무(DP 문제의 재미) 1. 문제https://www.acmicpc.net/problem/22402. 문제 이해물체의 상태는 1 또는 2이고 처음 상태는 1입니다.물체에게 정보가 1 또는 2가 임의로 최대 1000번 까지 순차적으로 주어지며, 물체의 상태와 같다면 값이 1 증가합니다.물체는 정보가 주어질 때 자신의 상태를 바꿀 수 있으며 바꾸는 횟수는 최대 30번입니다.이 때 얻을 수 있는 최대값을 구하는 문제입니다.3. 해결 방법가. 상태 변화 횟수와 현재 상태의 관계상태는 두 개(1 또는 2)이고, 처음 상태는 1로 고정이 되어 있습니다.상태를 홀수 번(1번, 3번, 5번, ...) 바꾼다면 상태는 2가 됩니다.상태를 짝수 번(0번, 2번, 4번, ...) 바꾼다면 상태는 1이 됩니다.다시 말해 상태 변화 횟수로 현재의 상..
[450] 백준 15486번 - 퇴사 2(DP 역순) 1. 문제https://www.acmicpc.net/problem/154862. 문제 이해상담원에게 상담을 할 수 있는 기간, 그리고 그 기간동안 매일 하나씩 상담이 주어집니다.각 상담은 완료까지 며칠이 걸리는지가 주어지고, 완료했을 때 가치가 주어집니다.상담원은 상담을 선택할 수도 있고 안 할 수도 있습니다.대신 상담이 진행 중이라면 새로운 상담을 선택할 수 없습니다.이 때 상담원이 얻을 수 있는 최대 가치를 구하는 문제입니다.각각 n개의 칸에서 시작하는 적당한 길이(T)의 막대가 있고, 막대에 값(P)이 정해져 있는 상황으로 바꾸어 생각할 수 있습니다.겹치지 않게, 그리고 n을 넘지 않게 막대를 적당히 골라, 값의 합을 가장 크게 하는 문제로 바꾸어 이해할 수 있습니다.3. 해결 방법막대를 순서대로..
[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..

티스토리툴바