본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준2537 - 빙산 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net bfs와 dfs를 활용하여 문제를 풀었습니다. 먼저 각각 빙산의 높이를 인접한 바다의 수만큼 감소시키고(bfs), 빙산을 2덩어리 이상으로 분리할 수 있는지 체크합니다. 여기서 분리할 수 있으면 그때의 시간을 출력하고, que에서 빙산이 없으면 0을 출력하게 합니다. 처음 배열의 크기를 10000 x 10000을 했더니 메모리 초과가 나와서 문제에서 사용한 모든 배열을 동적할당을 하였습니다. #includ.. 2020. 10. 22.
[알고리즘 문제] 백준2644 - 촌수계산 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net bfs로 문제를 해결할 수 있으며 시작점을 기준으로 그래프에서 연결되어 있는 노드를 이동하면서 노드의 위치가 도착지점이면 그때의 dis값을 출력하도록 합니다. 그래프에서 이동한 노드는 다시 방문하면 안되기 때문에 이 부분은 check[]로 관리하였습니다. #include #include using namespace std; int main() { int n, start, des, m; cin >.. 2020. 10. 16.
[알고리즘 문제] 백준1916 - 최소비용 www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 사용하여 해결하였습니다. 핵심은 우선순위 큐에 넣을 때 음수화, 뺄때 음수화를 해주는 것인데 이는 같은 도시로 비용이 적은 순으로 정렬하기 위함입니다. 예를 들어 [1,2],[1,3]을 그냥 넣게 되면 [1,3]이 [1,2]보다 높은 우선순위를 가지는데 [1,-2],[1,-3]의 경우 [1,-2]이 [1,-3]보다 높은 우선순위를 가지고 -에 다시 -를 붙.. 2020. 10. 16.
[알고리즘 문제] 백준1520 - 내리막 길 www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 처음에 dfs를 생각했다. 근데 출력결과를 보면 최대10억까지 나올 수 있다고 되어있다. 그렇다면 탐색해야 하는 경우의 수는 10억보다 더 많을 것이고...무조건 시간초과가 나온다. 또 각 위치에서 4방향을 움직일 수 있고 가로/세로의 크기가 최대 500이기 때문에 시간 복잡도는 4^250000이 된다. 아무튼 일반적인 dfs로 풀면 안된다. 다음 생각해본 방법은 dp로 푸는 방법이다. 현재 dp[y][x]에.. 2020. 10. 15.

티스토리툴바