분류 전체보기(514)
-
[Java] 분할정복, 백트레킹, 이진탐색
1. 분할 정복 Divide and Conquer 해결할 문제를 여러 작은 부분 문제로 나눈다. 나눈 작은 문제를 각각 해결한다. 접근법 Top-down approach bottom-up approach // Power 함수 import java.util.Scanner; // x^n을 O(logN) 시간복잡도로 구하는 분할 정복 알고리즘 public class SquareNumberTest { static int callCnt1; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); int n = sc.nextInt(); // 최대 10억 System.out.println(exp1..
2024.02.19 -
[알고리즘] 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 -
[알고리즘] 풀었던 문제 (240208)
1. 16546. Baby-gin 구현 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 1228. 암호문1 String.split() LinkedList SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 3. 16926. 배열 돌리기 1 배열 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3..
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