알고리즘 검색 결과

해당 글 114건

[BaekJoon] 백준 1916 최소비용 구하기

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 최단경로랑 같은 문제. input 순서, 출력만 바꾸면 정답 import java.io.*; import java.util.*; public class Main { static class Vertex implements Comparable{ int vertex; int distance; public Vertex(int v, int d) { this.vertex =..
알고리즘/백준 2020. 9. 23. 19:25

[BaekJoon] 백준 1753번 최단경로

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라의 개념을 물어보는 문제입니다. 다만 인접행렬이 아닌 인접리스트, 단순반복이 아닌 우선순위큐를 사용하여 풀어야 시간초과, 메모리 부족이 일어나지 않습니다. import java.io.*; import java.util.*; public class Main { static class Vertex implements Comparable{ int vertex; int..
알고리즘/백준 2020. 9. 23. 19:20

세그먼트 트리 (백준 2042번 구간합 구하기)

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 세그먼트 트리, 구간 합을 구할 때 이진트리를 사용해 빠른 답을 구할 수 있는 자료구조 단순히 합을 구할때도 마찬가지 지만 중간에 값이 갱신되거나 구간이 바뀔 때 선형 자료구조보다 빠르게 해답을 구할 수 있다. 단순 배열을 사용한 합에서는 덧셈에서만 O(n) 시간이 걸리고 구간이 바뀌면 바뀐만큼 *N 시간이 걸리게 된다. 세그먼트 트리..
알고리즘/백준 2020. 9. 21. 19:10

[BaekJoon] 백준 2839번 설탕배달(자바)

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그�� www.acmicpc.net 기본 조건을 잘못줘서 99%에서 자꾸 틀리길래 애먹었다. 5랑 같거나 클 때라고 해야하는데 > 으로 해버려서 어디서 오류나는건지 한참찾았다 . 일단 DP를 사용해서 풀었다. for문이 더 빠를거같은데 생각하기 귀찮아서 처음 생각한게 재귀니까 재귀로 풀었다. 내가 세운 점화식은 d[n] = Min(d[n-5], d[n-3]) + 1 이다. 여기서 설탕이 나눠지지 않을 때와 5로 나누어 떨어졌을 때 무조건 ..
알고리즘/백준 2020. 9. 15. 19:29

[BaekJoon] 백준 2748번 피보나치 수

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된�� www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); long fib[] = new long[n+1]; fib[0] = 0; fib[1] = 1..
알고리즘/백준 2020. 9. 15. 19:18

[BaekJoon] 백준 1010번 다리놓기

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다리 놓기 문제 다리는 중복될 수 없고 최대한 놓을 수 있는 경우의 수를 구하는 문제입니다. M개의 다리중에서 중복을 제외한 N개의 다리를 선택하는 조합 문제입니다. 조합 특성을 사용해 재귀함수로 풀었습니다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new ..
알고리즘/백준 2020. 9. 14. 19:31

[BaekJoon] 백준 2775. 부녀회장이 될테야

a, b가 주어지면 a층 b호에 사는 주민의 수를 구하는 문제 설명 생략 점화식을 세워서 풀었다. d[a][b] = d[a-1][b] + d[a][b-1] a층 b호에사는 주민의 숫자는 이전의 호수 즉 a층 b-1호에 사는 주민의 수와 a-b층 b호에 사는 주민의 수를 합한 것과 같습니다. (단, 1호일 경우 a-1층의 1호에 사는 주민의 수와 같다) 재귀를 사용하여 문제를 풀었습니다. import java.util.Scanner; public class main { static int[][] d; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int test_case = scan.nextInt(); for(..
알고리즘/백준 2020. 9. 14. 19:30