분류 전체보기1502 [백준] 2193 이친수 - Dynamic Programming / Java • 문제 링크 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net • 풀이 과정 [백준] 10844 쉬운 계단 수 - Dynamic Programming / Java • 문제 링크 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 정의하였으며, 이는 dp[자릿수][자릿값] 을 의미한 graycode.tistory.com 위 문제와 유사하게 2차원 dp 배열로 접근하여 풀이한다. 이친수.. 2022. 8. 24. [백준] 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. 이전 1 ··· 227 228 229 230 231 232 233 ··· 251 다음
