기록보관소

스타트링크 문제는 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..

총 수입(Total Revenue)는 공급자들이 재화를 수요자들에게 공급하고 받은 금액을 의미한다. 재화의 가격 * 총 수요를 계산하여 총 수입을 구할 수 있다. 수요가 비탄력적인 경우 가격의 상승률이 수요의 하락률보다 높으므로 총 수입이 감소한다. 반면 수요가 탄력적인 경우 가격의 상승률이 수요의 하락률보다 낮으므로 총 수입이 증가한다. 탄력성이 1인 경우 가격의 변동에도 총 수입은 그대로 유지된다.

수요곡선은 그것의 탄력성에 의해 5가지로 분류될 수 있다. 탄력성이 0인 경우, 0보다 크지만 1보다 작은 경우, 1인 경우(단위탄력적), 1보다 크지만 무한대보다 작은 경우, 무한대인 경우가 있다. 하나의 수요곡선에서 탄력성을 달라질 수도 있다. 직선 형태의 수요 곡선의 경우 가격과 수요의 변화량의 비율은 일정한 상수이지만 변화율을 일정하지 않다. 가격과 수요의 크기가 반비례하고 같은 량만큼 변할 때 초기 값의 크기가 다르기 때문이다. 보통 특정 지점을 기준으로 탄력적, 비탄력적으로 분할된다. 총 수입 또한 같이 늘어났다 줄어든다.

벽 부수고 이동하기는 변형된 BFS 문제입니다. BFS를 기반으로 문제를 풀어야 하지만 벽을 1회 부술 수 있다는 사실 때문에 단순 BFS에서 조금의 변형이 필요합니다. BFS는 이동할 수 있는 노드를 탐색하면서 중복된 탐색을 방지하기 위해 방문 여부를 표시하는 자료구조를 사용합니다. 한 노드에서 다른 노드로 가는 이동 조건이 모두 동일하다면 하나의 자료구조에 방문 여부를 표시하면 충분합니다. 하지만 이동 조건이 달라진다면 하나의 자료구조에서만 방문 여부를 표시하는 것을 문제를 해결할 수 있음을 보장하지 못합니다. 이동조건이 다르기 때문에 같은 노드를 뒤늦게 방문하여도 최단거리의 경로가 될 수도 있습니다. 따라서 하나의 자료구조에 대한 중복 조건 체크는 의미가 없으며 이동 조건의 수에 따라 방문 여부를 ..

숨바꼭질은 너비우선탐색을 활용하여 해결할 수 있는 문제입니다. 수빈이가 이동할 수 있는 3가지 방법을 탐색 방법으로 생각하여 동생의 위치까지의 최단 거리를 계산하는 문제로 바꾸어 생각할 수 있습니다. 따라서 너비우선탐색이 사용될 수 있습니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) int N, K; struct que { int x, time; }; struct que queue[100000+20]; int wp, rp; int visit[100000+20]; int main(void) { scanf("%d %d", &N, &K); visit[N] = 1; queue[wp].x = N; queue[wp++].time = 0; while (..