결국, 인덱스 == 정렬

인덱스란?

• DB의 테이블에 대한 검색 속도를 향상시켜주는 자료구조
• SELECT의 성능 향상 (대신 insert, update, delete의 성능은 희생됨)

• 기능 자체의 행위가 느린 것이고, 기능을 위한 조회 행위는 빨라짐

인덱스 사용에 적합한 경우

• 규모가 큰 테이블

• 데이터의 range가 크고 중복도가 낮은 컬럼

  카디널리티(Cardinality)가 가장 높은 것을 잡아야 한다 : 중복된 수치 성별, 학년 = 카디널리티 낮음 주민등록번호, 계좌번호 = 카디널리티 높음

• 조회가 많거나 정렬된 상태가 유용한 컬럼

• where, order by, join 이 자주 사용되는 컬럼

인덱스의 자료구조

해시 테이블 (Hash Table)

• (key, Value) = (컬럼의 값, 데이터의 위치) 로 인덱스를 구현
• O(1)의 시간

B+Tree

• 기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.

• B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다.

• 그리고 leaf node끼리는 Linked list로 연결되어있다. B-Tree 예시 B+Tree 예시

=> B+Tree 구조

• 인덱스의 두번째 컬럼은 첫번째 컬럼에 의존해서 정렬
  • 즉, 두번째 컬럼 정렬은, 첫번째 컬럼이 같은 열에서만 의미가 있음
• _Root에서 Leaft까지 오고가는 횟수를 얼마나 줄이느냐_에 인덱스의 성능이 달렸음

문제 링크

성능 요약

메모리: 73.9 MB, 시간: 1.21 ms

구분

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

문제 설명

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• 2 ≤ info의 길이 ≤ 17
  • info의 원소는 0 또는 1 입니다.
  • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
  • 0은 양, 1은 늑대를 의미합니다.
  • info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
• edges의 세로(행) 길이 = info의 길이 - 1
  • edges의 가로(열) 길이 = 2
  • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
  • 0번 노드는 항상 루트 노드입니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

주어진 입력은 다음 그림과 같습니다.

0번 - 2번 - 5번 - 1번 - 4번 - 8번 - 3번 - 7번 노드 순으로 이동하면 양 5마리 늑대 3마리가 됩니다. 여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리가 되어 양이 모두 잡아먹히게 됩니다. 따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리입니다.

제한시간 안내

• 정확성 테스트 : 10초

문제 풀이

• 처음엔 진짜 막막했다 어떻게.. 오르락 내리락.. 해서 찾는 건가? 라는 생각을 하고 거의 하루를 낭비했던 문제
• 최근에 다시 풀면서 새롭게 접근하고자 했다

• ArrayList[] 배열을 통해서 다음 탐색할 노드를 저장해두고 찾았다
• 자식을 넣고 자식을 탐색하면 내 자식과 형제를 넣는 식으로 dfs 탐색을 진행하여
• 최대의 양의 수를 갱신했다.

Solution

import java.util.*;
import java.lang.*;


class Solution {
    static int max = 0;
    static int[] animal;
    static ArrayList<Integer>[] childs;

    public int solution(int[] info, int[][] edges) {
        animal = info;
        childs = new ArrayList[info.length]; // 자식 값 저장
        for(int[] edge : edges) {
            if(childs[edge[0]] == null) {
                childs[edge[0]] = new ArrayList<>();
            }    
            childs[edge[0]].add(edge[1]);
        }

        List<Integer> check = new ArrayList<>();
        check.add(0); // 루트부터 탐색
        dfs(0, 0, 0, check);

        return max;

    }

    public void dfs(int idx, int sheep, int wolf, List<Integer> check) {
        if(animal[idx] == 0) {
            sheep++;
        }else {
            wolf++;
        }

        if(sheep <= wolf) return; // 잡아먹힘

        max = Math.max(sheep, max);

        // 다음 갈 수 있는 곳 갱신해줌
        List<Integer> next = new ArrayList<>();
        next.addAll(check);
        next.remove(Integer.valueOf(idx)); // 현재는 탐색했으니까 빼줌
        if(childs[idx] != null) { // 리프노드가아니면
            for(int child: childs[idx]) {
                next.add(child);
            }
        }

        for(int node : next) {
            dfs(node, sheep, wolf, next);
        }

    }

}

문제 링크

성능 요약

메모리: 13980 KB, 시간: 140 ms

분류

애드 혹(ad_hoc), 분할 정복(divide_and_conquer)

문제 설명

동호는 종이를 접는데 옆에서 보고 접으려고 한다. 옆에서 본다는 말은 아래 그림과 같이 본다는 뜻이다. 동호는 종이를 반으로 접을 때, 아래와 같이 두가지중 하나로만 접을 수 있다.

1. 오른쪽 반을 반시계 방향으로 접어서 왼쪽 반의 위로 접는다.
2. 오른쪽 반을 시계 방향으로 접어서 왼쪽 반의 아래로 접는다.

아래의 그림은 위의 설명을 그림으로 옮긴 것이다.

한 번의 종이 접기가 끝났을 때, 동호는 종이 접기를 원하는 만큼 더 할 수 있다. 종이 접기를 한번 접을 때 마다 두께는 2배가 되고 길이는 절반이 될 것이다.

종이 접기를 여러 번 했을 때 (안접을 수도 있다), 동호는 종이를 다시 피기로 했다. 그러고 나서 다시 접고 이렇게 놀고 있었다. 옆에서 보고 있던 원룡이는 동호를 위해 종이를 접어서 주기로 했다.(원룡이는 동호의 규칙대로 접지 않는다.) 동호는 그리고 나서 원룡이가 접었다 핀 종이를 다시 동호의 규칙대로 접을 수 있는지 궁금해졌다.

위의 저 종이를 접었다 피면 다음과 같은 그림처럼 펴진다.

종이가 시계방향으로 꺽여있으면 OUT이고, 반시계방향으로 꺾여있으면 IN이다.

종이가 접혀있는 정보가 왼쪽부터 오른쪽까지 차례대로 주어졌을 때, 이 종이를 동호의 규칙대로 접을 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1은 위의 그림에서 OUT을 의미하고 0은 위의 그림에서 IN을 의미한다. 예를 들어, 위의 그림과 같은 모양은 100으로 나타낼 수 있다. 문자열의 길이는 3000보다 작으며, 항상 2^N-1꼴이다. (N ≥ 1)

출력

T개의 줄에 차례대로 각각의 종이를 동호의 방법대로 다시 접을 수 있으면 YES를, 접을 수 없으면 NO를 출력한다.

문제 풀이

• 종이를 반접고 그걸 또 반접고 하는 방식으로 접어나갈 수 있다
• 그래서 숫자를 보고 중간을 기준으로 양쪽이 대칭이어야 하며
• 대칭인걸 확인하고 해당 종이를 또 반반 나눠서 양쪽을 접을 수 있는 숫자인지 확인해주어야한다
• 해당 종이가 한칸이 될때까지 양쪽을 쪼개서 확인하는 전형적인 분할정복의 문제였다.

Solution

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

public class Main {
    static char[] paper;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = sc.nextInt();
        for(int i=0; i<T; i++) {
            String p = sc.next();
            int n = p.length();
            paper = new char[n];
            paper = p.toCharArray();

            if(check(0, n-1)) {
                sb.append("YES\n");
            } else {
                sb.append("NO\n");
            }
        } // test case

        System.out.println(sb.toString().trim());
    }

    public static boolean check( int start, int end) {
        if (start == end) { // 끝까지 탐색하면 true
            return true;
        }

        int mid = (start+end)/2; // 중간 값
        for(int i=start; i<mid; i++) {
            if(paper[i] == paper[end-i]) return false;
        }
        return check(start, mid-1) && check(mid+1, end); // 양쪽 동시 탐색

    }
}

문제 링크

성능 요약

메모리: 16432 KB, 시간: 156 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2⁶³-1보다 작거나 같다.

문제 풀이

• dp 인걸 알면서도 고집스럽게 dfs로만 풀어봤다가 바로 시간초과 하하
• dp + dfs 로 풀었다
• 시작 점에선 방문을 했는지 확인 후, 경우의 수 return 또는 처음 방문이라면 dfs로 이동
• 점화식으로 따지자면
  • dp[r][c] = (r,c)까지 올 수 있는 경우의 수

Solution

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

public class Main {
    static int N;
    static int[][] map;
    static long[][] dp; // 2^63-1 이므로 long

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        dp = new long[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
            Arrays.fill(dp[i], -1);
        } // 입력


        System.out.println(go(0, 0));
    }

    public static long go(int r, int c) {
        if (r == N - 1 && c == N - 1) {
            return 1;
        }

        if (dp[r][c] != -1) { // 처음방문이 아니라면 해당 위치의 경우의 수 return
            return dp[r][c];
        }

        dp[r][c] = 0;
        int move = map[r][c];
        int nextRight = c + move; // 좌로이동
        int nextBottom = r + move; // 아래로이동

        if(nextRight < N) {
            dp[r][c] += go(r, nextRight);
        }

        if(nextBottom < N) {
            dp[r][c] += go(nextBottom, c);
        }

        return dp[r][c];
    }
}

문제 링크

성능 요약

메모리: 53.11 MB, 시간: 579 ms

문제 설명

대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다. 병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다. 클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다.

현지도 이러한 머신 러닝용 클러스터를 관리하는 역할을 맡고 있다. 클러스터의 성능은 컴퓨터의 수가 많아질 수록, 각각의 성능이 올라갈 수록 향상된다. 그런데 어느 날 협업 중인 몇몇 연구실에서 클러스터의 성능을 업그레이드해 달라는 요청을 보내 왔다. 이들은 특히 클러스터를 이루는 각각의 컴퓨터 중 성능이 가장 낮은 컴퓨터의 성능이 병목이 된다고 알려 왔다.

이 클러스터에는 N대의 컴퓨터가 있으며, 각각의 성능은 a_i라는 정수로 평가할 수 있다. 현지는 각각의 컴퓨터에 비용을 들여 업그레이드를 진행할 수 있다. 성능을 d만큼 향상시키는 데에 드는 비용은 d²원이다. (단, d는 자연수이다.)

업그레이드를 하지 않는 컴퓨터가 있어도 되지만, 한 컴퓨터에 두 번 이상 업그레이드를 수행할 수는 없다.

업그레이드를 위한 예산이 B원 책정되어 있다. 현지의 목표는 B원 이하의 총 비용으로 업그레이드를 수행하여, 성능이 가장 낮은 컴퓨터의 성능을 최대화하는 것이 목표이다. 이 최선의 최저성능을 계산하는 프로그램을 작성하시오.

제약조건

1≤ N ≤ 10⁵인 정수

1≤ a_i ≤10¹⁰인 정수

1≤ B ≤10¹⁸인 정수

입력형식

첫째 줄에 컴퓨터의 수와 예산을 나타내는 정수 N과 B가 공백을 사이에 두고 주어진다. 둘째 줄에 각 컴퓨터의 성능을 나타내는 N개의 정수 a₁, a₂, ..., a_n이 공백을 사이에 두고 주어진다.

B의 범위가 매우 넓어, 사용하는 프로그래밍 언어에 따라 64비트 정수형을 사용해야 할 수 있음에 유의하시오.

출력형식

첫째 줄에 예산을 효율적으로 사용했을 때, 성능이 가장 낮은 컴퓨터의 성능으로 가능한 최댓값을 출력하시오.

문제 풀이

• 시간초과 날정도로 큰 숫자라서 무작정 탐색하면 안된다는 건 알았지만
• 생각이 안나서 해설 찾아보니까 이분탐색 사용하면 된다 라고 해서 이분탐색 사용 문제 해설
• 소프티어 문제들은 개념, 자료구조 사용만 잘하면 잘 풀리는 문제들인 것 같다
  • 소프티어 문제들로 개념을 더 익히면 좋을 듯

Solution

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

public class C1204_슈퍼컴퓨터클러스터 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long b = sc.nextLong();

        int[] computers = new int[n];
        for (int i = 0; i < n; i++) {
            computers[i] = sc.nextInt();

        }

        Arrays.sort(computers); // 오륾차순 정렬
        long left = computers[0]; // 최소값으로 초기화
        long right = computers[n - 1] + (long) Math.sqrt(b); // 최대값 + B원으로 최대 업그레이 할 수 있는 성능

        long answer = 0;
        while (left <= right) {
            long mid = (left + right) / 2;
            if (upgrade(computers, b, mid)) {
                left = mid + 1;
                answer = mid; // upgrade가 true이므로 mid까지는 업그레이 가능
            } else {
                right = mid - 1; // mid 값 만들 비용이 안됨
            }
        }

        System.out.println(answer);
    }

    public static boolean upgrade(int[] arr, long b, long min) {
        long cost = 0; // min을 만들 비용 계산
        for (int com : arr) {
            if (com < min) { // 최소가 되야할 값보다 작은 수는 업그레이드 비용 계산해줌
                cost += (min - com) * (min - com);
                if (cost > b) return false;
            }
        }
        return true;
    }


}

문제 링크

구분

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT

채점결과

정확성: 53.8
효율성: 46.2
합계: 100.0 / 100.0

문제 설명

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

제한사항

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 100
• 1 ≤ board의 열의 길이 (= M) ≤ 100
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
• 1 ≤ skill의 행의 길이 ≤ 100
  • 1 ≤ degree ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

입출력 예

문제 풀이

• 처음엔 누적합으로 풀겠다는 감도 안왔지만
• for문이 세번 중첩되니까 효율성에서 떨어지는 걸 알게 되고 빠르게 푸는 방법을 찾다가 누적합으로 풀어야 한다는 것을 알게 되었다.
• 누적합을 예전에 배웠지만 다시 개념을 공부하고 푸니까 생각보다 간단하게 풀렸다 !
• 누적합을 가로/세로 두번 나눠서 구하는 방법과 한번에 사각형을 기준으로 구하는 방법 두가지 다 정답이다.

누적합

• 누적합은 배열에 들어있는 값이 바뀌지 않는다는 점을 이용 -> 구간의 합도 변하지 않음
• 누적합 개념 추천 문제 : BOJ_2167. 2차원 배열의 합

Solution

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int row = board.length;
        int col = board[0].length;
        int[][] damage = new int[row+1][col+1]; // 공격 좌표 저장
        // skill 계산
        for (int[] ints : skill) {
            int power = ints[5];
            if (ints[0] == 1) {
                power = -power;
            }
            //skill[i][1]:x1, skill[i][2]:y1, skill[i][3]:x2, skill[i][4]:y2
            damage[ints[1]][ints[2]] += power;
            damage[ints[1]][ints[4] + 1] -= power;
            damage[ints[3] + 1][ints[2]] -= power;
            damage[ints[3] + 1][ints[4] + 1] += power;
        }

        // 누적합 계산
        int[][] sum = new int[row+1][col+1];
        // 가로로
        for(int i=0; i<row+1; i++) {
            sum[i][0] = damage[i][0];
            for(int j=1; j<col+1; j++) {
                sum[i][j] = damage[i][j] + sum[i][j - 1];
            }
        }
        // 세로로
        for(int j=0; j<col+1; j++) {
            for(int i=1; i<row+1; i++){
                sum[i][j] += sum[i-1][j];
            }
        }

        //한번에 구하기
        // sum[0][0] = damage[0][0]; // 0,0 값 넣고
        // for(int i=1; i<row+1; i++) { // 0번째 열 계산
        //     sum[i][0] = damage[i][0] + sum[i - 1][0];
        // }
        // for(int i=1; i<col+1; i++) { // 0번째 행 계산
        //     sum[0][i] = damage[0][i] + sum[0][i - 1];
        // }
        // for(int i=1; i<row+1; i++) {
        //     for(int j=1; j<col+1; j++) {
        //         sum[i][j] = damage[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
        //     }
        // }

        // 누적합(총 데미지)과 원래 상태 더하기
        int answer = 0;
        for(int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if(board[i][j] + sum[i][j] > 0) {
                    answer++;
                }
            }
        }
        return answer;
    }
}

문제 링크

분류

누적 합(prefix_sum), 두 포인터(two_pointer)

문제 설명

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

문제 풀이

• 투포인터로 문제 접근
• sum이 S 보다 작으면 뒤의 포인터를 한칸 증가
• sum이 S 보다 크면 앞의 포인터를 한칸 증가
• 커질때마다 ans를 비교해서 작은 값으로 저장

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int totalSum = 0;

        int[] arr = new int[N];
        for (int n = 0; n < N; n++) {
            arr[n] = Integer.parseInt(st.nextToken());
            totalSum += arr[n];
        }
        if (totalSum < S) {
            System.out.println(0);
            return;
        }

        //투포인터로 구하기
        int s = 0;
        int e = 0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        while (true) {
            if (sum >= S) {
                ans = Math.min(e - s, ans);
            } else if (e == N) {
                break;
            }

            if (sum < S) {
                sum += arr[e++];
            } else {
                sum -= arr[s++];
            }
        }

        System.out.println(ans);

    }


}

문제 링크

구분

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

이진트리를 수로 표현하는 방법은 다음과 같습니다.

1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.

이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

다음은 이진트리를 수로 표현하는 예시입니다.

주어진 이진트리는 다음과 같습니다.

주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.

노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.

당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.

이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ numbers의 길이 ≤ 10,000
  • 1 ≤ numbers의 원소 ≤ 10¹⁵

입출력 예

문제 풀이

• 처음엔 아 쉽네 ! 했는데 포화이진트리를 생각을 못하고 그냥 String변환해서 푸는 생각만 했었다.
• 문제1. 숫자를 이진수로 바꿔서 해당 숫자를 포화이진트리에 채워넣는 과정을 생략함
  • 높이가 H인 포화 이진트리 전체 노드 수 = 2^H - 1
  • 부모 노드가 0일 경우 리프노드까지 모든 자식 노드는 1이면 안됨
• 문제2. Long을 이진수로 변환하는 과정
  • 처음에 분명 내 풀이가 맞는 것 같은데 16번 tc부터 다 틀려서 왜지왜지 했는데
  • Integer.toString(n, 2)로 이진수로 변환해서 그런거였음
  • _** Long.toBinaryString(n)**_으로 변환했어야 했다.

Solution

class Solution {
    static int result;
    static boolean[] binary;
    static int treeLen;

    public int[] solution(long[] numbers) {
        int n = numbers.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            String b = Long.toBinaryString(numbers[i]);

            int length = b.length();
            int exp = 1;
            do {
                treeLen = (int) Math.pow(2, exp++) - 1;
            } while (treeLen < length);

            binary = new boolean[treeLen];
            int idx = treeLen - length;
            for(int j=0; j<length; j++) {
                binary[idx++] = b.charAt(j) == '1';
            }

            result = 1;
            possible(0, treeLen-1, false); // s, e, 해당 루트가 더미인지
            answer[i] = result;
        }
        return answer;

    }

    public static void possible(int s, int e, boolean check) {
        int mid = (s+e)/2;
        if(check && binary[mid]) { //루트가 0이면 자식노드들에서 1이나오면 안됨
            result = 0;
            return;
        }

        // 내가 마지막 노드가 아니면 재귀
        if(s!=e) {
            possible(s, mid-1, !binary[mid]); // 왼쪽, 현재 루트가 더미이면 check = true
            possible(mid+1, e, !binary[mid]); // 오른쪽
        }

    }
}

문제 링크

문제 설명

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

문제 풀이

• 2*5 개수를 구하면 되겠다 싶어서 첨엔 배열로 2랑 5의 배수를 하나씩 구해서 Math.min 했는데 생각해보니까 2의배수가 5의 배수보다 많으니까 그냥 5의 배수를 구하면 되는 거였다.

Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int five = 0; // 5의배수, 2*5 배수 세야하는데 5가 더 적게나오니까 5만 세도 됨
        for (int i = 2; i <= n; i++) {
            int temp = i;
            while (temp % 5 == 0) {
                five++;
                temp /= 5;
            }
        }
        System.out.println(five);
    }

}

“코딩의 미래는 코딩을 전혀 하지 않는 것(The future of coding is no coding at all)” — GitHub CEO

노코드·로우코드

LCNC (Low-Code and No-Code) : 시각적 드래그 앤 드롭 응용 프로그램 또는 유사한 도구를 사용하여 개인 및 팀이 많은 선형 코딩없이 응용 프로그램을 프로그래밍할 수 있는 환경

• 복잡한 프로그래밍 도구나 전문 지식 없이도 구현하기 쉬운 개발 솔루션으로 개발 프로세스 간소화
• IT의 부족한 개발자 인력난 부족 문제를 해결하고, 새로운 응용 프로그램 및 인터페이스 출혈을 간소화

노코드

• 코딩을 하지 않고도 웹이나 앱 서비스를 만들 수 있도록 도와주는 서비스
• 코딩 대신 아이콘 같은 그래픽 클릭이나 드래그 앤 드롭 방식
• 노코드 플랫폼 : 윅스(Wix), 멘딕스, 아임웹, 식스샵(sixshop), 워드프레스, 카페24 등

로우코드

• 노코드 플랫폼과 같이 드래그 앤 드롭 방식
• 하지만, 어느 정도 개발에 대한 지식을 요구

장단점

장점

• 사용 편의성
  • 개발 지식 없이도 IT 서비스를 만들 수 있다 => 시간과 비용 절약
  • 제작 화면 자체가 UI
• 기존 솔루션 및 기술과의 통합 용이성
• 신속한 가치 창출

단점

• 개발 한계 : 플랫폼에서 제공하지 않는 기능은 구현할 수 없고, 유저가 많아지면 그에 맞게 백엔드 최적화가 필요하지만 LCNC 플랫폼을 사용한 사이트는 최적화가 어렵다
• 드래그 앤 드롭 방식도 결국 만드는 과정일 뿐 : 기획, 제작은 사용자의 몫
• 어쨌든 학습은 필요하다 : LCNC 플랫폼도 배경지식과 학습이 필요, 플랫폼이 다양한 만큼 플랫폼 별 차이와 활용도를 학습해야할 필요가 있다

결론

LCNC 플랫폼은 디지털 전환이 빠르게 진행되고 있는 현재 문제가 되는 IT분야의 인력난을 해결해 줄 수 있는 키워드로 떠오르고 있다. 쉽게 배우고 사용할 수 있으며 기존의 솔루션과의 통합이 쉬워 IT업계를 넘어 제조, 의료 산업에서 활용되어 디지털 전환을 가속화할 것으로 보인다. 클라우드 기업에서 산업별 AI서비스를 제공하듯, LCNC 도구도 산업에 특화된 서비스가 나올 것으로 예상된다.

• MVC
• MVP
• MVVM
• MVI 등이 있다.

이들은 모두 Model과 View를 공통적으로 가지고 있는데,

Model : 데이터 or 데이터를 생성하거나 업데이트 View : UI or 화면을 표시

프로그램의 Presentation Logic과 Business Logic을 구현하며 데이터와 UI는 필수이기 때문에, M-V 사이의 의존성도 생긴다.

Presentation Logic : 브라우저에 보이는 화면처럼 실제 눈에 보이는 GUI 화면을 구성하는 코드 Business Logic : 데이터를 보여주기 위해 데이터베이스를 검색하는 코드 및 GUI 화면에서 새롭게 발생된 데이터를 데이터베이스에 저장하는 코드 등 실제 작업을 하는 코드

Logic이 커지고 복잡해지면 생산성과 품질 저하의 우려가 있기 때문에, 유지보수와 확장성을 고려한 코딩을 위해 아키텍처에 대한 공부가 필요하다.

(주로 대중적으로 사용되고 웹에서 쓰이는 MVC와 안드로이드에서 인기있는 MVP등 공부가 필요하다.)

MVC 패턴

프로그램을 각 역할에 따라 Model, View, Controller 로 나누어 설계한 아키텍처 패턴

Model, View, Controller로 나누는 행위는 더 나은 업무의 분리와 향상된 관리를 가능하게 한다.

구성 요소

• Model : 데이터
• View : 레이아웃과 화면 처리
• Controller : 명령을 모델과 뷰 부분으로 라우팅, 데이터와 비즈니스 로직 사이의 상호동작 관리

출처 : mdn web docs

1. View에서 들어오는 모든 Input은 Controller로 전달
2. Controller는 데이터를 조작하여 Model을 업데이트
3. 업데이트 결과에 따라 View 선택

Model

데이터를 가진 객체

• 사용자가 편집하길 원하는 모든 데이터를 가지고 있어야 한다.
• View나 Controller에 대해서 어떤 정보도 알지 못한다.
• 변경이 일어나면, 변경 통지에 대한 처리 방법을 구현해야 한다.

View

UI와 같은 시각적 요소

• Model이 가지고 있는 정보를 따로 저장하면 안된다.
• Model이나 Controller와 같은 다른 구성 요소를 몰라야한다.
• 변경이 일어나면, 변경 통지에 대한 처리 방법을 구현해야 한다.

Controller

모델과 뷰를 연결, 비즈니스 로직

• Model과 View에 대해 알아야 한다.
• Model이나 View의 변경을 모니터링 한다.

장단점

장점

• 가장 단순한 패턴
• 구성 요소의 분리로, UI와 비즈니스 로직을 분리하면 애플리케이션의 시각적 요소나 실행되는 비즈니스 로직을 서로 영향없이 고칠 수 있게 되므로 유지보수의 독립적 수행이 가능
• Model 과 View 가 다른 컴포넌트에 종속되지 않아 애플리케이션의 확장성과 유연성을 확보

단점

Model 과 View 사이의 의존성 -> 프로그램이 커지고 복잡해질 수록 유지보수가 어려워짐

참고

• https://blog.naver.com/blayan/220569833085
• https://developer.mozilla.org/ko/docs/Glossary/MVC
• https://bsnippet.tistory.com/13

핀테크 (FinTech)

financial + technical 합성어 => it 기반의 새로운 금융 기술

구분

• 핀테크 1.0 : 아날로그에서 디지털로 (기존 금융회사) -> 금융산업 효율성 증대
• 핀테크 2.0 : 전통적인 디지털 금융 서비스의 개발 (기존 금융회사) -> 디지털화, 서비스 세분화
• 핀테크 3.0 : 디지털 금융 서비스의 민주화 (새로운 스타트업, 빅테크 기업) -> 서비스 융합

핀테크 산업 영역

• 자금이전, 지급결제 ; 결제 및 송금
• 수신 -> 디지털 뱅킹 ; 인터넷 전문은행
• 자산매매 중개 보관 관리 -> 디지털 자산 관리 ; 웰스테크
• 여신, 자금 조달 -> 렌딩 및 클라우드 펀딩 ; 자금 조달 및 대출, 클라우드 펀딩
• 위험 관리 -> 인슈테크 ; 보험 관련 핀테크
• 프롭테크 ; 부동산 금융 관련 핀테크

핀테크 기술

데이터 분석, 인공지능, 블록체인, 레그 테크(Reg Tech) 등 예) 핀테크 인에이블러(Enabler), 파이낸셜 테크놀로지

핀테크 기반 기술

• 모바일
  • 스마트폰, 태블릿 PC
  • 모바일 기기의 칩셋의 NFC 태깅 또는 MST(마그네틱보안전송), 바코드 및 큐알코드를 이용한 결제 활용
• 비콘 (beacon)
  • 저전력 블루투스 기술
  • 계속적으로 신호 송출하여 사용자의 위치 정보 파악
• 블록체인 (Blockchain)
  • 데이터 블록을 체인형태로 분산 저장하는 기술
  • 탈중앙화 => 거래정보 복사본을 모두가 보유하게 하여 위변조를 방지
  • 블록체인이 길어질수록 보안성이 강해지며, Hash를 통해 블록을 추가할 수 있음
• RPA (Robotic Process Automation)
  • 반복적인 수동작업을 로봇이 대신하는 프로세스
  • 통계 및 데이터 수집, 규정 준수 및 관ㄹ, 커뮤니케이션 마케팅, 거래관리 등 담당
• 빅데이터와 데이터 분석
  • 데이터 마이닝을 통한 데이터 추세, 패턴, 상관관계 분석
  • 관리자 측면 : 사용자 니즈 만족을 위한 전략 수립 및 시스템 안전관리
  • 사용자 측면 : 개인별 맞춤형 서비스
• AI, 보안 등

핀테크 현주소

기존 금융 기관과 새로운 플레이어들

1. 인에이블러 or 파이낸셜 테크놀로지 ; 각 기술 별의 플레이어의 등장
2. 디스럽터 ; 기존의 서비스를 비슷하거나 아예다른 접근을 통해 대체, 크라우드펀딩과 간편송금 등
3. 플랫폼 기반 플레이어 ;; 금융정보를 제공, 비교, 등으로 소비자에게 특정 기능 제공 -> 상품 판매나 자문으로 영역 확대

마무리

앞으로 펼쳐질 새로운 핀테크 시장 - 핀테크 4.0 시대

• 금융사는 비금융 시장에 진출하며 금융의 영역 확대롤 시도
• 빅테크, 핀테크 기업은 디지털 금융 혁신을 고도화하여 더 편리하고 똑똑한 서비스로 사용자 일상에 없어서는 안 될 핵심 서비스로 자리 잡음

핀테크 전반에서 금융적인 규제와 함께 보안, 개인정보보호가 중요하게 다뤄져야 할 것이다.

참고 자료

• https://www.lgcns.com/blog/it-trend/35486/
• https://brunch.co.kr/@musestory/36
• 핀테크FinTech 기술과 활용, 이지애 강신영

디자인 패턴과 아키텍처 패턴의 차이

아키텍처 패턴은 윤곽을 잡는 역할, 디자인 패턴은 더 세밀한 부분에 가이드라인이 되는 좁은 개념 이 둘은 유사성을 가지지만, 범위의 제한이 존재

• 건축과 비교하면 아키텍처 패턴은 건물 윤곽에 대한 가이드라인을 제시한다. ex> 오피스텔의 복도 넓이는 이정도, 층간 높이는 이만큼이 가장 적절하더라 _ 디자인 패턴은 좀 더 세밀한 부분적인 해결책을 제시한다. _ex> 오피스텔 각 방들의 인테리어, 화장실의 샤워 공간은 이정도면 적당하더라

  • 아키텍처 패턴 : 아키텍처(소프트웨어의 뼈대, 큰 구조로 다른 구성 요소를 관리하는 역할)를 설계할 떄 참조
  • 디자인 패턴 : 모듈 간의 관계 및 인터페이스를 설계할 때 참조, 특정 유형의 문제에 대한 구체적인 해결 방식

출처 : 시나공

디자인 패턴

개요

문제에 대한 전형적인 해결 방식 또는 예제 과거 소프트웨어 개발 과정에서 발견한 설계 노하우를 패턴으로 정리

• 소프트웨어를 설계할 때 특정 맥락에서 자주 발생하는 고질적인 문제들이 발생했을 때 참조할 수 있는 (재사용할 수 있는) 해결책
• "바퀴를 다시 발명하지 마라"
  • 이미 존재하는 기술이나 제품을 굳이 다시 만들기 위해 시간과 노동력을 소모하지 말라는 의미의 관용구
  • 개발 과정 중에 문제가 발생하면 새로 해결책을 구상하는 것보다 문제에 해당하는 디자인 패턴을 참고하여 적용하는 것이 더 효율적

목적

SW의 재사용성, 호환성, 유지 보수성

특징

• 특정한 구현이 아닌, 아이디어
• 항상 적용할 필요는 없지만, 문제 해결 시 참조하거나 문제를 예방하기 위해 만들어 둔 것

GoF 디자인 패턴 분류

1. 생성(Creationa) 패턴
   • 클래스나 객체의 생성과 참조 과정을 정의하는 패턴
2. 구조(Structural) 패턴
   • 구조가 복잡한 시스템을 개발하기 쉽도록 클래스나 객체들을 조합하여 더 큰 구조로 만드는 패턴, 객체간의 관계를 조직
3. 행위(Behavioral) 패턴
   • 클래스나 객체들이 서로 상호작용하는 방법이나 책임 분배 방법을 정의하는 패턴, 객체의 행위를 조직/관리/연합

GoF 디자인 패턴 종류

1. 생성 패턴
   • 추상 팩토리 (Abstract Factory)
   • 빌더 (Builder)
   • 팩토리 메소드 (Factory Method)
   • 프로토타입 (Prototype)
   • 싱글톤 (Singleton)
2. 구조 패턴
   • 어댑터 (Adapter)
   • 브리지 (Bridge)
   • 컴포지트 (Composite)
   • 데코레이터 (Decorator)
   • 퍼사드 (Facade)
   • 플라이웨이트 (Flyweight)
   • 프록시 (Proxy)
3. 행위 패턴
   • 책임 연쇄 (Chain of Responsibility)
   • 커맨드 (Command)
   • 인터프리터 (Interpreter)
   • 이터레이터 (Iterator)
   • 미디에이터 (Mediator)
   • 메멘토 (Memento)
   • 옵서버 (Observer)
   • 스테이트 (State)
   • 스트래티지 (Strategy)
   • 템플릿 메소드 (Template Method)
   • 비지터 (Visitor)

아키텍처 패턴

개요

소프트웨어 아키텍처에서 발생하는 문제점에 대한 해결 방식 또는 예제

• 문제점들에 대한 일반화되고 재사용 가능한 해결책
• 소프트웨어 디자인 패턴과 유사하지만 더 큰 범주에 속함

목적

복잡한 구조 단순화, 효율적인 코드 작성 + 디자인패턴의 목적과 같음

좋은 아키텍처 패턴의 특징

• Distribution : 역할 분담
• Testability : 각 요소의 독립적 테스트
• Easy of Use

종류

• MVC (Model-View-Controller)
• MVP (Model-View-Presenter)
• MVVM (Model-View-ViewModel)
• MVI (Model-View-Intent)
• 기타

SOLID 원칙 (객체지향 설계 원칙)

1. Single Responsibilty Principle (SRP)
2. Open - Close Principle
3. Liskov Substitution Principle
4. Interface Segregation Principle
5. Dependency Inversion Property

=> 자세한 내용 포스팅 예정

작성자의 주절,,주절,,

• MVC패턴이 디자인 패턴인 줄로만 알고 있었으나 정보처리기사를 공부할 때 외웠던 생구행의 디자인 패턴 속에 없었던 것이 생각나 찾아보니 아키텍처 패턴의 챕터에서 나왔었다.
• 이러한 패턴 사용의 이유와 아키텍처 패턴과 디자인 패턴의 차이점에 대해 설명할 수 없었다.
• 역시 알고 있다고 생각했지만 머리속에서 정리되지 않았고, 이를 계기로 알고 있었던 개념에 대해 차근차근 정리해보려고 한다...

문제 링크

문제 설명

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.

예제 입력

문제 풀이

• 처음 문제 풀었는데 예제 2번이 계속 20이 나와서 돌아가는 순서를 출력해봤더니 후진을 못했다.
• 근데 후진을 못하는 줄 알았더니 그냥 후진하고 재귀를 안돌려서 그런 것이었다. !
• 문제 자체는 어려운 편은 아니었는데, 왼쪽 방향으로 돈다는 말이 헷갈렸다.

Solution

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, ans = 0;
    static String[][] map; // 방 정보 저장
    static int[] robot = new int[3]; // 좌표x,y ,방향
    static int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 북,동,남,서

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine().trim(), " ");
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        stk = new StringTokenizer(br.readLine().trim(), " ");
        for (int i = 0; i < 3; i++) {
            robot[i] = Integer.parseInt(stk.nextToken());
        }
        map = new String[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().split(" ");
        } // 입력

        run();
        System.out.println(ans);
    }

    static int dR, dC;

    public static void run() {
        if (map[robot[0]][robot[1]].equals("0")) { // 청소가 안된 곳이라면
            ans++;
            map[robot[0]][robot[1]] = "-1"; // 청소함으로 바꿔줌
        }

        for (int i = 0; i < 4; i++) {
            robot[2] = (robot[2] + 3) % 4; // -1해주면 인덱스 에러나니까 +3해줌
            dR = robot[0] + dir[robot[2]][0];
            dC = robot[1] + dir[robot[2]][1];
            if (map[dR][dC].equals("0")) { // 청소가 안된 곳이라면
                robot[0] = dR; // 이동
                robot[1] = dC; // 이동
                run();
                return;
            }
        } // 4방향 탐색 다함

        // 다 돌았는데도 청소할 곳이 없다면 뒤로 백
        dR = robot[0] + dir[(robot[2] + 2) % 4][0];
        dC = robot[1] + dir[(robot[2] + 2) % 4][1];
        if (!map[dR][dC].equals("1")) { // 벽이 아니면
            robot[0] = dR;
            robot[1] = dC;
            run();
            return;
        }
    }

}

문제 링크

문제 설명

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

문제 풀이

• dp에 해당 날에 얻을 수 있는 최대 수익을 넣는다.
• 날짜가 넘어가면 안되므로 n-1 인덱스부터 시작 (for문)
• i+T[i] => 해당 날짜와 소요되는 상담날이 N을 넘어가면 해당 날의 상담은 진행하지 못하니 dp[i]에 dp[i+1] 날의 값을 넣어준다.
• 넘어가지 않는다면 얻을 수 있는 최대 값을 dp[i]에 저장해준다.
• dp[i] = Math.max(DP[i+1], DP[i]+DP[i+T[i]])

Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] T = new int[n];
        int[] P = new int[n];
        int[] DP = new int[n+1];
        for(int i=0; i<n; i++) {
            T[i] = sc.nextInt();
            int p = sc.nextInt();
            P[i] = p;
            DP[i] = p;
        }

        for(int i=n-1; i>=0; i--) {
            if (i+T[i] > n) {
                DP[i] = DP[i+1];
            } else {
                DP[i] = Math.max(DP[i+1], DP[i]+DP[i+T[i]]);
            }
        }

        System.out.println(DP[0]);
    }
}

문제 링크

문제 설명

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

문제 풀이

• 이건 아주 불친절한 문제라고 생각했다 참내,,,, 그래도,, 이런 퀴즈같은 문제는 재밌으니까 계속 보게되긴 했다

• 가운데가 빈 삼각형이 기본형이고 저 기본형이 될때까지 쪼개야겠다 라고 생각했다

• 배열 크기는 N 입력받으면 char[N][[2*N-1]

• 삼각형의 꼭대기는 (0, N-1) 이고

• 사이즈가 3이 될때 까지 3개로 쪼개서 재귀 돌리자 ! 라고 생각함

Solution

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

// 별 찍기 - 11
public class Main {
    static char[][] stars;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        stars = new char[N][N * 2 - 1]; // 꼭대기 별이 (0,N-1)에 찍힘
        for (int i = 0; i < N; i++) {
            Arrays.fill(stars[i], ' '); // 공백으로 채움
        }

        star(0, N-1, N);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 2 * N - 1; j++) {
                sb.append(stars[i][j]);
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    public static void star(int r, int c, int N) {
        if (N == 3) { // k=0인 가장 작은 삼각형일 때 별찍기
            stars[r][c] = '*';
            stars[r + 1][c - 1] = stars[r + 1][c + 1] = '*';
            stars[r + 2][c - 2] = stars[r + 2][c - 1] = stars[r + 2][c] = stars[r + 2][c + 1] = stars[r + 2][c + 2] = '*';
            return;
        } else { // 큰 삼각형 세개로 다시 쪼갬
            int cut = N / 2;
            star(r, c, cut); // 제일 위에 삼각형
            star(r + cut, c - cut, cut); // 아래 왼쪽 삼각형
            star(r + cut, c + cut, cut); // 아래 오른쪽 삼각형
        }
    }
}

문제 링크

문제 설명

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

• *

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

문제 풀이

• 기본 네모 모양에서 123 456 789 로 숫자를 세면 항상 5자리가 비는걸 확인할 수 있다
• 이걸 큰 모양으로 보더라도 5자리가 비는 걸 활용해서 재귀를 짰다
• N이 들어면 9등분 해서 5번째 칸을 공백으로 만들고
• 나머지 칸도 1칸짜리가 될때까지 9등분 한다
• 1칸짜리가 되면 별찍음

Solution

import java.util.Scanner;

// 별 찍기 - 10
public class Main {
    static char[][] stars;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        stars = new char[N][N];
        star(0, 0, N, false);

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                sb.append(stars[i][j]);
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    public static void star(int r, int c, int size, boolean block) {
        if (block) { // 빈칸일 때
            for (int i = r; i < r + size; i++) {
                for (int j = c; j < c + size; j++) {
                    stars[i][j] = ' ';
                }
            }
            return;
        }

        if (size == 1) { // 한칸 되면 별찍기
            stars[r][c] = '*';
            return;
        }

        /*
         ***
         * * 
         ***
         인 경우 9칸으로 쪼개서 보면 다섯번째 칸은 공백 
         모든 큰 덩어리를 9칸로 쪼개서 보면 5번째 칸은 공백이다 
         그리고 한칸이 1이 될 때, 별찍으면 됨
         */
        int count = 0; // 5번째를 확인하는 변수
        int cut = size / 3; // 3등분 하는 수
        for (int i = r; i < r + size; i += cut) {
            for (int j = c; j < c + size; j += cut) {
                count++;
                if (count == 5) { // 빈칸일때
                    star(i, j, cut, true);
                } else { // 빈칸이 아닐때
                    star(i, j, cut, false);
                }
            }
        }

    }
}

문제 링크

문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

문제 풀이

• 어렸을때 하노이 탑 가지고 많이 놀았었는데, 점화식을 구해야할 줄이야,,,

• 하노이탑 옮긴 횟수 구하기

  • 1번 기둥에서 3번 기둥으로 N개를 옮기려면 2번 기둥에 N-1번까지의 기둥을 옮겨놓고 3번기둥에 N을 옮긴다.
  • 그리고 3번 기둥에 N-1개를 다시 옮기면 N-1개를 옮기는 작업이 똑같이 2번 수행되므로
  • $a_{n+1} = 2 \times a_n + 1$
  • $a_{n+1} + 1 = 2 \times (a_n + 1)$
  • $b_n = a_n +1$ 이라 가정 했을 때, $b_{n+1} = 2 \times b_n$
  • 이 때 $b_n$은 첫째항이 $b_1 = a_1 + 1 = 2$ 이고 공비가 2 인 등비수열이다
  • $a_1 = 1$ 이니 $a_n$ 은 초항이 1이고 공비가 2인 등비수열 => $a_n = 2^n -1$

• 하노이 탑 이동시키기

  • 1번에서 3번으로 이동시키려면 N-1 개를 2에 옮겨두고
  • N 원반을 3에 옮긴다
  • 다시 N-1개의 하노이 탑을 2에서 3으로 옮긴다를 반복
  • N이 1일 때 (작은 탑이 완성될때마다) return;

• 하노이 탑은 재귀문제 기본이라고 한다.. 그래서 나무위키에 아주 친절하게 설명되어 있음

• 나는 몰라서 되게 헤맸지만,,,

Solution

import java.util.Scanner;

// 하노이 탑 이동 순서
public class Main {
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // 메르센 수 2^n - 1
        sb.append((int) (Math.pow(2, N) -1)).append('\n');
        Hanoi(N, 1,2,3);

        System.out.println(sb);

    }

    public static void Hanoi(int N, int from, int by, int dest) {
        // 작은 탑이 완성 되면 return
        if(N==1) {
            sb.append(from).append(" ").append(dest).append('\n');
            return;
        }

        // 1 에서 3으로 옮겨야 할 때
        // N-1개를 2에 옮긴다
        Hanoi(N-1, from, dest, by);
        // N원반을 1에서 3으로 옮긴다
        sb.append(from).append(" ").append(dest).append('\n');
        // 다시 N-1개를 2에서 3으로 옮긴다
        Hanoi(N-1, by, from, dest);
    }
}

문제 링크

문제 설명

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

문제 풀이

• 0,1,2 를 카운트할 배열 생성
• 종이의 숫자가 모두 같은지 확인 후 같으면 배열값 ++
• 다르면 9개로 자른다

Solution

import java.util.Scanner;

// 종이의 개수
public class Main {
    static int[][] paper;
    static int N;
    static int[] ans = new int[3]; // -1(+1해서 0인덱스), 0(+1해서 1인덱스), 1(+1헤서 2인덱스)

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        paper = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                paper[i][j] = sc.nextInt();
            }
        } // 입력

        papercut(1, N+1, 1, N+1);

        System.out.println(ans[0]);
        System.out.println(ans[1]);
        System.out.println(ans[2]);

    }

    public static void papercut(int rStart, int rEnd, int cStart, int cEnd) {
        // 종이가 모두 같은 수가 아니면 9개로 쪼갬
        if (!checkSameNumber(rStart, rEnd, cStart, cEnd)) {
            int cut = (rEnd - rStart) / 3; // 3등분할 숫자
            for (int i = rStart; i < rEnd; i += cut) {
                for (int j = cStart; j < cEnd; j += cut) {
                    papercut(i, i + cut, j, j + cut); // 9개로 나눈다
                }
            }
        }
        // 종이가 모두 같은 수로 되어 있으면 ans++ return
        else {
            ans[paper[rStart][cStart] + 1]++; // -1(+1해서 0인덱스), 0(+1해서 1인덱스), 1(+1헤서 2인덱스)
            return;
        }
    }

    public static boolean checkSameNumber(int rStart, int rEnd, int cStart, int cEnd) {
        int num = paper[rStart][cStart]; // 처음 시작 숫자와
        for (int i = rStart; i < rEnd; i++) {
            for (int j = cStart; j < cEnd; j++) {
                if (num != paper[i][j]) // 다른 숫자가 나오면
                    return false; // false 반환
            }
        }
        return true;
    }
}

문제 링크

[16194. 카드 구매하기 2] (https://www.acmicpc.net/problem/16194) 문제랑 완전히 똑같다 ! 최대값 최소값만 달라서 이거 풀면 2도 제출 삽가능 ~

문제 설명

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

문제 풀이

• 이 문제를 고민하면서 디피를 제일 이해하게 됐달까?
• dp 는 dp 배열에 값을 저장하면서 그 값을 활용해야 한다
• card 배열에는 각 카드 가격을 저장
• dp 배열에는 각 카드의 개수를 살 때의 최대값을 저장한다
• 1장을 살때는 1장의 카드팩을 고르는 것이 최대값이므로 dp[1] = card[1]
• dp[2] 부터는 여러 장을 합쳐서 사는 것이 비싼지, N개의 카드팩을 사는게 비싼지를 비교하여 저장한다

Solution

import java.util.Scanner;

// 카드 구매하기
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] card = new int[N + 1]; // N개의 카드팩 가격
        for (int i = 1; i < N + 1; i++) {
            card[i] = sc.nextInt();
        } // 입력

        int[] dp = new int[N + 1]; // N개를 고르는 가장 비싼 가격 저장
        dp[1] = card[1]; // 카드 한장을 고르는 가장 비싼 가격은 card[1]을 고르는 것

        for (int i = 2; i < N + 1; i++) {
            int tempMax = 0;
            for (int a = 1; a < i; a++) {
                    tempMax = Math.max(tempMax, dp[a] + dp[i-a]);
            }
            dp[i] = Math.max(tempMax, card[i]); // dp[i]는 여러개를 합해서 사는게 비싼지, N개의 카드팩을 사는게 비싼지
        }

        System.out.println(dp[N]);

    }

}