알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 완전탐색을 이용한 그래프 문제입니다. 5*5 숫자판에서 무작위 위치에서 5번까지 이동해 수열을 구하는 문제입니다. 1을 5번 이동했다면 11111이 수열이 됩니다. 만들 수 있는 수열이 숫자판에 따라 11111 ~ 99999까지 있을 수 있습니다. 따라서 이전에 만들었던 수열을 찾는 배열 칸은 100000 이상으로만 잡아주면 됩니다. 아..

문제 링크입니다. https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 그래프탐색을 이용해 푸는 문제입니다. 저는 BFS를 이용해 풀었습니다. 자신의 친구와 친구의 친구를 결혼식에 초대하려고 할 때, 부를 수 있는 사람 수를 구하는 문제입니다. 친구의 친구까지 부를 수 있으니, 2번까지 이동할 수 있습니다. 1번 정점에서 시작해 2번까지 이동해서 자신과 연결된 정점 갯수를 찾아주면 됩니다. 자세한 것은 코드를 참고해주세요 #includ..

문제 링크입니다. https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 그래프 탐색을 이용하는 문제입니다. 노드를 하나 지웠을 때, 리프 노드를 구하는 문제입니다. 시작 노드를 찾은 뒤, 시작 노드에서 그래프 탐색을 시작해줍니다. 탐색 노드와 연결된 노드 중, 연결되지 않는 노드로 이동해 다음 노드로 계속 이동해줍니다. 더 이상 이동할 수 없는 노드로 도착하면, 리프 노드 갯수를 1 증가해줍니다. 여기서, 지워진 노드가 연결되어 있어도 이동할 ..

문제 링크입니다. https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 분리 집합과 그래프 탐색을 이용해 푸는 문제였습니다. 연결된 정점들을 줬을 때, 주어진 길로 여행을 할 수 있는지 확인하는 문제입니다. 예제 입력을 봤을 때, 1 -> 2 2 -> 1, 3 3 - > 2 와 같이 연결되어 있습니다. 또한, 출발지와 목적지를 여러개로 나눠서 생각해보면, 1 -> 2와 2 -> 3을 확인할 수 있습니다. 따라서, (1, 2) + (2, 3)으로 나눠..

문제 링크입니다. https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이분탐색을 활용해야하는 문제였습니다. 두 개의 섬이 주어졌을 때, 옮길 수 있는 중량의 최댓값을 구하는 문제입니다. 저는 이분탐색의 방법으로 풀었는데, low = 0, high = 다리의 최대 중량로 만들어, mid값을 얻은 뒤, mid값보다 큰 값으로만 두 섬을 이동할 수 있냐? -> 해당 과정을 확인했습니다. mid ..

문제 링크입니다. https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net Dp로 풀 수 있지만, BFS로 푸는게 더 간단해 보여 약간의 노다가를 추가한 BFS로 풀었습니다. 3개의 SCV가 각각 9 or 3 or 1의 값이 빼집니다. 따라서 모든 경우를 확인한 뒤, 전부 0이 된 최소 횟수를 출력해주면 됐습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 그래프 탐색을 이용해 푸는 문제였습니다. 시작점을 큐에 넣고 탐색을 시작하지 않는 것이 중요했습니다. 시작점이 아닌 시작점과 연결된 점들을 큐에 넣은 뒤 탐색을 시작해, 최단 거리를 구해주면 됐습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #in..

문제 링크입니다. https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 그래프 탐색을 통해 푸는 문제입니다. 두 동전을 상하좌우 4방향으로 움직여 한 동전만 떨어뜨리는 문제입니다. 두 동전이 모두 떨어지는 상황만 나오거나, 10번보다 많이 움직이면 -1를 출력해주면 됩니다. 먼저 두 동전의 위치에서 시작합니다. 두 동전은 4방향 전부 움직일 수 있으니, 상하좌우를 모두 탐색해줘야합니다. 탐색을 할 때는 이동한 좌표를 통해 판별을 하는데, 1. 두 ..

문제 링크입니다. https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net BFS를 이용한 문제입니다. 친구 사이가 얼마나 떨어져있나에 따라 점수가 달라집니다. 모든 사람과 친구 사이이면 1점, 친구의 친구 사이가 있다면 2점, 친구의 친구의 친구 사이가 있다면 3점이 됩니다. 즉, BFS 탐색을 할 때, 탐색의 깊이만큼 사람의 점수가 된다는 의미입니다. 1번 사람부터 N번 사람까지 각각 탐색을 해줘야합니다. 그러면, 1~N번 사람까지 자신의 점수가 구..

문제 링크입니다. https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 y; connect[x].push_back(y); connect[y].push_back(x); } solve(); return 0; } 질문 및 조언은 댓글을 남겨주세요

문제 링크입니다. https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 백트래킹과 BFS를 이용한 문제였습니다. N개의 정점이 주어질 때, 이들을 적절하게 나눠 인구수 차이를 가장 적게 만드는 문제였습니다. 해당 문제를 풀려면 구햔해야 하는 것들이 있습니다. 1. 선거구를 나누는 방법 2. 나뉜 선거구가 연결되는 지 확인 3. 선거구의 인구차를 확인 이와 같이 3개를 구현하면 풀 수 있었습니다. 먼저 1번부터 확인해보겠습니다. 1. 선거구를 나누는 방법 인구수를 최소로 ..

문제 링크입니다. https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net BFS를 이용해 푸는 문제입니다. 일반적인 상하좌우 4방향 탐색이 아닌, 나이트 이동인 8방향으로 탐색하는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF ..