Algorithm(49)
-
[알고리즘] 1183. 동전 자판기 (하)
0. 문제 JUNGOL code_blocks 코드 보기 www.jungol.co.kr 1. 문제 이해 그리디 - 동전자판기 변형 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class JOL1183 { static int W, allMoney, useCnt; static int[] cnt, ret; static final int[] coins = { 500, 100, 50, 10, 5, 1}; public static void main(String[] args) throws Exception { BufferedReader br = new Buffere..
2024.02.19 -
[알고리즘] 1828. 냉장고
0. 문제 JUNGOL code_blocks 코드 보기 www.jungol.co.kr 1. 문제 이해 그리디 알고리즘 - Activity-Selection Problem 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class JOL1828 { static int N; static Thing[] arr; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamRead..
2024.02.19 -
[알고리즘] 1931. 회의실 배정
0. 문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 문제 이해 그리디 알고리즘 - Activity-Selection Problem 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class BOJ1931 { private static class Meeting implements Comparable { int start, end; ..
2024.02.18 -
[Java] Greedy algorithm
1. Greedy algorithm 문제 상황 : 최적해를 구하기 위해서 사용되는 근사적인 방법. (보통 최대 또는 최소를 구한다.) 원리 : 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 한계 : 각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었을 때, 그것이 반드시 최적이라고 보장할 수 없다. : 대부분의 그리디 알고리즘은 몇몇 단순하고 제한된 문제에 적용된다. 필수 조건 : 원문제의 최적해 = 탐욕적 선택 속성 + 최적 부분 구조 : 탐욕적 선택이 최적해로 이어진다는 것을 증명해야 한다. (탐욕적 선택 속성) : 하나의 선택을 풀면 하나의 하위 문제가 ..
2024.02.18 -
[알고리즘] 4012. 요리사
0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 조합 next_Permutation 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class SWEA4012 { static int N, R, ret; // 식재료 숫자, 음식 간의 최소 차이 static int A, B; // A음식, B음식 static int[][] map; // 조합 시너지 public static void main(String[] args) throws Exce..
2024.02.18 -
[알고리즘] 1861. 정사각형 방
0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 dfs 2. 제출 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * SWEA1861 */ public class SWEA1861 { static int[][] map; static int N, num, max; // N, 방번호, 이동할 수 있는 횟수 static int[] dy = {-1, 0, 1, 0}; static int[] dx = {0, 1,..
2024.02.18 -
[알고리즘] 11286. 절댓값 힙
0. 문제 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 문제 이해 Heap Priority Queue Comparator 2. 제출 가. Priority Queue로 풀기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BO..
2024.02.18 -
[알고리즘] 1991. 트리 순회
0. 문제 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 1. 문제 이해 트리 dfs 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ1991 { static int N; // 알파벳 개수 26개 static Node[] tree; static StringBuffer sb; public static void main(String[]..
2024.02.18