알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net Dp와 다익스트라 알고리즘을 합펴서 푸는 문제였습니다. 이동 비용이 M이하이면서, 최소시간을 구하는 문제입니다. 1에서 N까지 이동할 때, 최소 거리를 구하는 방법은 간단합니다. 하지만, N까지 이동할 수 있는 비용은 다를 수 있습니다. 따라서 2차원 배열을 이동해, X번 노드를 Y비용에 도착했을 경우로 만들어줘야 합니다. 저는 Distanc..

문제 링크입니다. https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 탐색 횟수가 많은 다익스트라 문제였습니다. 시작점에서 마지막점까지 갈 수 있는지를 확인하는 문제였습니다. X번 정점을 갈 수 있는지 여부를 확인한 뒤, 이에 따라 최소 거리를 구해야합니다. N M; for(int i = 1; i > View[i]; } View[N] = 0; for(int i = 1; i > x >> y >> cost; if(View[x..

문제 링크입니다. https://www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 특이한 8방향 그래프 이동을 통해 원하는 목적지에 도달할 수 있는지를 구하는 문제입니다. 상이 왕을 잡을 수 있는 횟수가 얼마인지를 구하는 문제입니다. 상이 이동할 수 있는 8방향을 통해 계속 이동하면서 왕이 있는 곳까지 움직이면 되는 문제입니다. 주의할 점은 상이 이동하는 길에 다른 말이 있을 경우 해당 방향으로 움직일 수 없다는 것입니다. 해당 조건만 주의하면 쉽게 풀 수 있는 문제입..

문제 링크입니다. https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net BFS의 순서를 확인할 수 있는지를 물어보는 문제였습니다. 1번부터 BFS 탐색을 시작했을 때, 주어진 순서가 올바른 BFS 방문 순서인지를 확인하는 문제입니다. 부모가 같은 노드가 다수일 경우, 방문 순서가 여러개가 나올 수 있습니다. 문제 예시에서는 (1, 2, 3, 4) or (1, 3, 2, 4)가 나올 수 있습니다. 여러개가 나올 수 있는 방문 순서 중 하나가 입력에 주어졌는지를 찾아야합니다. 나올 수 있는 모든 경우를 확인하는 방법보다는 문제에서 나온 경우만을 맞는지 확인하는 것이 효..

문제 링크입니다. https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net BFS와 구현, 브루트포스가 합쳐진 문제였습니다. 문제 자체는 간단하지만 구현 능력이 있어야했던 문제입니다. 5개 층의 Map이 주어지고, 이를 통해 미로를 구성한 뒤 탈출할 수 있는지를 확인하는 문제입니다. 이 문제를 풀기 위해서 구현해야할 것이 있습니다. 1. 5개 층을 선택하기 2. 층을 반시계 혹은 시계 방향으로 돌리기 3. 구성된 미로를 탐색하기 먼..

문제 링크입니다. https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 이전과 이후를 비교하는 문제였습니다. 백신을 맞기 전과 후의 MAP을 주고 백신을 맞은 확률이 있는지를 알아보는 문제였습니다. 백신을 한번만 맞을 수 있다는 것이 중요했습니다. 이전과 이후의 MAP을 비교해서 다른 곳이 하나 있다면 해당 점에서 4방향 탐색을 시작합니다. 탐색을 완료한 뒤에 두개의 MAP을 비교해서 다른 경우 NO, 같은..

문제 링크입니다. https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 4방향 탐색으로 친구를 찾아주는 문제였습니다. 'I'에서 시작해서 4방향 탐색으로 'P'를 찾는 문제였습니다. 'X'를 제외한 모든 곳을 탐색할 수 있음으로 이를 유의하여 문제를 풀면 됩니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #i..

문제 링크입니다. https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 8방향 탐색을 하는 간단한 BFS 문제였습니다. 0과 1로 이루어진 map에서 1로만 이루어진 영역을 찾는 문제였습니다. 다른 문제와는 다르게 대각선까지 포함한 8방향 탐색을 해야됨을 유의했다면 쉽게 풀 수 있던 문제입니다. 먼저 map을 전부 확인해본후, 1이 있는 곳을 확인합니다. 이때, 이전에 방문했던 곳은 아니여야 합니다. 조건을 만족했다면 해당 점부터 8방향 탐색을 시작해 글자가 어디까지 이어져있는지를 확인합니다. 자세한 것은 코드를 참고해주세요 #define _CRT_S..