알고리즘 모음(C++)

문제 링크입니다 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%가 됩니다. ..

문제 링크입니다 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net DFS에 익숙하지는 않아 https://yabmoons.tistory.com/117 님의 접근 방식을 참고했습니다. DFS, BFS를 모두 사용한 문제입니다 1번 기능을 구현하는 함수, 3번과 4번을 구현하는 함수와 2번 기능을 구현하는 함수로 나누어서 풀었습니다. 접근방법 1. DFS를 통해 7명의 학생을 뽑습니다. (1,2,3,4,5,6,7)이나 (7,6,5,4,3,2,1)은 똑같..

문제 링크입니다 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net K의 값이 주어졌을때, B[K]의 값을 구하는 문제입니다. N의 값이 최대 10^5이라서 이분 탐색을 하지 않는다면 시간 초과가 나는 문제였습니다. 푸는 방법이 도저히 떠오르지 않아 꾸준함님의 포스팅을 참고했습니다. https://jaimemin.tistory.com/988 백준 1300번 K번째 수 문제 링크입니다: https://www.acmicp..

문제 링크입니다 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 깊이 우선 탐색(BFS) 문제였습니다. 문제 조건입니다. 한번 지나간 알파벳은 지나가지 않고 최대로 갈 수 있는 횟수를 구하는 문제입니다. 예를 들어 CAAB ADCB 의 경우에는 C -> A -> D 총 3번이 됩니다. 접근 방법 1. 26칸을 가진 배열을 선언해 이동중에 어떤 알파벳이 입력되었는지 저장한다. 2. 상, 하, 좌, 우를 확인하여 갈 수 있는 경로를 확인한다..

문제 링크입니다 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 길이 주어졌을때 다음과 같은 방식으로 경사로가 만들어집니다. 그림에서 위 경우에는 높이 차가 1이며, 경사로를 놓을 수 있는 구간 길이가 2이상이기에 경사로를 설치할 수 있습니다. 아래 경우에서는 1번 그림에서는 높이 차가 2이기 때문에 2번 그림에서는 경사로가 바닥에 닿아있지 않기 때문에 3번 그림에서는 경사로가 곂쳐서 놓였기 때문에 4번 그림에서는 기울여졌기 때문에 경사로를 놓지 못합니다. 왼쪽 그림..

문제 링크입니다 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 삼성 SW 역량테스트 문제입니다. BFS를 이용해 풀었습니다. N*N의 입력이 주어졌을 때, 위의 조건을 따라서 인구 이동이 시작합니다. 왼쪽 그림은 인구 이동 전, 오른쪽 그림은 인구 이동 후의 모습입니다. 모든 나라가 국경선을 공유하기에 전부 인구가 달라진 모습을 볼 수 있습니다. 접근 방법 1. 이중 for문을 통해서 check배열의 값이 0일때 해당 칸부터 B..

문제 링크입니다 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 삼성 SW 역량 테스트 문제입니다. BFS를 이용하여 풀었습니다. 1. 현재 택시의 좌표에서 가장 가까운 손님에게 찾아간 뒤, 목적지까지 간다. 2. 목적지에서 가장 가까운 손님을 찾아간 뒤, 손님의 목적지까지 간다. 2 - 1. 가장 가까운 손님이 많을 경우, 행이 작은순으로 행이 같은 손님이 있을 경우 열이 작은 순으로 정렬한다. 3. 1..