회고

• 칸에 쓰여진 수의 합의 최대.
• 각 테트로미노는 연속된 4개의 칸으로 이루어진 도형
• 즉, DFS 로 depth <= 4 까지 최댓값을 구하면 된다
• ㅗ,ㅜ,ㅏ,ㅓ 테트로미노의 경우는 DFS로 불가능하므로 따로 구해야 함

풀이

• 전형적인 DP 문제.
• dp[i] = max(dp[i-1] + v[i], dp[i-1] - v[i])  if, dp[i-1] + v[i] < M, 0< dp[i-1] - v[i])
• 마지막 곡 의 dp[i] 값이 정답

풀이

회고

• 최대/최소 구하는 문제는 DFS 로
• 기저 조건은 적어도 P개의 발전소가 고장나 있지 않도록 고친다
• 그렇다면, 3 개의 발전소가 고장나 있지 않은 상태는 다양하다
  • 1, 0, 0, 1, 1
  • 0, 1, 1, 1, 0
  • 0, 0, 1, 1, 1
  • ...
• 따라서 고장나 있지 않은 발전소 상태를 bit 값으로 표현 (발전소 최대 16개, 2^16)
• dp[n][bit]
• 이를 memoization 한다

풀이

문제

은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다.

발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다.

적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값이다. 그 다음 줄에는 각 발전소가 켜져있으면 Y, 꺼져있으면 N이 순서대로 주어진다. 마지막 줄에는 P가 주어진다. 비용은 50보다 작거나 같은 음이 아닌 정수이고, P는 0보다 크거나 같고, N보다 작거나 같은 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다. 불가능한 경우에는 -1을 출력한다.

소스

회고

• 어떤 값을 0번째부터 부터 하나씩 선택, 안선택 하는 문제는 DP 로 풀어야 함 (DFS)
• 하지만 N 이 50이므로, recursive call 을 하게되면 stack overflow 발생..
  • memoization 이 필요
• dp[사용한 조각 갯수][왼쪽 탑 높이][오른쪽 탑 높이] 이러면..
  • 50 * 500000 * 500000 헐
• dp[N][diff] 로 푼다
• dfs(n, diff) 아래 값 들 중 max
1. dp[n][diff] 또는 
2. dfs(n+1, diff)
3. difs(n, arr[n] + diff)
4. dfs(n , |diff - arr[n]|)

풀이

소스

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int N;
    public static int[][] dp;
    public static int[] arr;
    public static int inf = 1 << 20;

    public static int search(int n, int diff) {
        if (diff > 250000)
            return -inf;

        if (N == n) {
            if (diff == 0)
                return 0;
            else
                return -inf;
        }

        if (dp[n][diff] != -1)
            return dp[n][diff];

        // 아무 선택하지 않은 경우
        dp[n][diff] = search(n + 1, diff);

        // 차이를 더 벌리는 경우
        dp[n][diff] = Math.max(dp[n][diff], search(n + 1, diff + arr[n]));

        // 차이를 좁히는 경우
        if (arr[n] > diff) {
            dp[n][diff] = Math.max(dp[n][diff], diff + search(n + 1, arr[n] - diff));
        } else {
            dp[n][diff] = Math.max(dp[n][diff], arr[n] + search(n + 1, diff - arr[n]));
        }

        return dp[n][diff];
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        dp = new int[N + 1][250001];
        arr = new int[N + 1];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();

            Arrays.fill(dp[i], -1);
        }

        int ans = search(0, 0);
        System.out.println(ans > 0 ? ans : -1);

        sc.close();
    }

}

p.91 ~ p.126

반복문

알고리즘의 수행시간을 지배하는 것은 반복문

반복문의 수행 횟수는 입력의 크기에 대한 횟수로 표현

수행시간에 따른 알고리즘 분류

선형 시간 알고리즘

입력의 크기에 대비해 걸리는 시간을 그래프로 그리면 직선인 경우.

우리가 찾는 좋은 알고리즘.

선형 이하 시간 알고리즘

N을 계속 절반으로 나누는 일을 1이하가 될때까지 지속

lgN: 100,000 을 17번만 나누면 1에 도달 함

ex) 이진 탐색 알고리즘

• 정렬이 필요 A[ ]
• A[i-1] < x <= A[i]

다항 시간 알고리즘

반복문의 수행 횟수를 다항식으로 표현

대다수의 알고리즘에 해당

지수 시간 알고리즘

완전탐색 방식, 재귀호출을 통해 할지 말지 결정하는 알고리즘

ex) DFS

n 가지 경우, 모든 조합의 수 2ⁿ, 조합이 맞는지 여부 체크 m*n

∴ 재귀호출() 2ⁿ + isValid() m*n = mn2ⁿ

입력으로 주어지는 숫자의 갯수가 아닌 숫자의 값에 따라 지수시간이 될 수도 있음

시간 복잡도

시간복잡도가 높다

입력의 크기가 증가할 때 수행시간이 급격히 증가

시간복잡도가 낮다

입력의 크기가 증가해도 수행시간이 비슷

알고리즘 수행시간은 보통 최악의 시간을 측정

O 표기법 (Big-O Notation)

주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지 다 버림

정렬 알고리즘

선택 정렬은 무조건 O(N²)

삽입 정렬은 O(N) ~ O(N²) 까지 입력에 따라 다름

∴ 대부분의 경우 삽이 정렬이 더 빠름

∴ 삽입 정렬은 O(N²) 정렬 중 가장 빠른 알고리즘

수행 시간 어림짐작하기

1초 ≒ 1억

ex)

알고리즘 선택에 따른 수행 시간 비교

문제) 1차원 배열 연속된 부분 구간의 합이 최대인 구간

완전 탐색: O(N³)

반복문 2개 + 메모이제이션: O(N²)

분할 정복 알고리즘: O(NlgN)

동적 계획법: O(N)

AngularJS 는 Google에서 개발된 JavaScript Framework로써 SPA(Single Page Application)을 개발할 때 유용한 프레임웤.

https://angularjs.org/

Start !

HTML 문서에서 공백은 spacebar를 아무리 눌러도 삽입되지 않는다.

 이때는 &nbsp  태그를 삽입하여 공백을 넣어준다.

예제

공백을     삽입할 경우에는      nbsp 태그를 이용하여     연속적으로 삽입합니다.

공백을     삽입할 경우에는      nbsp 태그를 이용하여     연속적으로 삽입합니다.