목록PS (176)
득이공간
16953번: A → B 첫째 줄에 A, B (1 ≤ A End) { con..
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]) { ..
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..
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;..
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로 탐색하도록 하고, 현재 숫..
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..
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, ..
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..
9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net #include #include #include using namespace std; string Command[10000]; bool Visited[10000]; queue SearchQueue; void InitContainers() { for (int i = 0; i < 10000; ++i) { Command[i] = ""; Visited[i] = false; } while (!SearchQueue.empty()) { SearchQueue.po..
7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net #include #include #include using namespace std; unordered_map CheckNum; priority_queue MaxHeap; priority_queue MinHeap; void Input(int Number) { ++CheckNum[Number]; MaxHeap.emplace(Number); MinHeap.emplace(Number); } void DeleteMax() { if (!MaxHeap.empty()) ..