알고리즘 모음(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/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/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net bfs를 이용한 간단한 문제입니다. 쩰리가 -1에 도착할 수 있는지 구하는 문제입니다. 쩰리는 아래와 오른쪽으로만 이동할 수 있습니다. 이동할 때 한칸만 이동하는 것이 아닌, map에 있는 값만큼 움직여야 합니다, 따라서 움직이고 난 뒤, map의 범위를 초과하는지 확인하는 것은 필수입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #..

문제 링크입니다. https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS를 이용해 푸는 문제입니다. 사이클이 이루어져 있을 때, 이를 어떻게 찾는지 물어보는 문제입니다. 문제를 해석했을 때, 가장 쉬운 접근은 "X번부터 사이클이 존재한다면, 도착점도 X번이니 DFS를 통해서 X가 X에 도착할 수 있는지를 확인하면 된다." 입니다. 하지만, N의 값이 100,000 이하이기에 모든 점들을 DFS탐색 하기에는 시간이 부족합니다. 따라서 사이클을 확인하는..

문제 링크입니다. https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 다익스트라를 사용한 문제입니다. 문제를 풀기위해 새로운 접근이 필요했습니다. 상근이가 두 죄수를 탈옥하기 위해 열어야하는 최수 문 갯수를 구하는 문제입니다. 실수할 수 있는 부분이 있어, 많이 틀렸던 문제입니다. 문제에서 문을 열 수 있는 사람은 상근이와 두 죄수입니다. 그렇다면 생각할 수 있는 경우는 3가지입니다. 1. 상근이만 문을 열어 죄수들을 데려갈 경우 2. 죄수1이 죄수2를 데리고..