본문 바로가기

알고리즘44

펜윅 트리 쉽게 이해하기. 알고리즘에 입문을 해서 문제를 풀다 보면 구간 합과 관련된 문제를 접하게 된다. 우리는 구간 합 문제를 O(N) 복잡도의 누적 합을 구하고 특정 구간의 원소들의 합을 O(1) 만에 구할 수 있는 방법을 습득하게 된다. 누적 합이 몇인지 묻는 질의(또는 쿼리)가 M개가 주어진다면, 우리는 O(M)의 복잡도로 문제를 빠르게 해결할 수 있다. 만약, 위와 같은 질의 중간중간에 원소의 값이 바뀌는 새로운 질의가 주어진다면 어떻게 해결해야 할까? 매번 O(N)을 수행해서 누적 합을 저장하는 배열의 값을 업데이트해주어야 할까? 그럼 O(NM)의 복잡도로 시간 초과를 받게 될 것이다. 구간 트리 또는 세그먼트 트리(segment tree)라는 것이 있지만 누적 합과 관련된 문제에서 좀 더 간단하게 구현할 수 있는 펜.. 2023. 7. 21.
2-sat 쉽게 이해하기 [boj] 11280 2-SAT - 3 https://www.acmicpc.net/problem/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 2-sat은 2개의 변수가 or (v) 관계로 이어진 1개 이상의 절(clause)을 and (⋀)로 이었을 때, 전체 식의 결과가 true를 반환하는 변수가 존재하냐를 묻는 질문이다. 변수가 4개고 2개의 절이 있는 식 f의 예시는 아래가 있다. ¬ 기호는 not 을 의미한다. 예를 들면, a가 참(true)일 때, ¬a는 거짓(f.. 2023. 6. 13.
2022 성균관대학교 프로그래밍 경진대회 open contest 풀이가없길래 내가 푼 것만 복습 겸 글을 써본다.. https://www.acmicpc.net/problem/24523 24523번: 내 뒤에 나와 다른 수 첫째 줄에 수열 $A$의 크기 $N$이 주어진다. 둘째 줄에는 $A_1 \ A_2 \ \cdots \ A_N$이 공백으로 구분되어 주어진다. $(1 \le N \le 10^6$, $-10^9 \le A_i \le 10^9 )$ 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net A번. 특정 수열이 있을 때 i번째 수 다음으로 A[i]와 다른 A[j] 중 j가 가장 작은 것을 고르는 문제입니다. 맨 뒤부터 다른 수 2개를 찾아 p1, p2에 인덱스를 저장하여 맨 앞까지 반복하면서 조건에 따라 p1과 p2를 업데이트 합니다. 먼저 p1과.. 2022. 3. 2.
[BOJ] 백준 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 n개의 동전의 가치가 주어질 때 동전을 원하는 대로 사용하여 k원을 만드는 경우의 수를 구하는 문제입니다. 동적 계획법 관련 문제들에서 이 문제와 유사한 문제들이 가끔 출제되며 이 문제를 잘 이해하고 풀면 0/1 배낭 문제 또한 쉽게 풀 수 있습니다. 풀이 쉽게 접근해 보기 위하여 dp [i][j]를 0~i 번째 동전을 사용하여 j원을 만들 때 적어도 한 개의 i번째 동전을 사용하는 경우의 수.. 2021. 3. 24.

티스토리툴바