알고리즘

[백준] 14719 빗물 (JAVA)

✉️문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 📝 접근 왼쪽에 있는 기둥의 최대값(LM)과 오른쪽에 있는 기둥의 최대값(RM)을 구한다. LM과 RM의 최소값을 구한다. 최소값 - 현재 인덱스의 높이 🗝 문제풀이 public class Q14719_B { static int[] heights; public static void main(String[] args) { Scanner sc = new Scanner(Sys..

[백준] 2504 괄호의 값

✉️문제 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 📝 접근 분배법칙을 이용하면 쉽게 풀 수 있다. 일단 stack과 Tmp 변수를 준비하자. 여기에 분배법칙을 한 값들을 더 해줄 예정이다. 1. ‘(’이면 tmp변수에 2를 곱해준다. 2. ‘[’이면 tmp변수에 3을 곱해준다. 3. ‘)’일 때 a. 만약 stack이 비어있거나, ‘(’가 아니면 잘못된 입력이므로 종료한다. b. 이전 문자가 ‘(’ 이면 answer에 tmp를 더 해준..

[백준] 1197 최소 스패닝 트리 (JAVA)

✉️문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 📝 접근 최소 스패닝 트리를 구하는 문제이다. 최소 스패닝 트리를 구하는 방법은 2가지이다. 1. 크루스칼 알고리즘 2. 프림 알고리즘 이번 문제에서는 크루스칼 알고리즘을 이용하였다. 구현 방법은 다음과 같다. 1. Edge라는 클래스를 만들어 cost를 기준으로 오름차순 정렬한다. 2. List를 순회하면서 연결되지 않은 간선을 연결한다. ..

[백준] 1916 최소비용 구하기 (Java)

✉️문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 📝 접근 그래프 알고리즘 중 다익스트라 알고리즘을 이용하였다. 다음의 문장에서 다익스트라 알고리즘을 이용해야겠다는 생각이 들었다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라." 다익스트라 알고리즘은 최단 경로 탐색 알고리즘으로 한 정점에서 모든 정점으로 가는 최단 경로를 구할 수 있다. 만약 문제에서 한 정점에서 모든 경로로의 최단..

[백준] 17425 약수의 합2 (Java)

✉️문제 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 📝 접근 1. 테스트 케이스가 여러개이므로 미리 배열에 값들을 저장해 놓아야 한다. // f(A)를 구하는 과정 for(int i = 1; i < SIZE; i++) { for(int j = i; j < SIZE; j = j + i) { arr[j] += i; } } // g(A) 구하기 for(int i = 1; i < SIZE..