0. 문제 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 1. 문제 이해 분할 정복 알고리즘 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ1074 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new ..

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..

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..

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..

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; ..

1. Greedy algorithm 문제 상황 : 최적해를 구하기 위해서 사용되는 근사적인 방법. (보통 최대 또는 최소를 구한다.) 원리 : 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 한계 : 각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었을 때, 그것이 반드시 최적이라고 보장할 수 없다. : 대부분의 그리디 알고리즘은 몇몇 단순하고 제한된 문제에 적용된다. 필수 조건 : 원문제의 최적해 = 탐욕적 선택 속성 + 최적 부분 구조 : 탐욕적 선택이 최적해로 이어진다는 것을 증명해야 한다. (탐욕적 선택 속성) : 하나의 선택을 풀면 하나의 하위 문제가 ..

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..

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,..