![]()
www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 이 문제는 동적 계획법을 2차원 배열에 적용하여 풀 수 있습니다. 두 문자열을 각각 A와 B라고 할 때, 2차원 배열의 가로는 문자열 A, 세로는 문자열 B로 지정하고, 인덱스 마다 해당 지점까지 존재할 수 있는 가장 긴 부분 문자열의 길이를 저장하면 됩니다. 해당 지점 (X, Y). A문자열의 X까지, B문자열의 Y까지 등장할 수 있는 공통 부분 문자열의 길이는 A의 X - 1까지, B의 Y - 1..
문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 더보기 n의 크기를 키워가며 방법의 수를 구하다 보면 피보나치 수의 규칙을 찾을 수 있다. 3번째 이후부터 Fn = Fn-1 + Fn-2 규칙을 적용할 수 있다. 따라서 0,1,2,3 번째까지의 vector는 초기화를 해준다. 그리고 vector의 크기가 기하급수적으로 커지는 것을 막기 위해 최종적으로 구해야하는 수인 2xn 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 저장한다. 소스코드 #include #include #include #include using namespace std; int..
문제 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. 1, 1, 2, 3, 5, 8, ... 타일의 개수 N(1 ≤ N ≤ 80)이 주어졌을 때, N개의 타일로 구성된 직사각형의 둘레를 구하는 프로그램을 작성하시오. 풀이 더보기 반복적으로 문제의 직사각형을 구성하는 정사각형들을 구하다보면 각 정사각형의 한 변이 피보나치 수임을 알게 된다. 그리고 타일의 수의 합을 n이라 하면 정사각형의 한 변이 n번째 피보나치 수이..
www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [2225번] 합분해 0부터 N까지의 정수 중 K개를 더한 값이 N이 되는 경우의 수를 구하라. 덧셈의 순서가 바뀐 경우는 다른 경우에 해당하고, 한 개의 수를 여러 번 사용 가능하다. 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력하라 만약 N = 20, K = 1 일 때, 0 ~ 20까지의 정수 중 1개를 더한 값이 20이 되는 경우의 수는 1이다. 이를 dp로 표현하기 위해 2차원 배열을 정의하면 dp[N][K] : 정수 N을 K개의 정수의 합으로 만들 수 있는 경우의 수 더보기 N = 20, K = 1 dp[0][..
문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 풀이 더보기 n을 입력받은 뒤 피보나치 수의 공식( Fn = Fn-1 + Fn-2)을 이용한 함수를 만든다. vector 를 이용하여 피보나치 수를 저장한다. 초기값으로 0번째 수는 0, 1번째 수는 1로 초기화 시켜놓는다. 최종적으로 n번째 피보나치 수를 출력한다. 소스코드 #include #include #include #include using namespace std; int N; vector num; long long result = 0; int fib(int a..
알고리즘 헤더파일에는 배열의 정렬을 쉽게 처리해주기 위한 sort가 내장되어 있습니다. 오름차순 정렬, 내림차순 정렬과 Pair가 있을 때 내맘대로 정렬하는 법을 살펴보겠습니다. 1. 오름차순 정렬 정렬할 배열과 범위를 정해주면, 기본적으로 오름차순으로 정렬해줍니다. c++의 sort함수는 quick sort로 구현되어 있습니다. sort(a, a + 10, less()); 오름차순이 기본이므로, 세번째 인자를 제외해도 오름차순 정렬이 됩니다. sort(a, a + 10); #include #include #include #include using namespace std; int main() { int a[10] = { 1,5,4,6,7,10,9,2,3,8 }; sort(a, a + 10);..
![]()
youtu.be/neR0Dmct6E8 youtu.be/D9Vf4L-a76k
![]()
문제 링크 codeforces.com/contest/1473 Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces codeforces.com A. Replacing Elements 문제 양의 정수로 이루어진 수열 a가 주어질 때, 다음과 같은 작업을 할 수 있다. 서로 다른 인덱스 i, j, k를 고른 후, ai = aj + ak 로 바꿀 수 있다. 이 작업을 무한정 할 수 있다고 할 때, 수열 a의 모든 수를 d보다 작거나 같게 만들 수 있는가? 풀이 1 더보기 이 문제의 경우 두 가지 case일 때, 문제 조건을 만족시킬 수 있습니다. 1. 모든 수가 d보다 작거나 같을 때, 작업을 하지 않고 그대로 정답이 됩니다. ..
www.acmicpc.net/problem/2992 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 두가지 풀이를 가지고 왔습니다. 1. 첫번째는 풀이는 강의에서 소개해주신 next_permutation 함수를 이용하는 방식입니다. 코드가 매우 직관적이고 간결합니다. string변수로 입력을 받고난뒤 next_permutation 함수를 1번 실행시키면 문제에서 요구하는 "크면서 작은 수"를 얻을 수 있습니다. if 조건문 내부에서 next_permutation 함수를 실행시킴으로서 정답이 ..
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 주어진 N개의 숫자 중 부분수열의 합이 S를 만족시키는 수열의 개수를 찾는 문제이다. 백트래킹을 이용해 모든 경우의 수의 수열을 뽑아낸뒤 그 수열의 합이 S를 만족시킨다면 카운트를 하는 방식으로 접근하였다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #..
![]()
www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 이 문제는 주어진 DNA들에대해 Hamming Distance의 합이 가장 작은 DNA하나를 찾고, 그, Hamming Distance의 합을 구하는 문제입니다. *Hamming Distance : 두 DNA가 있을 때 각 위치의 뉴클오티드 문자가 다른 것의 개수 입력받은 DNA들과의 Hamming Distance 합이 최소가 되기 위해서는 각 열 별로 빈도가 가장 ..
