기록보관소

상근날드 문제는 반복문을 이용한 단순 연산 문제입니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) int bugger[3]; int drink[2]; int min = 0x0fffffff; int main(void) { scanf("%d %d %d", &bugger[0], &bugger[1], &bugger[2]); scanf("%d %d", &drink[0], &drink[1]); for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) { if (bugger[i] + drink[j] - 50 < min) { min = bugger[i] + drink[j] - 50; } } } printf("%..

피보나치 수 2는 다이나믹 프로그래밍으로 해결할 수 있는 문제입니다. 피보나치 수를 구하기 위해 피보나치 수를 보관할 배열을 선언한 후 반복적인 연산을 통해 피보나치 배열을 업데이트시켜 최종적으로 원하는 피보나치 수를 구하도록 하여야 합니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) long long int fibo[120]; int N; int main(void) { fibo[0] = 0; fibo[1] = 1; scanf("%d", &N); if (N == 0) printf("%d\n", fibo[0]); else if (N == 1)printf("%d\n", fibo[1]); else { for (int i = 0; i < N-1; i..

A+B-6는 단순한 연산 문제이다. 본 글에서는 c언어를 이용하여 코드를 작성하였습니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) //https://ark-hive.tistory.com int T; int A, B; int main(void) { scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%d,%d", &A, &B); printf("%d\n", A + B); } } 문제는 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/problem/10953

가장 긴 증가하는 부분 수열 2는 이분법을 사용하여(솔직히 이 문제의 핵심은 이분법이 아닌 것 같습니다. 이분법만 아는 것으로는 조금 부족할 수도 있을 것 같습니다.;) 풀 수 있는 문제입니다. 원래 문제인 가장 긴 증가하는 부분 수열(LIS)문제는 동적계획법(완전탐색 + 메모이제이션)으로 해결할 수 있으나 N의 개수가 100만이 되어서 더 빠른 방식의 알고리즘을 고안해야 합니다. 문제를 곰곰히 생각해보면 다음과 같은 통찰을 얻을 수 있습니다. 수열의 어떠한 위치를 탐색하고 있다고 가정하면 우리는 그 이전의 수들로만 구성된 수열들을 상상할 수 있습니다. 어떤 수열은 1개의 숫자로만 이루어질 수도 있고, 어떤 수열을 2개, 3개 혹은 그 이상의 숫자로 만들어질 수 있을 것입니다. 우리가 구하고자 하는 것은..

K번째 수 문제는 최적화 문제를 결정 문제로 바꾸어 푸는 유형의 문제로 볼 수 있습니다. K번째 수를 X로 가정하면 X보다 작거나 같은 수는 K개 이상이라는 사실을 알 수 있습니다. 그보다 작으면 K번째 수가 될 수 없기 때문입니다. 작거나 같은 수가 K개 이상인 수 중 가장 작은 값을 찾는 문제로 생각해볼 수 있습니다. 이와 같은 최적화 문제를 X이상의 수에 대해 자기 자신보다 작거나 같은 수를 K개이상 가지고 있는지 확인하는 결정문제로 바꿀 수 있습니다. 이러한 결정문제는 이분법을 이용하여 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) //https//ark-hive.tistory.com int N, K; int min(..

공유기 설치는 최적의 값을 찾는 문제를 참과 거짓을 결정하는 문제로 변환하여 이분법을 통해 해결할 수 있는 문제입니다. 문제의 지문을 그대로 해석하면 가장 인접한 공유기의 거리의 최대값을 구하는 문제로 생각할 수 있습니다. 이러한 최적화 문제를 참과 거짓을 결정하는 결정 문제로 변환하여 이분법을 이용하여 쉽게 해결할 수 있습니다. 위의 최적화 문제를 다음과 같은 결정 문제로 변환할 수 있습니다. "가장 인접한 공유기의 거리가 x이상이 되도록 공유기를 설치할 수 있을까" 이 질문에 대해서는 참 또는 거짓으로만 답을 할 수 있습니다. 만약 이 질문의 답이 참이라고 가정하면 가장 인접한 공유기의 거리가 x 이하인 모든 값으로 설치가 가능하다는 자명한 사실을 알 수 있습니다. 따라서 x이하의 값에 대해서는 더 ..

나무 자르기 문제는 최적화 문제를 결정 문제로 변환하여 푸는 기법을 통해 해결할 수 있는 문제입니다. 적어도 ~이상의 나무를 가져가기 위해 전기톱을 최대한으로 설정할 수 있는 높이를 구하는 최적화 문제를 참, 거짓의 결정 문제로 변환하여 이분법으로 빠르게 해결할 수 있습니다. 최대의 값을 구하기를 결정 문제로 변환하면 "나무를 어떠한 값 이하로 잘랐을 때 적어도 ~만큼 가져갈 수 있는가?"라는 질문을 할 수 있습니다. 이 질문에 대해 참, 거짓으로 답을 하게 되면 그 값을 기준으로 이하나 이상에 대해서는 더 이상 질문을 할 필요가 없어지게 됩니다. 이분법의 논리와 같다는 사실에서 이분법을 그대로 적용하여 결국에는 최적의 값을 찾을 수 있게 됩니다. 작성한 코드는 다음과 같습니다. #include #pra..

평균 점수 문제는 평균을 구하는 문제입니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) int score[5]; int sum; int main(void) { for (int i = 0; i < 5; i++) { scanf("%d", &score[i]); if (score[i] < 40) score[i] = 40; sum += score[i]; } printf("%d\n", sum / 5); } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/problem/10039