Algorithm283 [BOJ]2211번: 네트워크 복구 문제: https://www.acmicpc.net/problem/2211 다익스트라 문제입니다. 주어진 간선중에 1번 컴퓨터에서 모든 컴퓨터를 연결하되 최소비용 조건을 맞추려면 다익스트라의 최종 경로가 된 간선들만 뽑아내면 됩니다. 제가 해결한 방법은 다익스트라에서dist[] 배열을 pair로 선언하여 first에는 길이 값을 담고, 길이가 더 짧을 만나 갱신될 때 마다 second값에 현재 나와 연결된 NODE 값을 저장해놓습니다. 그렇게 하면 최종적으로 dist[] 배열에 저장된 다익스트라의 (dist[i], dist[i].second) 모든 쌍이 정답입니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2211.cc 2020. 5. 21. [BOJ]1261번: 알고스팟 문제: https://www.acmicpc.net/problem/1261 다익스트라 문제입니다. 단순 BFS로 벽을 뚫을 때마다 방문표시를한다면 visit[10000][100][100]으로 메모리 초과가 날 것입니다. 중복해서 방문을 하지 않도록 조건을 걸어보자면, visit[y][x] : (y,x) 칸을 방문했을 때 부순 벽의 갯수 위와 같이 방문배열을 정의하고 now.BROEKN < visit[y][x].BROKEN 조건일 때만 방문할 수 있도록 갱신해주면 최소한으로 벽을 부순 상태로만 계속 탐색을 할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1261.cc 2020. 5. 21. [BOJ]9095번: 1, 2, 3 더하기 문제: https://www.acmicpc.net/problem/9095 기본 DP 문제입니다. N제한이 작으니 단순 재귀로 풀어도 상관없을 듯 합니다. 기저 사례는 아래와 같이 세 가지 입니다. dp[1] = 1 dp[2] = 2 dp[3] = 4 이 때 특정 숫자를 나타낼 수 있는 방법은 임의의 숫자에 1,2,3을 더해주는 방식의 합으로 표현할 수 있습니다. 즉 dp 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ9095.cc 2020. 5. 21. [BOJ]1926번: 그림 문제: https://www.acmicpc.net/problem/1926 BFS 문제입니다. 전체 2차원 배열을 순회하면서 컴포넌트의 갯수와 크기를 구해주면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1926.cc 2020. 5. 21. 이전 1 ··· 56 57 58 59 60 61 62 ··· 71 다음
