목록PS/알고리즘 문제풀이 (157)
득이공간
[백준 C++] 1629 곱셈 - 분할정복
1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net #include using namespace std; int A, C; long long BinaryFunction(int B) { if (B == 0) { return 1; } else if (B == 1) { return A % C; } if (B % 2 == 0) { return BinaryFunction(B / 2) * BinaryFunction(B / 2) % C; } else { return BinaryFunction(B / 2) * BinaryFunction(B / 2 + 1) % C; } } int main() ..
[백준 C++] 1149 RGB거리 - 다이나믹프로그래밍
1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #include using namespace std; int Weight[1001][3]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int R, G, B; cin >> R >> G >> B; Weight[1][0] = R; Weight[1][1] = G; Weight[1][2] = B; for (int i = 2; i > ..
[백준 C++] 16953 A → B - 너비우선탐색
16953번: A → B 첫째 줄에 A, B (1 ≤ A End) { con..
[백준 C++] 11725 트리의 부모 찾기 - 너비우선탐색
11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include #include using namespace std; int N; int Parent[100001]; bool Visited[100001]; list Neighbors[100001]; queue SearchQueue; void BFS(int Root) { SearchQueue.emplace(Root); while (!SearchQueue.empty()) { int Current = SearchQueue.front(); SearchQueue.pop(); if (Visited[Current]) { ..
[백준 C++] 11053 가장 긴 증가하는 부분 수열 - 다이나믹프로그래밍
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #include using namespace std; int Sequence[1000]; int Length[1000]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int MaxLength = 0; int N; cin >> N; for (int i = 0; i > Seq..
[백준 C++] 15654 N과 M (5) - 백트래킹
15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net #include #include #include #include using namespace std; int N, M; vector Numbers; void DFS(int Sequence[], int Index, bool Visited[]) { if (Index == M) { for (int i = 0; i M; Numbers.reserve(N); for (int i = 0; i < N; ++i) { int Number;..
[백준 C++] 15650 N과 M (2) - 백트래킹
15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include using namespace std; int N, M; void DFS(int Sequence[], int Index, int Number) { if (Index == M) { for (int i = 0; i < M; ++i) { cout M; int Sequence[8]; DFS(Sequence, 0, 1); } DFS & 백트래킹을 이용해서 푸는 문제입니다. 1부터 N까지 각 숫자를 고를 때와 안 고를 때를 DFS로 탐색하도록 하고, 현재 숫..
[백준 C++] 16928 뱀과 사다리 게임 - 너비 우선 탐색
16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net #include #include using namespace std; int Depth[101]; bool Visited[101]; int Event[101]; queue SearchQueue; int BFS(int Start, int End) { SearchQueue.emplace(Start); Depth[Start] = 0; while (!SearchQueue.empty()) { int Current = Searc..
[백준 C++] 14500 테트로미노 - 브루트포스
14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net #include using namespace std; int N, M; int Paper[500][500]; const int Tetromino[19][3][2] = { { { 1, 0 }, { 2, 0 }, { 3, 0 } },// 1-1 { { 0, 1 }, { 0, 2 }, { 0, 3 } },// 1-2 { { 1, 0 }, { 0, 1 }, { 1, 1 } },// 2 { { 1, 0 }, { 2, 0 }, { 2, -1 } },// 3-1 { { 1, ..
[백준 C++] 10026 적록색약 - 깊이우선탐색
10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net #include using namespace std; int N; char Color[100][100]; bool Visited[100][100]; bool Visited2[100][100]; int DX[4] = { -1, 0, 1, 0 }; int DY[4] = { 0, -1, 0, 1 }; void DFS(int X, int Y) { Visited[Y][X] = true; for (int i = 0; i < 4; ++i) { int NX = X + D..