기록보관소

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

스타트링크 문제는 BFS를 사용하여 해결할 수 있는 문제입니다. 시작 층을 하나의 노드로, 도착 층을 하나의 노드로 생각하고 U, D 버튼을 다른 노드로 가는 간선을 나타낸다고 생각하면 BFS로 생각할 수 있습니다. 최소한으로 버튼을 눌러서 도착하기 위해서는 BFS를 사용하여 U, D 버튼으로 이동가능한 모든 노드를 탐색해야 합니다. BFS에 대한 설명은 다음의 게시물에서 확인할 수 있습니다. 2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS DFS와 BFS는 DFS와 BFS에 대한 가장 기초적이면서도 중요한 문제입니다. DFS와 BFS에 대한 충실한 이해가 필요합니다. DFS의 경우 처음 발..

피보나치 함수 문제는 동적 프로그래밍 기법을 사용하여 해결할 수 있는 문제입니다. 피보나치 함수를 재귀함수를 이용하여 계산하게 되면 많은 시간이 걸리게 됩니다. 따라서 배열을 사용하는 동적 프로그래밍 기법을 이용하여 구현하여야만 시간을 절약할 수 있습니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) //https://ark-hive.tistory.com int T; int N; long long fibo[50]; int main(void) { scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%d", &N); for (int j = 0; j 1; j--) { for (int k = 0; k < f..

이분 그래프 문제는 그래프 탐색 알고리즘과 이분 그래프의 정의를 이용하여 해결할 수 있는 문제입니다. 구체적으로 어떻게 해결할 수 있는지에 대해서는 후술 할 내용을 통해 차근차근 탐구해보겠습니다. 이분 그래프는 각각의 집합에 속하는 모든 정점들이 서로 연결되지 않도록 그래프의 모든 정점을 두 개의 집합에 속하도록 나눌 수 있는 그래프를 의미합니다. 즉, 하나의 간선에 대해 한 쪽에서는 집합 1의 정점이 연결되어 있을 때 다른 쪽에는 반드시 집합 2의 정점이 연결되어야만 합니다. 그래프 탐색 알고리즘으로 사용할 BFS는 하나의 정점에서 시작하여 도달할 수 있는 그래프의 모든 정점을 탐색하는 알고리즘입니다. BFS가 그래프를 탐색할 때는 하나의 정점와 간선으로 연결된 모든 정점를 탐색합니다. 이분그래프의 정..

나이트의 이동 문제는 BFS를 사용하여 해결할 수 있는 문제입니다. BFS로 나이트가 이동 가능한 모든 노드들을 탐색하여 목표하는 노드까지의 최단거리를 계산할 수 있습니다. 나이트의 특이한 이동 조건을 잘 고려하기만 하면 문제를 쉽게 풀 수 있습니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) //https://ark-hive.tistory.com/ int T; int I; int board[330][330]; int current[2]; int target[2]; int dx[8] = { 1, 1, 2, 2, -1, -1,-2,-2 }; int dy[8] = { 2, -2, 1, -1, 2, -2, -1, 1 }; struct que { i..