전체 글1321 [백준] 10844 쉬운 계단 수 - Dynamic Programming / Java • 문제 링크 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 정의하였으며, 이는 dp[자릿수][자릿값] 을 의미한다. 이때 오버플로우를 방지하기 위하여 long 형으로 정의한다. 이때 각 자릿값의 계단수를 구하는 코드는 dp[i - 1][j - 1] + dp[i - 1][j + 1] 이며, 예시로 dp[3][4] 이 주어질 때, 위의 코드를 적용하면 dp[2][3], dp[2][5] 가 구해지게 된다. dp[3][4] - - 4 dp[2][3] - 3 4 dp[2][5] - 5 4 다만 자릿값이 0 일 경우 다음 자릿수의 값은 1 만 가능하고, 자릿값이 9 일 경우 다음 자릿수의 값.. 2022. 8. 23. [백준] 1389 케빈 베이컨의 6단계 법칙 - Graph Theory / Java • 문제 링크 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net • 풀이 과정 [백준] 11404 플로이드 - Graph Theory / Java • 문제 링크 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 graycode.tistory.com 위 문제와 유사한 구조의 Floyd-Warshall 알고리즘 문제이다. 모든 노드간.. 2022. 8. 22. [백준] 11404 플로이드 - Graph Theory / Java • 문제 링크 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net • 풀이 과정 모든 노드간 최단 경로를 구하는 Floyd-Warshall 알고리즘을 활용한다. 2차원 배열에 자기 자신 노드로 이동하는 경우을 제외한 모든 최단 거리를 inf 값으로 지정하고, 이때 inf 값을 Integer.MAX_VALUE 로 지정 시 오버플로우가 발생할 수 있으므로 정점과 간선의 최대값의 곱에 1을 더한 수로 지정하였다. 이 후 간선의 정보를 입력받는데 같은 간선이 추가로 주어질 시 가중치의 최소값을 매번 갱신하여, dist 배.. 2022. 8. 21. [백준] 1753 최단경로 - Graph Theory / Java • 문제 링크 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net • 풀이 과정 [백준] 1916 최소비용 구하기 - Graph Theory / Java • 문제 링크 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스 graycode.tistory.com 위 문제와 유사한 구조의 Dijkstra 알고리즘 문제이다... 2022. 8. 20. [백준] 1916 최소비용 구하기 - Graph Theory / Java • 문제 링크 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net • 풀이 과정 한 노드에서 다른 모든 노드까지의 최단 거리를 구하고, 음의 가중치가 없는 그래프이므로 Dijkstra 알고리즘을 활용한다. 모든 노드까지의 최단 거리를 저장할 dist 배열을 최대값으로 초기화하고, 각각의 간선의 시작점이 인접 리스트의 인덱스로써, 도착점과 가중치를 저장한다. 입력받은 시작점 source를 dijskstra 함수의 매개 변수로 전달하여 실행하고, 우선 순위 큐를 람다식을 통해 가중치.. 2022. 8. 19. [백준] 1865 웜홀 - Graph Theory / Java • 문제 링크 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net • 풀이 과정 [백준] 11657 타임머신 - Graph Theory / Java • 문제 링크 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000.. graycode.tistory.com 위의 문제와 유사한 벨만 포드 알고리즘 문제이다. 다만 이 문.. 2022. 8. 18. 이전 1 ··· 197 198 199 200 201 202 203 ··· 221 다음
