기록보관소

평균 점수 문제는 평균을 구하는 문제입니다. 작성한 코드는 다음과 같습니다. #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..

벽 부수고 이동하기는 변형된 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 (..

7569번 토마토는 전에 풀었던 토마토 문제를 확장한 문제입니다. 토마토를 보관하는 상자를 위로 쌓을 수 있도록 하였기 때문에 너비우선탐색을 할 때 상하좌우 뿐만 아니라 위, 아래 방향으로도 탐색을 해야 합니다. 탐색의 방향이 추가된 것을 제외하면 기존 토마토 문제와는 모든 부분이 똑같습니다. 이전에 풀었던 토마토 문제는 다음 글에서 확인할 수 있습니다. 2021.09.12 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 7576번] 토마토 [알고리즘/문제풀이][BOJ 7576번] 토마토 토마토 문제는 BFS를 이용하는 문제입니다. BFS의 flood fill 기법을 사용하는 문제로 여러 개의 루트 노드에서 BFS를 수행한다는 점에서 다른 BFS 문제와의 차이를 확인할 수 있습니다. 문제를 해결..