본문 바로가기

Programming456

[C/C++] 백준 #2188 축사 배정(이분 매핑) #2188 문제는 이분 매핑의 대표적인 문제입니다. 이분 매핑(binary mapping)이라는 것은 최대 유량 알고리즘(maximum flow algorithm)의 특별한 버전입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 문제에서 축사를 소에 배정을 해주는데, 소들은 자신들이 원하는 축사들 중 하나를 배정받지 않으면 다른 축사에 들어가지 않으려 합니다. 이럴 경우 가능한 많은 소를 원하는 축사에 배정하는 알고리즘입니.. 2023. 4. 13.
[C/C++] 백준 #2178 미로 탐색(너비 우선 탐색) 미로 탐색은 대표적인 그래프 탐색과 관련되어 풀 수 있는 문제입니다. 길이 여러개이고, 움직일 때 비용이 똑같다고 한다면, 다익스트라와 같이 우선순위큐를 사용하는 알고리즘을 이용하지 않고, 너비 우선 탐색을 이용해도 됩니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 미로 탐색은 최단 경로를 찾아야 한다는 표현이 있지만, 고전적인 미로 탐색 문제입니다. 너비우선탐색 알고리즘을 이용하였습니다. 출발점에서부터 너비우선탐색을 하다가 도착지점에 도착하면.. 2023. 4. 13.
[C/C++] 백준 #2169 로봇 조종하기(동적 계획법) #2169 문제는 동적 계획법을 이용했지만, 일반적인 동적 계획법은 한방향으로만 진행되는 경우에 주로 사용됩니다. 이 문제에서는 한곳의 값을 결정하기 위해서는 왼쪽, 오른쪽, 그리고 위라는 3군데 방향을 고려해야 하므로 좀 까다롭습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 문제는 나사(NASA)의 로봇이 화성을 돌아다닐때, 최대한의 가치를 얻으면서 지역을 탐사하는 것입니다. 처음에 어떻게 짜야할까 고민하.. 2023. 4. 12.
[C/C++] 백준 #2168 타일 위의 대각선(정수론) 이번 문제는 정수론(number theory)을 알면 쉽게 해결할 수 있습니다. 정수론에서 가장 기본이 되는 것 중에 하나가 최대 공약수(GCD; Greatest Common Divisor)입니다. 최대 공약수를 구해서 문제를 해결할 수 있습니다. 문제의 링크는 다음과 갈습니다. https://www.acmicpc.net/problem/2168 2168번: 타일 위의 대각선 첫째 줄에 가로의 길이 xcm와 세로의 길이 ycm가 주어진다. x와 y는 1,000,000,000 이하의 자연수이다. x와 y사이에는 빈칸이 하나 이상 있다. www.acmicpc.net 대각선이 그려진 타일의 개수를 구하는데, 어떻게 하면 될까요? 일단 아래의 그림을 가지고 이야기를 해보죠. 가로가 16, 세로가 5개인 타일들입니.. 2023. 4. 12.
[C/C++] 백준 #2167 2차원 배열의 합(포함배제 원리) #2167 문제는 2차원 배열 공간에서 사각형으로 지정한 공간에 있는 숫자합을 계산해야 합니다. 지정된 공간의 합을 한번 계산하는 것이라면, 이중 반복문을 이용해서 풀면 되겠지만, 여기는 K개의 질의(query)가 있기때문에 단순하게 처리하면 \(O(KNM)\)이라는 시간 복잡도를 가지게 됩니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 이 문제는 (0, 0)을 시작점으로 해서.. 2023. 4. 12.
[C/C++] 백준 #2166 다각형의 면적(벡터) 이번 문제는 기하와 벡터에 대해서 알고 있으면 쉽게 풀 수 있는 문제입니다. 컴퓨터 그래픽 관련해서 자주 쓰이는 기법입니다. 중고등학교 때, 외적(cross product, outer product, vector product)을 배우고 있지만, 실제로 이런데에 쓰일 수 있다는 점들은 잘 모릅니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 세점 \(O(0, 0)\), \(A(x_A, y_A)\), \(B(x_B, y_B)\)가 있다.. 2023. 4. 12.
728x90

티스토리툴바