www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수의 범위가 long long 범위를 초과하므로, string을 이용하여 풀어야합니다. 점화식 dp[i] = dp[i-1] + dp[i-2] string 덧셈 길이가 짧은 문자열 앞쪽에 '0'을 추가하여 두 문자열의 길이를 같게 만들어 준 뒤 덧셈연산을 수행하였고 10이상이면 carry를 하나 늘리고 다음자릿수 계산에서 carry가 있으면 1더해주도록 했습니다. ..
전체 글
항공대 알고리즘 동아리 Koala 🥰
www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 동적 계획법을 통해 풀 수 있는 문제입니다. 하나의 스티커를 떼면, 맞닿아있는 3개의 스티커는 뗄 수 없게 됩니다. 이 조건을 지키면서 각 칸마다 얻을 수 있는 최대값을 구해봅시다. 1번 열은 그대로입니다. 2번 열의 10점 스티커가 얻을 수 있는 최대 점수는 10+30점, 2번 열의 50점 스티커가 얻을 수 있는 최대 점수는 50+50점입니다. 따라서 스티커를 선택했을 때 얻을 수 있는 최대 점수로..
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 함수를 실행시킴으로서 정답이 ..