복습노트 복습노트

문제 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net N개의 트리 정점이 주어지고 두 노드의 쌍 M개가 주어졌을 때 두 노드의 가장 가까운 공통 조상이 몇번인지 출력하는 문제입니다. naive하게 생각하면 시간복잡도가 O(N)이므로 범위가 커지게 되면 시간초과가 나게 됩니다. 따라서 Sparse Table 알고리즘 방식을 사용하였습니다. 먼저 par[x][y] = x노드의 2^y 부모 라는 배열을 정의합니다. 다음에 depth배열을 정의해줍니다. depth배열은 노드의 깊이를 저장한 배열입니다. LCA..

문제 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 정의역과 공역 문제 입니다. m개의 정수가 주어지면 각 정수마다 f(1), f(2)....f(m)의 위치를 갖습니다. 쿼리의 갯수 Q가 주어지면 Q개의 쿼리마다 정수 n과 x가 주어지면 n번의 f(x) 연산을 한 값을 출력하면 되는 문제입니다. naive하게 계산하면 총 O(n)번의 연산을 통해 계산 가능합니다. 하지만 m..

Sparse table이란 행렬 중에서 행렬의 값의 대부분이 0인 경우를 나타내는 행렬 우리가 그래프를 표현하는 방식 중에 인접 행렬 방식을 활용할 때에 있어서 특수한 경우에는. 그래프의 모든 정보를 표현할 필요 없을 때가 있다. 예시 문제 백준 17435 (합성함수와 쿼리) c++ 문제 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(.. riveroilstone.tistory.com LCA는 트리에서 사용되는 개념이다.(최소공통조상) 트리에 존재하는 어떤 두 정점에..

문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 유명한 knapsack 알고리즘 문제 입니다. n개의 물건들이 주어지고 각 물건들은 무게 w와 가치 v가 주어집니다. 가방은 최대 무게 k만큼 짐을 넣을 수 있습니다. 가치를 최대로 하면서 가방에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제입니다. dp를 활용해서 문제를 해결하였습니다. dp[i][j] = i번째 물건을 확인하고 있고 가방의 최대 무게가 j일때 가방에 담긴 물건들의 최대..

문제 Problem - D - Codeforces codeforces.com 1원짜리, 2원짜리, 3원짜리 동전만 사용가능할 때 물건의 가격이 n개 주어지면 가장 최소한의 동전 갯수로 n개의 물건중 아무거나 1개 살 수 있을때 최소한의 동전 갯수를 구하는 문제입니다. 가격은 거스름돈 없이 정확히 맞아 떨어져야 합니다. 예를 들어 n = 3이고 물건의 가격들이 각각 10, 8, 10 이라면 최소한의 동전 갯수는 2원짜리 2개 + 3원짜리 2개 로 (2, 2, 3, 3) 8원도 살 수 있고 10원도 살 수 있습니다. 따라서 최소 동전 갯수는 4개 입니다. 필요한 동전의 개수를 최소화 하는 것이기 때문에 3원짜리 동전이 많이 있으면 좋습니다. 따라서 3원짜리 동전을 최대화하고 나머지 가격은 3원보다 낮을 것이..

실전문제 풀이! 자료구조나 알고리즘의 활용

문제 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 배열 A(1) ~ A(n) 까지 주어지면 임의의 구간 [i, j] (A(i)+ ~ +A(j))에서의 합이 m으로 나누어 떨어지는 (i, j) 쌍의 개수를 구는 문제 입니다. 단순히 prefix sum을 이용해서 구간의 합인 [i, j]를 구하기 위해 prefixsum[j] - prefixsum[i-1]을 하게 되면 끝점 j를 잡고 이중 for문을 돌리게 되면 시간 복잡도가 O(n^2)이 나와서 시간초과가 나오게..

문제 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net N X N 의 2차원 배열이 주어지고 (x1, y1) ~ (x2, y2) 까지의 합을 구하는 문제입니다. 예를 들어 n = 4 이고 (2, 2) ~ (3, 4) 구간의 합을 구하고 싶으면 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 빨간색 부분의 합을 구하면 됩니다. prefix sum 형태로 해결하였습니다 psum[x][y] = (1, 1) 부터 (x, y)의 합으로 정의 하였습니다. 예를 들어 psu..