분류 전체보기

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. 알고리즘은 다음과 같다. 입력된 두 개의 문자열을 비교하면서 LCS(최장 공통 부분 수열)을 찾는 문제로, 가능한 수열을 하나하나 비교하면 시간 초과이기 때문에, dp를 이용하는 문제이다. 입력 값으로 표를 만들어 보면 아래와 같은 표가 만들어진다. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 이 문제는 DP를 통한 누적합을 구하는 문제이다. DP를 통해 누적합을 구하기 위해서 아래 식을 사용한다. 누적합(X, Y) = 누적합(X-1, Y) + 누적합(X, Y-1) - 누적합(X-1, Y-1) + 요소(X, Y) 누적합 (X-1, Y-1)을 빼는 이유는 누적합 (X-1, Y) + (X, Y-1)에서 (X-1, Y-1)이 공통으로 들어가 한번만 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. 알고리즘은 다음과 같다. 2N개의 데이터를 삽입시켜야 하므로 2차원 배열을 사용했다. DP배열도 2N만큼 생성한다. 0번 줄의 0번째 스티커와 1번 줄의 0번째 스티커는 (0,0) (1,0)의 값을 그대로 삽입한다. 0번 줄의 1번째 스티커와 1번 줄의 경로를 누적한다. 2번째 스티커부터 같은 패턴으로 경로가 누적된다. i-2 전의 경로와 i-1..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. 알고리즘은 다음과 같다. 삼각형의 최대 크기는 500까지이다. 따라서 501x501크기의 배열을 선언하여 삼각형의 비용을 저장한다. DP를 위한 배열은 삼각형의 크기와 동일하게 선언한다. (모든 경로의 비용을 계산하기 위해) dp 배열의 첫번째 경로와 두번째 경로를 저장한다. 반복을 통해 왼쪽 경로와 오른쪽 경로를 계속해서 저장한다. 겹치는 노드가 있기 떄문에 max 함수를 통해 최대 값인 경우를 저장한다. max 함수는 위아래..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 벡트래킹을 통해 해결할 수 있다. 알고리즘은 다음과 같다. 입력 배열의 요소를 정렬한다. (오름차순 출력을 위해) dfs를 0번 요소부터 수행한다. 만약 M번째 자리까지 탐색했다면 출력한다. 0번째 요소부터 N번째 요소까지 반복을 진행한다. 이때 방문하지 않았으며, i번째 배열의 요소가 중복된 값이 아니라면 출력을 위한 배열에 값을 삽입하고, 중복 값 검사를 위한 변수에 i번째 요소를..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 이 문제는 DFS를 통해 해결할 수 있다. 알고리즘은 다음과 같다. M개의 간선에 대해 정보를 받아 go, to와 to, go에 대해 그래프를 설정한다. N개의 정점에 대해 탐색을 시작하는데 방문하지 않았다면 DFS를 수행하고 연결 요소 수를 증가시킨다. DFS는 방문하지 않은 노드가 없을 때 까지 계속해서 진행한다. 모든 노드를 검..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제는 DFS를 통한 백트레킹으로 해결할 수 있다. 알고리즘은 다음과 같다. 입력받은 N개의 숫자를 vector에 삽입하고, 삽입이 끝나면 오름차순으로 정렬한다. DFS를 0번째 인덱스, 1번째 자리부터 시작한다. num번째 부터 N까지 반복하며 DFS를 수행하면 주어진 조건에 맞게 출력할 수 있다. #include #include #include using namespace std;..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제는 DFS를 통한 백트레킹으로 해결할 수 있다. 알고리즘은 다음과 같다. vector에 N만큼의 입력 값을 삽입하고, 삽입이 끝나면 sort를 통해 오름차순으로 정렬한다. DFS를 0번 인덱스 부터 수행한다. 방문하지 않은 인덱스라면 방문 표시를 하고 cnt자리에 i번째 인덱스를 삽입한다. (DFS의 값) num은 필요하지 않은 값이지만 넣어버렸다.(실수) #include #inc..