데일리썽

문제 제목 : 평범한 배낭

난이도 : 하

문제 유형 : 동적 프로그래밍(DP)

추천 풀이 시간 : 30분 (못하면 2배 60분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

https://www.acmicpc.net/problem/12865

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();    
        int[][] dp = new int[n + 1][k + 1];
        
        for (int i = 1; i < n + 1; i++) {
            int w = sc.nextInt();
            int v = sc.nextInt();
            
            for (int j = 1; j < k + 1; j++) {
                if (j < w) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
                }
            }
        }
        
        System.out.println(dp[n][k]);
    }
}

문제 제목 : 01타일

난이도 : 하

문제 유형 : 동적 프로그래밍(DP)

추천 풀이 시간 : 20분 (못하면 2배 40분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

https://www.acmicpc.net/problem/1904

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long[] dp = new long[1000001];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
        }  
        
        System.out.println(dp[n]);
    }
}

문제 제목 : 파도반 수열

난이도 : 하

문제 유형 : 동적 프로그래밍(DP)

추천 풀이 시간 : 20분 (못하면 2배 40분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

https://www.acmicpc.net/problem/9461

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        long[] dp = new long[101];
        for (int i = 1; i < 101; i++) {
            if (i <= 3) {
                dp[i] = 1;
            } else if (i <= 5) {
                dp[i] = 2;
            } else {
                dp[i] = dp[i - 1] + dp[i - 5];
            }
        }  
        
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            System.out.println(dp[n]);
        }
    }
}

문제 제목 : 2×n 타일링

난이도 : 하

문제 유형 : 동적 프로그래밍(DP)

추천 풀이 시간 : 20분 (못하면 2배 40분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

https://www.acmicpc.net/problem/11726

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[1001];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i < n + 1; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
        
        System.out.println(dp[n]);
    }
}

1. 동적 계획법 (Dynamic Programming)

입력 크기가 작은 부분 문제들을 해결한 후 이 해를 활용해서 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘

상향식 접근법, 가장 최하위 해답을 구한 후 이를 저장하고 해당 결과값을 이용해 상위 문제를 풀어가는 방식

Memoization 기법 사용

Memoization (메모이제이션) : 프로그램 실행 시 이전에 계산한 값을 저장, 다시 계산하지 않도록 전체 실행 속도를 빠르게

문제를 잘게 쪼갤 때, 부분 문제는 서로 중복됨, 재활용

2. 분할 정복 (Divide and Conquer)

문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제를 답을 얻는 알고리즘

하양식 접근법, 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식

재귀함수로 구현

문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음

3. 공통점과 차이점

공통점

• 문제를 잘게 쪼개서 가장 작은 단위로 분할

차이점

• 동적 계획법 : 부분 문제는 중복되어 상위 문제 해결 시 재활용, Memoization 기법 사용
• 분할 정복 : 부분 문제는 서로 중복되지 않음, Memoization 기법 사용 안함

4. 피보나치 수열을 동적 계획법으로 작성

import java.util.*;

public class DynamicProgramming {
    public static void dynamicProgramming() {
        for (int i = 1; i < 10; i++) {
            System.out.println(fibo(i));
        }
        
    }
    
    //1. 재귀 활용
    public Integer fibo(Integer num) {
    	if (num <= 1) {
            return num;
        }
        return fibo(num - 1) + fibo(num - 2);
    }

    //2. 동적 프로그래밍 활용
    public Integer fiboDp(Integer num) {
    	int[] cache = new int[num];
        cache[0] = 0;
        cache[1] = 1;
        
        for (int i = 2; i < num + 1; i++) {
        	cache[i] = cache[i - 1] + cache[i - 2];
        }
        
        return cache[num];
    }
}

1. 재귀 용법

함수 안에서 동일한 함수를 호출하는 형태

코드 작성 패턴을 익히자

2. 예제

n! = n x (n - 1)!

import java.util.*;

public class RecursiveCall {
    public static void recursiveCall() {
        for (int i = 1; i < 10; i++) {
            System.out.println(factorial(i));
        }
        
    }
    
    public Integer factorial(Integer num) {
    	if (num > 1) {
            return factorial(num - 1);
        } else {
            return num;
        }
    }
}

    public Integer factorial(Integer num) {
    	if (num <= 1) {
            return num;
        }
        return factorial(num - 1);
    }

시간복잡도 O(n)

공간복잡도 O(n)

3. 재귀 호출의 일반적인 형태

fun(입력) {
    if (입력 > 일정값) {
    	return fun(입력 - 1);
    } else {
    	return 일정값, 입력값, 또는 특정값;
    }
}

fun(입력) {
    if (입력 <= 일정값) {
    	return 일정값, 입력값 또는 특정값;
    } 
    fun(입력보다 작은 값);
    return 결과값;
}

4. 연습

import java.util.*;

public class RecursiveCall {
    public static void recursiveCall() {
        for (int i = 1; i < 10; i++) {
            System.out.println(multiple(i));
        }
    }
    
    // 1. 1부터 num까지의 곱이 출력
    public Integer multiple(Integer num) {
    	if (num <= 1) {
            return num;
        } else {
            return num * multiple(num - 1);
        }
    }
}

문제 제목 : 프린터 큐

난이도 : 하

문제 유형 : 큐, 구현, 그리디

추천 풀이 시간 : 25분 (못하면 2배 50분)

https://www.acmicpc.net/problem/1966

import java.util.*;

class Docs {
    private int index;
    private int priority;
    
    public Docs(int index, int priority) {
        this.index = index;
        this.priority = priority;
    }
    
    public int getIndex() {
        return this.index;
    }
    
    public int getPriority() {
        return this.priority;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        int n;
        int m;
       
        for (int i = 0; i < tc; i++) {
            n = sc.nextInt();
            m = sc.nextInt();
            
            Queue<Docs> docsQueue = new LinkedList<Docs>();
            Queue<Integer> prioQueue = new PriorityQueue<Integer>();
            
            for (int j = 0; j < n; j++) {
                int priority = sc.nextInt();
                docsQueue.add(new Docs(j, priority));
                prioQueue.add(-priority);
            }
            
            int cnt = 0;
            while (true) {
                Docs docs = docsQueue.poll();
                if (docs.getPriority() >= -prioQueue.peek()) {
                    cnt++;
                    prioQueue.poll();
                
                    if (docs.getIndex() == m) {
                        System.out.println(cnt);
                        break;
                    }
                } else {
                    docsQueue.add(new Docs(docs.getIndex(), docs.getPriority()));
                }
            }
        }
    }
}

문제 제목 : 스택 수열

난이도 : 하

문제 유형 : 스택, 그리디

추천 풀이 시간 : 30분 (못하면 2배 60분)

https://www.acmicpc.net/problem/1874

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ArrayList<Character> result = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int num = 1;
        for (int i = 0; i < n; i++) {
            int data = Integer.parseInt(br.readLine());
            while (num <= data) {
                stack.push(num++);
                result.add('+');
            }
            if (stack.peek() == data) {
                stack.pop();
                result.add('-');
            } else {
                System.out.println("NO");
                return;
            }
        }
        
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
}