알고리즘 모음(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/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 문자열을 사용한 구현 문제였습니다. 문자가 연속되는지만 찾으면 되는 문제입니다. 같은 알파벳이 떨어져서 나오면 안되며, 항상 붙어져 나와야지 그룹 단어가 됩니다. 따라서 알파벳을 3가지로 나눠야하는데, 1. 처음 나온 알파벳인 경우 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/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net BFS를 이용해 푸는 문제입니다. BFS를 짜는 것 자체는 간단했습니다. 돌이 A, B, C가 존재하니 옮길 수 있는 경우는 3가지입니다. 1. A 와 B 2. A 와 C 3. B 와 C 각 경우에서도 X가 큰 경우, Y가 큰 경우가 있으니 총 6가지 경우만 확인하면 됐습니다. 방문했던 돌의 크기를 확인하는 방법은 3차원 배열을 이용해 [A][B][C]로 저장하면 편하겠지만..

문제 링크입니다. 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/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net BFS 혹은 DFS를 통해 푸는 문제였습니다. 물통의 물을 옮겨 C물통의 경우를 구하는 문제입니다. 물통을 옮기는 경우를 생각하면 문제 풀기가 쉬워집니다. 1. A에서 B 2. A에서 C 3. B에서 A 4. B에서 C 5. C에서 A 6. C에서 B 이렇게 6가지입니다. 하지만 경우마다 2가지로 나눠서 생각해야합니다. 1. X물통을 Y에 옮겨도 Y물통이 전부..

문제 링크입니다. 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번 사람까지 자신의 점수가 구..