전체 글34 Union Find Disjoint Set (UFDS) 유니온 파인드 상호배타적 집합 상호 베타적인 집합들을 모델랑하는 자료구조이다. 여기서 상호베타적이라는 말은 임의의 두 집합의 교집합이 공집합이라는 뜻이고 이는 각집합이 서로 서로소임과 동치이다. 이 자료구조를 이용하면 어떤 원소가 어느 집합에 속해 있는지를 판별하는 작업, 혹은 두 원소가 동일한 집합에 속하는지 판별하는 작업, 그리고 상호 베타적인 두 집합을 더 큰 하나의 집합으로 합치는 작업을 거의 O(1)이라는 시간 복잡도에서 해낼 수 있다. 이를 이용하여 해결할 수 있는 대표적인 문제로는 무방향 그래프의 연결된 컴포넌트를 찾는 문제를 풀 수 있다. 각 그래프의 정점을 별개의 상호 베타적 집합으로 초기화 하고, 두 정점을 잊는 간선을 탐색하며 두정점이 속한 집합을 하나의 집합으로 합친다. 이와 같은 .. 2018. 1. 18. GRID https://algospot.com/judge/problem/read/GRID 문제 We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled. Write a program that takes as input the width, W, of the grid and outputs the number of different ways to tile a 4-.. 2017. 10. 17. DICT https://algospot.com/judge/problem/read/DICT 문제 (주의: 이 문제는 TopCoder SRM428 Div2 Hard 의 번역 문제입니다.) a 와 b 로만 이루어진 단어들을 담고 있는 사전이 있다. 이 사전은 n 개의 a 와 m 개의 b 로 이루어진 단어들을 _전부_ 포함하는데, 예를 들어 n=2, m=2 인 경우, 사전에는 aabb, abba 등의 단어들이 포함된다. n 과 m 이 주어질 때, 이 사전의 k 번째 단어를 출력하는 프로그램을 작성하라. 단어들은 사전 순서대로 정렬되어 있다고 가정한다. 입력 입력의 첫 줄에는 테스트 케이스의 수 C ( m >> k; if (c[n + m][n] < k || (n == 0 && m == 0)) { cout 2017. 10. 14. CHANGE https://algospot.com/judge/problem/read/CHANGE 문제 Sue is waiting in line at the grocery store. Being in a hurry, she wants to pay with exact change when she gets to the front of the line. However, she does not know how much her items are going to cost; instead, she only knows an upper bound C on their total cost. Given a list of the various coins Sue has in her pocket, your goal is to determine .. 2017. 8. 28. CAKECUT https://algospot.com/judge/problem/read/BOOKTHIEF 문제 You are given a rectangular cake of integral dimensions w × h. Your goal is to divide this cake into m rectangular pieces of integral dimensions such that the area of the largest piece is minimal. Each cut must be a straight line parallel to one of the sides of the original cake and must divide a piece of cake into two new pieces of positive a.. 2017. 8. 22. FENCE https://algospot.com/judge/problem/read/FENCE 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다. 판자의 너비는 모두 1이라고 가정합니다. 위의 문제를 푸는 방법은 다양하다. 하지만 그중에서도 분할정복으로 .. 2017. 8. 18. MATEXP https://algospot.com/judge/problem/read/MATEXP 행렬의 자승은 동적 계획법의 선형 점화식을 빠르게 계산하는 등의 여러 용도에 유용하게 쓰인다. 크기 100 이하의 정방행렬 A 와 1 이상의 정수 p 가 주어질 때, Ap 을 계산하는 프로그램을 작성하여라. 단 행렬의 큰 자승을 계산할 경우 숫자가 매우 커질 수 있기 때문에, 행렬의 각 원소에 대해 10007 에 대한 나머지를 계산하기로 한다. 간단하다 분할정복을 이용해서 풀면 끝!! 연산자 오버로딩을 통한 행렬의 곱만 정의해주면 궂이 그 외적으로 할게 없는 문제이다. 2017. 8. 17. QUADTREE https://algospot.com/judge/problem/read/QUADTREE 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니.. 2017. 8. 16. CHRISTMAS https://algospot.com/judge/problem/read/CHRISTMAS 이 문제는 인형 구매를 위한 조건을 수식으로 나타내고 수식을 적절한 형태로 변화시키면 반정도 풀었다고 생각된다. 하지만 여기서 오버플로우를 신경 못쓴다면 AC를 받지 못한다. 절대로...ㅋ 문제는 아래와 같다. 크리스마스를 맞이하여 산타 할아버지는 전세계의 착한 어린이 K명에게 인형을 사주려고 한다. 산타 할아버지는 인형을 구입하기 위해서 유명한 인형가게인 "놀이터"에 찾아갔다. 놀이터에는 N개의 인형 상자가 한 줄로 진열되어 있고, 각 인형 상자에는 한 개 이상의 인형이 들어 있다. 그리고 놀이터에서는 주문의 편의성을 위해 각 상자에 번호를 붙여 놓았고, 주문은 "H번 상자부터 T번 상자까지 다 주세요."라고만 할.. 2017. 8. 15. 중복 조합 n 종류의 물건이 있고 i번째 물건은 ai개 있습니다. 다른 종류의 물건끼리는 구별 가능합니다만, 같은 종류의 물건끼리는 구별 불가능합니다. 이들 물건 중에 m개를 골라 조합해 총수를 구하고M으로 나눈 나머지를 구하세요. 위의 문제는 다른 종류의 물건끼리는 구별이 가능하므로 아래와같이 점화식을 세울 수 있다. dp[i + 1][j] = i까지의 숫자를 이용하여 j개를 조합할 수 있는 총 갯수 i - 1번째 까지의 숫자를 이용하여 j - k개를 고르고 나머지 k개를 i번째 수에서 고르는 경우를 모두 더하면 i까지를 이용하여 j개를 고르는 모든 조합을 구할 수있다. dp[i + 1][j] = dp[i][j - k] (0 2017. 8. 10. LIS(최장 증가 부분열) 길이가 n인 수열 a0, a1, ... , an - 1이 있습니다. 이 수열의 증가 부분열 중 최장의 것의 길이를 구하세요. 단 증가 부분열이란 모든 i < j 에서 ai < aj를 만족하는 부분열을 말합니다. !제약 1 2017. 8. 9. 갯수 제한이 있는 부분합 n 종류의 수 a[i]가 각각 m[i]개씩 있습니다. 이들 중 몇개를 골라 그 합이 K가 될 수 있는지 판정합시다. !제약 1 2017. 8. 9. BILLS https://algospot.com/judge/problem/read/BILLS 문제 After being retired from ACM-ICPC, Mr. R decided to quit studying computer science to become a farmer. This year, he harvested N cabbages, and the price of one cabbage is K won. R wants to sell all of these cabbages to the Farm Co-Op, but the Farm Co-Op has a rather complicated purchasing policy: R can split the cabbages into any number of bunches.. 2017. 8. 4. Unbounded Knapsack Problem(갯수 제한없는 배낭문제) 무게와 가격이 각각 Wi, Vi인 n개의 물건이 있습니다. 이 물건들로부터 무게의 총합이 W를 초과하지 않도록 선택했을 때의 가격 총합의 최대치를 구하세요. 단 같은 종류의 물건을 몇 개라도 고르는 것이 가능합니다. 일반적인 배낭문제를 생각하고 점화식을 정의하면 아래와 같다. dp[i + 1][j] = i번까지 물건 무게의 총합이 j 이하가 되도록 골랐을 때 가치의 최대치 dp[i][0] = dp[0][j] = 0 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]) (j >= k * w[i]) 이와 같은 점화식으로 코드를 구현하면 아래와 같다 int dp[MAX_N + 1][MAX_W + 1]; void solve() { for(int i = 0;.. 2017. 8. 4. 최장 공통 부분열(DP) 문자열 S1, S2, ... , Sn과 T1, T2, ... , Tn이 주어져 있습니다. 이 둘의 공통 부분 문자열의 길이의 최대 값을 구하세요. 단 문자열 S1S2...Sn의 부분 문자열이란 Si1, Si2, ... Sim(i1 < i2 < ... < im)로 표현 가능한 문자열을 말합니다. 제약 1 2017. 8. 4. 이전 1 2 3 다음