알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net BFS 문제였습니다. 문제 접근 방법 1. 배추들의 좌표를 입력받은뒤, 배열에 배추의 존재여부를 표시한다. 2. For문을 통해서 배추가 존재하면서, 전에 방문하지 않았던 곳을 찾아 BFS를 실행한다. 3. 필요한 지렁이의 갯수를 출력한다. 4. Test_case 만큼 반복한다. 문제 접근 방법 - 1번 for (int i = 0; i > x >..

문제 링크입니다 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 간단한 bfs,dfs 문제였습니다. 저는 bfs로 풀었습니다. 문제 접근 방법 1. 연결된 컴퓨터들을 입력받은뒤, 각각의 백터에 저장한다. 2. BFS를 1번 컴퓨터 시작한다. 문제 접근 방법 - 1번 for (int i = 0; i > x >> y; com[x].push_back(y); com[y].push_back(x); } 연결..

문제 링크입니다 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net MST 문제였습니다. Union() + Find()를 할 때 기존과 다르게 Union 부분에서 조건을 걸어줘야 했던 문제였습니다. 문제 접근 방법 1. 발전소의 번호를 입력받을때, 배열을 하나 만들어서 해당 지점에 발전소가 있다는 것을 표시한다. 2. 간선들의 정보를 입력받고, 비용에 따라 오름차순으로 정렬한다. 3. 정렬한 간선들의 갯수..

문제 링크입니다 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 2차원 공간에서의 최소 비용 구하기와 다르게 3차원이면서 N의 범위도 100,000 까지이기에 까다로운 문제였습니다. 방법을 생각하는데 꽤 오래걸린 것 같습니다.(괜히 골드1 문제가 아니였습니다) 문제 접근 방법 1. 각 좌표들을 입력받는다.(저는 구조체로 입력받았습니다) 2. 좌표들을 X, Y, Z축에 따라 오름차순으로 정렬한다. 3. 각 축으로 ..

문제 링크입니다 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 쿠르스칼 알고리즘을 사용해서 풀었습니다. 문제 접근 방법 1. 각 학교가 남초 대학인지 여초대학인지 알 수 있는 배열을 선언해 값을 저장합니다. 2. 구조체 백터를 통해서 출발점, 도착점, 비용을 저장한뒤, 비용값에 따라 오름차순으로 정렬합니다. 3. 백터의 처음부터 마지막까지 for문을 돌립니다. 4. for문 안에서 출발점과 도착점이 서..

문제 링크입니다 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 간단한 MST 문제였습니다. 본격적인 쿠르스칼 알고리즘을 실행하기 전에 연결되어 있는 지점들을 연결해주고 시작하는게 포인트였습니다. for (int i = 0; i > x >> y; Union(x, y); } 연결되어 있는 지점을 입력 받은 뒤에 Union함수를 통해서 연결해줬습니다. for (..

문제 링크입니다 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 간단한 MST 문제였습니다. 플로우 관리비용이 10억까지 있어, long long을 써주는 것만 주의하면 되는 문제였습니다. Union + Find 함수를 이용해 Kruskal 알고리즘을 구현했습니다. -> 이것만 할 수 있으면 푸는 문제입니다 자세한 것은 코드를 참고해주세요! #include #include #include #include #include #include #inc..

문제 링크입니다 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 간단한 MST문제였습니다. 문제 접근 방법 1. 백터를 통해서 좌표를 입력 받는다. 2. 1번 좌표에서 갈수 있는 다른 별들의 거리를 저장한다. ex) 1번에서는 2,3,4,5...등 갈수 있습니다. 따라서 구조체 백터에 시작점, 도착점, 거리를 저장한다. 2번의 경우에는 3,4,5,6...등을 갈 수 있습니다. 1번과 똑같이 저장한다. 3. cost의 값에따라 오름차순으로 정렬한다..

문제 링크입니다 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 최소 스패닝 트리 문제였습니다. 각 라운드마다 가중치가 가장 작은 선을 없앤뒤, 남은 간선을 통해서 최소 스패닝 트리를 돌립니다. 그후에 모든 점이 연결 되었는지 확인하고 답을 출력하는 문제입니다. 문제 접근 방법 1. 구조체를 만들어서 출발 지점, 도착 지점, 가중치를 담을 수 있도록 한뒤, 구조체 백터를 구현합니다..

문제 링크입니다 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 최소 스패닝 트리를 이용해 연결할 수 있는 최소 액수를 구한 다음 전체 액수에서 빼면 되는 문제였습니다. 문제 접근 1. M과 N을 입력을 받은후, X,Y,Z를 입력받고, 구조체 백터에다가 넣어준다. (Z 값을 maxi에다가 전부 더해준다) 2. 백터를 COST에 따라서 오름차순으로 정렬한다. 3. check배열의 i번째 칸은 i에서 출발하면 어디를 갈 수 있는지를 의미한다. 따라서 chec..

문제 링크입니다 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.www.acmicpc.netBFS와 DFS를 동시에 사용하는 문제였습니다. 위와 같은 조건으로 다리를 연결해 건널 수 있는 최소 연결 갯수를 구하는 문제입니다. 간단한 문제 접근 방법은 1. 섬의 구역에 번호 붙이고 좌표 저장하기 2. A섬에서 B섬까지 갈 수 있는 다리를 구하기 3. 다리를 연결해주면서 최소수를 구하기 였습니다. 문제 접근 1. 현재 지도의 상태 입력받기 2. 지도에서 각각..

문제 링크입니다. https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net DFS를 사용한 문제입니다! 이동시 확률 계산이 조금 까다로운 문제였습니다. 예를 들어서 2번을 이동하고, 동서남북 이동 확률이 각각 25%라고 하겠습니다. 동->서 / 서->동 / 남->북 / 북->남 의 경우를 제외하면 전부 단순한 이동입니다. 따라서 동 -> 동,남,북 으로 이동하면 되는데 동서남북의 경우가 있으니 전부 계산하면 1/4*1/4*3*4인 75%가 됩니다. ..