목록전체 글 (60)

쫑쫑이의 블로그

백준 1916 최소비용 구하기 Java [다익스트라]

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 사용해서 풀면 된다 끝까지 돌 필요 없이 도착 도시에 최초로 방문할 때 break해준다 import java.io.*; import java.util.*; public class Main { static final int INF = 200_000_000; public static void main(String[] args) throws IOE..
알고리즘/백준 2022. 10. 20. 01:43
백준 11660 구간 합 구하기 5 Java [DP, 누적합]

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net x1 부터 x2까지 하나씩 다 더해서 구했을 때 (1,1)부터 (1024, 1024)까지 합을 구하는 것을 100000번 반복하면 시간복잡도가... 터진다 - 풀이 - 1 2 3 4 5 6 7 8 9 10 위와 같은 행이 있을 때 각 자리에 1부터 해당 자리까지 합을 구한다 1 3 6 10 15 21 28 36 45 55 4부터 10까지 합을 구하고 싶으..
알고리즘/백준 2022. 10. 19. 00:36
백준 5639 이진 검색 트리 Java [트리 순회]

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 예제를 배열로 만들면 [50, 30, 24, 5, 28, 45, 98, 52, 60]이 된다 50이 루트 노드이고 왼쪽 자식 노드는 30, 오른쪽 자식 노드는 98이다 30부터 98의 전인 45까지가 왼쪽 자손이고, 98부터 오른쪽 자손이다 이 규칙을 이용해 분할 정복으로 풀이하면 된다 먼저 루트는 50이고 배열을 탐색해서 50보다 큰 숫자를 만나면 해당 인덱스를 기준으로 아래와 같이..
알고리즘/백준 2022. 10. 10. 16:00
백준 11404 플로이드 Java [플로이드 워셜]

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 주의할점 각 노선은 단방향이고, 여러개 존재할 수 있으므로 최소값만 담아준다 i에서 j로 갈 수 없는 경우 0을 출력해줘야한다 100개 도시이고, 비용은 100000보다 작기 때문에 A에서 B로 가는 최대 비용은 99x100000이다 최대값은 최대비용보다 100000 더 큰 100 x 100000으로 설정해줬다 플로이드 워셜 (Floyd-Warshall) 알고리즘을 알면 쉽게 풀 수 있다 플로이드..
알고리즘/백준 2022. 10. 9. 12:18
백준 10830 행렬제곱 Java [분할 정복]

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 A의 B제곱 행렬을 구해야한다 B의 숫자가 1000억이므로 Long타입으로 써야하고, 완전탐색으로 하면 안된다 제곱을 생각해보면 A^5 = A^4 * A^1 성립한다 A^c = A^a * A^b로 일반화할 수 있고 c = a + b이다 B를 100이라고 가정할때 2의 제곱수로 위에 일반화한 식으로 표현하면 64(2^6) + 32(2^5) + 4(2^2) B를 2로 나눠서 몫이 1일때만 A의 제곱수를 곱하면..
알고리즘/백준 2022. 10. 9. 00:30
백준 1967 트리의 지름 Java [트리, DFS]

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이전에 푼 문제와 같은데 설명이 더 상세히 추가됐다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int[] vtd; static int V; static HashMap nod..
알고리즘/백준 2022. 10. 7. 16:35
이전 Prev 1 ··· 5 6 7 8 9 10 Next 다음