BOJ75 [BOJ]1504번: 특정한 최단 경로 문제: https://www.acmicpc.net/problem/1504 반드시 경유해야 할 노드가 2개라면 그 두 노드를 반드시 지나는 다익스트라를 돌리면 노드 두 개를 경유한 상태로 최단경로가 만들어집니다. 경로 후보1: 1번노드 → N1노드 → N2노드 →N번노드 경로 후보2: 1번노드 → N2노드 → N1노드 →N번노드 위 두 개의 후보 중에 정답이 존재합니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1504.java 2020. 5. 26. [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]16922번: 로마 숫자 만들기 문제: https://www.acmicpc.net/problem/16922 BFS 문제입니다. 매 깊이 마다 1,5,10,50을 더해봐서 X개의 숫자의 합으로 Y를 만든 적이 있는지 계속 저장하면서 N개를 모두 합쳤을 때의 값을 set에 저장해주었습니다. 상태를 탐색하는 방법은 DFS도 가능하겠지만 아마 재구 깊이를 20까지 탐색 하면 터지지 않을까 싶네요. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16922.cc 2020. 5. 20. 이전 1 ··· 13 14 15 16 17 18 19 다음
