is-A 관계

is-A는 “A는 B의 한 종류다” 라고 말할 수 있는 관계이다.
주로 상속에서 사용된다.

예시:

• 강아지는 동물이다.
• 자동차는 탈것이다.

class Dog extends Animal {
}

has-A 관계

has-A는 “A는 B를 가지고 있다” 라고 말할 수 있는 관계이다.
주로 객체를 필드로 포함할 때 사용된다.

예시:

• 자동차는 엔진을 가지고 있다.
• 컴퓨터는 CPU를 가지고 있다.

class Car {
    private Engine engine;
}

인터페이스 vs 추상클래스

추상클래스

추상모 클래스*이다.
is-A 관계가 자연스러울 클래스는 *공통 속성과 기능을 물려주기 위한 부때 사용한다.

abstract class Animal {
    void eat() {
        System.out.println("먹는다");
    }

    abstract void sound();
}

인터페이스

인터페이스는 반드시 구현해야 할 기능 규칙을 정하는 것이다.
can-do 관계, 즉 “~할 수 있다” 가 자연스러울 때 사용한다.

interface Flyable {
    void fly();
}

1. 문제요약

N일 동안 사용할 금액이 주어질 때, 매번 같은 금액 K만 인출해서 생활한다.
돈이 부족하면 다시 K원을 인출하며, 필요하면 일부러 인출 횟수를 늘려 정확히 M번도 맞출 수 있다.

따라서 구해야 하는 값은
최소 필요 인출 횟수가 M 이하가 되는 최소 K 이다.

2. 알고리즘

이 문제는 K를 기준으로 하는 이분탐색 문제다.

2.1 핵심상태

• 탐색값: 인출 금액 K
• 판별: K로 생활할 때 최소 인출 횟수가 M 이하인가

2.2 핵심과정

• lo는 하루 사용 금액의 최댓값
• hi는 전체 사용 금액의 합
• mid를 K 후보로 두고 인출 횟수를 계산
• 횟수가 M 이하이면 더 작은 K 탐색
• 횟수가 M 초과이면 K를 더 키움

2.3 핵심 규칙

• K는 하루 사용 금액보다 작을 수 없다
• K가 커질수록 인출 횟수는 줄어든다
• 최소 필요 인출 횟수 <= M 이면 가능한 K다
• 따라서 가능한 최소 K 를 찾으면 된다

3. 코드

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

public class Main {
    static int N, M, REMAIN;
    static int [] MONEY;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        MONEY = new int[N];

        int lo=0;
        int hi=0;
        for(int i = 0; i < N; i++){
            MONEY[i] = Integer.parseInt(br.readLine());
            hi += MONEY[i];
            lo = Math.max(lo, MONEY[i]);
        }

        REMAIN = 10000;
        System.out.println(binarySearch(lo, hi));
    }

    static int binarySearch(int lo, int hi) {

        int mid;
        while (lo < hi) {
            mid = (lo + hi) / 2;
            if (canTakeOut(mid)) hi = mid; 
            else lo = mid + 1;
        }
        return lo;
    }

    static boolean canTakeOut(int standard) {
        int takeOutCnt = 1;
        int remain = standard;
        for(int money : MONEY) {
            if(money > standard) return false;
            if(money > remain) {
                takeOutCnt ++;
                remain = standard - money;
            }
            else {
                remain -= money;
            }
        }

        return takeOutCnt <= M;
    }
}

1. 문제요약

• 블로그 총 기간 N, 특정 기간 X가 주어짐
• X일동안 최대 접속자 수 구하기

2. 알고리즘

2.1 누적합으로 풀기.

1. prefix 배열 생성 (N+1)
2. prefix[i] = prefix[i-1] + 입력값
3. for (end = X end = X ~ N; end++)
4. sum = prefix[end] - prefix[end-X]

import java.io.*;
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 X = Integer.parseInt(st.nextToken());

        int[] prefix = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            prefix[i] = prefix[i - 1] + Integer.parseInt(st.nextToken());
        }

        int max = 0;
        int cnt = 0;

        for (int end = X; end <= N; end++) {
            int sum = prefix[end] - prefix[end - X];

            if (sum > max) {
                max = sum;
                cnt = 1;
            } else if (sum == max) {
                cnt++;
            }
        }

        System.out.println(max == 0 ? "SAD" : max+"\n"+cnt);
    }
}

2.2 슬라이딩 윈도우로 풀기

1. 처음 X개 합을 먼저 구해서 windowSum 초기화
2. max = windowSum, cnt = 1로 시작
3. for (right = X ~ N-1)
4. windowSum += arr[right]
5. windowSum -= arr[right-X]

import java.io.*;
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 X = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int windowSum = 0;
        for (int i = 0; i < X; i++) {
            windowSum += arr[i];
        }

        int max = windowSum;
        int cnt = 1;

        for (int right = X; right < N; right++) {
            windowSum += arr[right];
            windowSum -= arr[right - X];

            if (windowSum > max) {
                max = windowSum;
                cnt = 1;
            } else if (windowSum == max) {
                cnt++;
            }
        }

         System.out.println(max == 0 ? "SAD" : max+"\n"+cnt);
    }
}

두 알고리즘 차이!

누적합

• 전체 누적합 배열을 만든 뒤
• 구간합을 prefix[end] - prefix[start-1]로 계산

슬라이딩 윈도우

• 첫 구간합을 먼저 만든 뒤
• 다음 구간합은 이전 합에서 앞값을 빼고 뒷값을 더해 갱신

고정 길이 구간 문제에서는 슬라이딩 윈도우가 더 직관적이다.

1. 문제요약

• 1×1, 2×2, 3×3, 4×4, 5×5 색종이가 총 5개씩 있다.
• 10×10 색종이를 위 5종류의 색종이로 채워야한다.
  • 각 칸에는 0,1이 적혀있다.
  • 1에는 색종이로 가려야 하고, 0은 가려선 안된다.
• 겹치면 안된다.

2. 입출력

출력

불가능한 경우 -1 출력

3. 알고리즘

• 핵심 상태
  • paper[][] : 현재 남아있는 1 영역
  • remain [] : 색종이 남은 개수
  • answer : 최소 사용 개수
• 진행 방식
  • dfs 함수 내에서, 이중 for문으로 행,열 처음부터 보며 1 찾음
    • 1 찾으면 즉시 중단 및 1 찾았다는 boolean 변수 true로 변경
  • 1 찾은 위치에 대해 5×5 ~ 1×1 색종이를 모두 시도
    • 붙일 수 있다면 다음 재귀로 이동(인자는 현재까지 계산된 색종이의 총 합)
• 핵심 규칙
  • 붙일 때 해당 영역 0으로 변경
  • 재귀 후 다시 1로 복귀
  • 색종이 개수도 다시 복구
  • used >= answer 면 가지치기로 재귀 탐색 x
• 이동 처리
  • 매 DFS마다 왼쪽 위부터 첫 번째 1 탐색
  • (r,c)에서 size×size 범위 검사
• 종료 조건
  • 더 이상 1이 없으면 정답 갱신
• 시간복잡도
  • 완전탐색 + 백트래킹
  • 가지치기로 줄임

4. 코드

public class Main {
    static int[][] PAPER;
    static int[] TYPE_CNT = {0, 5, 5, 5, 5, 5};
    static int ANSWER;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PAPER = new int[10][10];
        ANSWER = Integer.MAX_VALUE;

        for (int i = 0; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                PAPER[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0);

        System.out.println(ANSWER == Integer.MAX_VALUE ? -1 : ANSWER);
    }

    static void dfs(int used) {
        if (used >= ANSWER) {
            return;
        }

        boolean found = false;
        int r = 0;
        int c = 0;
        for (r = 0; r < 10; r++) {
            for (c = 0; c < 10; c++) {
                if (PAPER[r][c] == 1) {
                    found = true;
                    break;
                }
            }
            if (found) {
                break;
            }
        }

        if (!found) {
            ANSWER = Math.min(ANSWER, used);
            return;
        }

        for (int size = 1; size <= 5; size++) {
            if (!canGo(r,c,size))
                continue;
            attach(r, c, size, 0);
            TYPE_CNT[size]--;
            dfs(used + 1);
            attach(r, c, size, 1);
            TYPE_CNT[size]++;
        }
    }

    static boolean canGo(int r, int c, int size) {
        if (r + size > 10 || c + size > 10 || TYPE_CNT[size] == 0) {
            return false;
        }

        for (int nr = r; nr < r + size; nr++) {
            for (int nc = c; nc < c + size; nc++) {
                if (PAPER[nr][nc] == 0) {
                    return false;
                }
            }
        }

        return true;
    }

    static void attach(int r, int c, int size, int value) {
        for (int nr = r; nr < r + size; nr++) {
            for (int nc = c; nc < c + size; nc++) {
                PAPER[nr][nc] = value;
            }
        }
    }
}

1. 문제요약

• 1×1, 2×2, 3×3, 4×4, 5×5 색종이가 총 5개씩 있다.
• 10×10 색종이를 위 5종류의 색종이로 채워야한다.
  • 각 칸에는 0,1이 적혀있다.
  • 1에는 색종이로 가려야 하고, 0은 가려선 안된다.
• 겹치면 안된다.

2. 입출력

출력

불가능한 경우 -1 출력

3. 알고리즘

• 핵심 상태
  • paper[][] : 현재 남아있는 1 영역
  • remain [] : 색종이 남은 개수
  • answer : 최소 사용 개수
• 진행 방식
  • dfs 함수 내에서, 이중 for문으로 행,열 처음부터 보며 1 찾음
    • 1 찾으면 즉시 중단 및 1 찾았다는 boolean 변수 true로 변경
  • 1 찾은 위치에 대해 5×5 ~ 1×1 색종이를 모두 시도
    • 붙일 수 있다면 다음 재귀로 이동(인자는 현재까지 계산된 색종이의 총 합)
• 핵심 규칙
  • 붙일 때 해당 영역 0으로 변경
  • 재귀 후 다시 1로 복귀
  • 색종이 개수도 다시 복구
  • used >= answer 면 가지치기로 재귀 탐색 x
• 이동 처리
  • 매 DFS마다 왼쪽 위부터 첫 번째 1 탐색
  • (r,c)에서 size×size 범위 검사
• 종료 조건
  • 더 이상 1이 없으면 정답 갱신
• 시간복잡도
  • 완전탐색 + 백트래킹
  • 가지치기로 줄임

4. 코드

public class Main {
    static int[][] PAPER;
    static int[] TYPE_CNT = {0, 5, 5, 5, 5, 5};
    static int ANSWER;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PAPER = new int[10][10];
        ANSWER = Integer.MAX_VALUE;

        for (int i = 0; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                PAPER[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0);

        System.out.println(ANSWER == Integer.MAX_VALUE ? -1 : ANSWER);
    }

    static void dfs(int used) {
        if (used >= ANSWER) {
            return;
        }

        boolean found = false;
        int r = 0;
        int c = 0;
        for (r = 0; r < 10; r++) {
            for (c = 0; c < 10; c++) {
                if (PAPER[r][c] == 1) {
                    found = true;
                    break;
                }
            }
            if (found) {
                break;
            }
        }

        if (!found) {
            ANSWER = Math.min(ANSWER, used);
            return;
        }

        for (int size = 1; size <= 5; size++) {
            if (!canGo(r,c,size))
                continue;
            attach(r, c, size, 0);
            TYPE_CNT[size]--;
            dfs(used + 1);
            attach(r, c, size, 1);
            TYPE_CNT[size]++;
        }
    }

    static boolean canGo(int r, int c, int size) {
        if (r + size > 10 || c + size > 10 || TYPE_CNT[size] == 0) {
            return false;
        }

        for (int nr = r; nr < r + size; nr++) {
            for (int nc = c; nc < c + size; nc++) {
                if (PAPER[nr][nc] == 0) {
                    return false;
                }
            }
        }

        return true;
    }

    static void attach(int r, int c, int size, int value) {
        for (int nr = r; nr < r + size; nr++) {
            for (int nc = c; nc < c + size; nc++) {
                PAPER[nr][nc] = value;
            }
        }
    }
}

1. 문제요약

1. 사진틀은 비어있다.
2. 특정 학생 추천 시, 등록된다.
3. 사진틀이 비어있지 않다면 가장 추천횟수가 적은 학생을 삭제한다.
   • 추천횟수가 같다면 가장 오래된 사진을 삭제한다.
   • 삭제된 학생의 추천 수는 0이 된다.
4. 이미 있는 학생이 추천받으면 추천 수가 오른다.

2. 입출력

[입력]

• 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20)
• 총 추천횟수 (1000 이하)
• 추천된 학생의 번호

3. 알고리즘

• pq를 이용하는 문제

4. 코드

오랜만에 Map을 쓰니 좀 헷갈렸다. Map 복습용 문제!

class Info implements Comparable<Info> {
    int num;
    int great;
    int order;

    public Info(int num, int great, int order) {
        this.num=num;
        this.great=great;
        this.order=order;
    }

    @Override
    public int compareTo(Info o){
        if(this.great == o.great)
            return this.order - o.order;
        return this.great - o.great;
    }

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

        int N = Integer.parseInt(br.readLine());
        int greatCnt = Integer.parseInt(br.readLine());

        //번호, 자료구조
        Map<Integer, Info> list = new HashMap<>();

        st = new StringTokenizer(br.readLine());
        int order = 0;
        while (greatCnt --> 0) {
            int now = Integer.parseInt(st.nextToken());
            order++;
            if(list.containsKey(now))
            {
                list.get(now).great++;
                continue;
            }
            if(list.size() >= N && !list.containsKey(now)) {
                Info out = findOut(list);
                list.remove(out.num);
            }
            list.put(now, new Info(now,1, order));
        }

        List<Integer> keys = new ArrayList<>(list.keySet());
        Collections.sort(keys);

        StringBuilder sb = new StringBuilder();
        for (int key : keys) {
            sb.append(key).append(" ");
        }
        System.out.println(sb);
    }

    static Info findOut(Map<Integer, Info> list){
        PriorityQueue<Info> queue = new PriorityQueue<>();

        for(Info value : list.values()){
            queue.add(value);
        }

        return queue.poll();
    }
}

1. 문제 요약

• 3가지 연산 기호 +, -, *의 우선순위를 다르게 설정하여 계산
• 주어진 수식에서 만들 수 있는 결과값의 절댓값 중 최댓값을 구하는 문제
• 계산 과정에서 음수 결과가 발생할 수 있으므로 - 연산자와 음수 값의 구분이 필요
• 연산자 우선순위는 총 3! = 6가지 조합이 존재하므로 모든 경우를 확인해야 함.

2. 입출력

입력

• expression
  • 숫자와 연산자(+, -, *)로 이루어진 문자열
  • 길이: 3 이상 100 이하
• 계산 중 값이 커질 수 있으므로 long 타입 사용

출력

• 주어진 식에서 연산자 우선순위를 적절히 설정했을 때 얻을 수 있는 결과값의 절댓값 중 최댓값 반환

3. 알고리즘

1. 수식 파싱

• StringTokenizer를 이용하여 수식을 숫자 리스트(nums)와 연산자 리스트(ops)로 분리한다.

• 예시
  100-200*300-500+20

  nums = [100, 200, 300, 500, 20]
  ops = ['-', '*', '-', '+']

2. 연산자 우선순위 경우의 수 생성

• 가능한 연산자는 +, -, * 총 3개
• 모든 우선순위 경우는 3! = 6가지
• permute()를 사용하여 연산자 우선순위 순열 생성

3. 우선순위에 따른 계산

• 각 우선순위마다 evaluate() 실행
• 연산자 우선순위 순서대로 식을 계산하면서 리스트를 줄여나감

[예시]

초기 상태 * nums = [100, 200, 300, 500, 20]
ops = ['-', '', '-', '+']

우선순위가 * 먼저일 경우

• ops[1] = *;
• nums[1]과 nums[2]가 피연산자!
  즉 200 * 300 = 60000 의 새로운 결과 도출됨

• 리스트 갱신*
  1) 60000의 결과값을 현재 nums[i] 에 넣음 (i=1)
  • nums = [100, 60000, 300, 500, 20]

    nums.set(i, 60000);

    2) 쓰인 피연산자 300을 nums에서 삭제해줌

    nums.remove(i + 1);

    3) 쓰인 연산자 *을 ops에서 삭제해줌

     - ops  = ['-', '-', '+']

    ops.remove(i);

    ---

    이 과정을 우선순위 순서대로 반복

4. 최대 절댓값 갱신

• 모든 계산이 끝나면 결과는 nums[0]
• 결과의 절댓값을 계산하여 최대값 갱신

best = max(best, abs(result))

5. 최종 결과 반환

• 모든 우선순위(6가지)를 검사한 후
• 가장 큰 절댓값 반환

4. 코드

import java.util.*;

class Solution {
    private static final char[] OPS = {'+', '-', '*'};
    private static boolean[] used;
    private static long best;

    public long solution(String expression) {
        List<Long> nums = new ArrayList<>();
        List<Character> ops = new ArrayList<>();
        used = new boolean[3];

        parse(expression, nums, ops);
        permute(0, new char[3], nums, ops);

        return best;
    }

    private static void parse(String expr, List<Long> nums, List<Character> ops) {
        StringTokenizer st = new StringTokenizer(expr, "+-*", true);

        while (st.hasMoreTokens()) {
            String token = st.nextToken();

            if (token.equals("+") || token.equals("-") || token.equals("*")) {
                ops.add(token.charAt(0));
            } else {
                nums.add(Long.parseLong(token));
            }
        }
    }

    private static void permute(int depth, char[] order, List<Long> baseNums, List<Character> baseOps) {
        if (depth == 3) {
            long val = evaluate(order, baseNums, baseOps);
            best = Math.max(best, Math.abs(val));
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (used[i]) continue;
            used[i] = true;
            order[depth] = OPS[i];
            permute(depth + 1, order, baseNums, baseOps);
            used[i] = false;
        }
    }

    private static long evaluate(char[] order, List<Long> baseNums, List<Character> baseOps) {
        // ⭐복사본에서 작업
        List<Long> nums = new ArrayList<>(baseNums);
        List<Character> ops = new ArrayList<>(baseOps);

        for (char target : order) {
            for (int i = 0; i < ops.size(); ) {
                if (ops.get(i) == target) {
                    long a = nums.get(i);
                    long b = nums.get(i + 1);
                    long r = calc(a, b, target);

                    nums.set(i, r);
                    nums.remove(i + 1);
                    ops.remove(i);
                } else {
                    i++;
                }
            }
        }
        return nums.get(0);
    }

    private static long calc(long a, long b, char op) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        return a * b;
    }
}

1. 문제 요약

• 각 재료마다 쓴 맛과 신 맛이 주어진다.
• 주어진 재료들을 적당히 섞어 쓴 맛과 신 맛의 차이를 최소로 줄이고자 한다.
  • 신 맛은 사용된 재료들의 총곱 / 쓴 맛은 사용된 재료들의 총합
• 재료는 1개 이상 무조건 사용한다.

2. 입출력

[입력]

• 재료의 개수 N(1 ≤ N ≤ 10)
• 1,000,000,000보다 작은 양의 정수

[출력]

• 신맛과 쓴맛의 가장 최소 차이를 출력하라.

3. 알고리즘

• 조합 문제
• 자료의 개수가 10개. boolean 대신 비트마스킹을 써서 표시해보기
• Long형 써야 함

4. 코드

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

public class Main {
    static int N;
    static int [][] TASTE;
    static long ANSWER;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        TASTE = new int[N][2];

        for(int i=0; i<N; i++){
            TASTE[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(s -> Integer.parseInt(s))
                    .toArray();
        }

        ANSWER = Long.MAX_VALUE;
        johap(0, 0, 1, 0);

        System.out.println(ANSWER);
    }

    static void johap (int start, int visit, long sour, long bitter) {
        if(start == N)
            return;

        for(int i = start; i<N; i++){
            if ((visit & (1 << i)) != 0) continue;
            visit |= (1<<i);
            long ns = sour * TASTE[i][0];
            long nb = bitter + TASTE[i][1];
            long newTaste = Math.abs(ns - nb);
            ANSWER = Math.min(ANSWER, newTaste);
            johap(i + 1, visit, sour * TASTE[i][0], bitter + TASTE[i][1]);
            visit &= ~(1<<i);
        }
    }
}

5. 알게된 점

사실 비트마스킹을 연습해보고자 푼 문제다.

비트마스킹으로 현재 방문했는지 확인하는 조건문

if ((visit & (1 << i)) != 0) {
    continue;
}

비트마스킹으로 i번째 방문체크

 visit |= (1<<i);

visit의 초기값은 0에서 시작한다.

비트마스킹으로 i번째 방문해제

visit &= ~(1<<i);

1. 문제 요약

• 각 줄마다 k와 k개의 수가 주어짐. 해당 주어진 수들 중 6개의 수를 선택하는 경우의 수를 모두 출력할것
• 각 케이스마다 경우의 수는 오름차순으로 출력하고, 케이스간 한 줄씩 띄어쓰기로 출력한다.

2. 알고리즘

해당 문제는 조합론 공부를 위해 풀어보았다.

이 문제의 중요점은 다음과 같다.

• 한 번 선택된 번호는 다시 뽑을 수 없다.
• 6개의 번호만을 뽑아야 한다.

처음에는 아무생각없이 순열 만드듯이 하다가 틀렸다는 걸 깨달았다.

3. 코드

어렵지 않으니 까먹을 때 마다 자주봐두자

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

public class Main {
    static int K;
    static int[] ARR;

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

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            if (K == 0) break;

            ARR = new int[K];
            for (int i = 0; i < K; i++) ARR[i] = Integer.parseInt(st.nextToken());
            Arrays.sort(ARR);

            johap(0, 0, new StringBuilder());
            System.out.println();
        }
    }

    static void johap(int start, int depth, StringBuilder sb) {
        if (depth == 6) {
            System.out.println(sb.toString().trim());
            return;
        }

        for (int i = start; i < K; i++) {
            int len = sb.length();
            sb.append(ARR[i]).append(' ');
            johap(i + 1, depth + 1, sb);
            sb.setLength(len); // 백트래킹(원복)
        }
    }
}

4. 알아둬야 할 점

sb.setLength(len); // 백트래킹(원복)

StringBuilder는 자주 쓰니까, 해당 함수 정도는 기억해두자!

1. 문제 요약

• 서로 다른 포트를 연결하고자 한다.
• 이떄 포트간 선이 겹치지 않게 놓을 수 있는 최대 갯수를 구하라.

2. 입출력

[입력]

• n개의 정수(1 ≤ n ≤ 40,000)
• 차례로 1번 포트부터, n개까지 연결되어야 하는 반대쪽 포트 번호가 주어진다.

[출력]

• 포트 선이 겹치지 않게 최대 연결 개수를 출력한다.

3. 알고리즘

• 특정 조건을 만족하는 최대의 개수 구하기 (=LIS)
• 개수가 무려 40,000이므로, 일반적인 LIS O(n^2)가 아닌, 이분탐색을 활용한 O(LogN2)로 풀어야 한다.

4. 코드

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;

        int n = Integer.parseInt(br.readLine());
        int[] binary = new int[n];

        st = new StringTokenizer(br.readLine());
        int len = 0;
        for (int i = 0; i < n; i++) {
            int value = Integer.parseInt(st.nextToken());

            // lower_bound
            int l = 0, r = len;
            while (l < r) {
                int m = (l + r) >>> 1;
                if(binary[m] >= value)
                    r = m;
                else
                    l = m + 1;
            }
            binary[l] = value;
            if (l == len) len++; //⭐핵심코드!!⭐
        }

        System.out.println(len);
    }
}

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.

예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이 됩니다. { 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 입니다.

일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 간편한 방법은 DP를 이용하는 것입니다.

아래에서 length[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미합니다.

for (int i = 0; i < n; i++){
    length[i] = 1;
    for (int k = 0; k < i; k++){
        if (arr[k] < arr[i]){
            length[i] = max(length[i], length[k] + 1);
        }
    }
}

주어진 배열에서 인덱스를 하나씩(i+1) 늘려가면서 확인합니다. 그리고 내부 반복문으로 i보다 작은 인덱스들을 하나씩 살펴보면서 arr[k] < arr[i]인 것이 있을 경우, length[i]를 업데이트합니다.

업데이트하는 기준은,

• (1) k번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[i]를 추가했을 때의 LIS 길이와
• (2) 추가하지 않고 기존의 length[i] 값

둘 중에 더 큰 값으로 length[i] 값을 업데이트합니다.

LIS 최적화 방법

위와 같은 방식으로 진행할 시, 시간복잡도는 O(N^2)에 도달합니다.

이런 느린 알고리즘을 최적화 하는 방법은 이분탐색을 활용하는 것 입니다.

시간복잡도를 O(nlog n)으로 줄일 수 있습니다.

관련 문제

- 반도체 설계(b_2352)

참고 블로그

LIS란?

1. 문제 요약

• 상자의 크기가 일렬로 주어지고, 앞 상자(바로 앞x)가 현재 상자보다 작으면, 현재 상자에 넣을 수 있다.
• 한 번에 넣을 수 있는 최대 상자 개수?

2. 입출력

입력

• 상자의 개수 (1 ≤ n ≤ 1000)

출력

넣을 수 있는 최대의 상자 개수

3. 알고리즘

• 그리디 아닌 이유 -> 현재 상자를 뒤에 등장할 상자에 넣을 수 있는지 없는지 현재 시점에서 알 수 없음.
• DP 문제

그 중에서도 LIS(최장 증가 부분 수열) 문제임

1. 문제 요약

• 정수가 적힌 숫자 카드가 있다.
• 상근이는 여러 장의 카드를 가지고 있다. (같은 숫자의 카드가 여러 장 있을 수 있음)
• 특정 숫자가 적힌 카드를 몇 장 가지고 있는지 구하는 문제이다.

2. 입출력

입력

① 상근이가 가진 카드 정보

• 카드 개수 N (1 ≤ N ≤ 500,000)
• 각 카드에 적힌 정수
  (-10,000,000 ≤ 숫자 ≤ 10,000,000)

② 확인해야 할 카드 정보

• 알고 싶은 카드 개수 M
• 확인할 카드에 적힌 정수
  (-10,000,000 ≤ 숫자 ≤ 10,000,000)

출력

• 입력으로 주어진 각 숫자 카드에 대해
  상근이가 몇 장 가지고 있는지 공백으로 구분하여 출력한다.

3. 첫 번째 구현 방법

접근 방식

1. 카드 배열을 정렬한다.
2. 이분 탐색으로 특정 숫자를 찾는다.
3. 찾은 위치에서 왼쪽/오른쪽으로 확장하며 같은 숫자의 개수를 센다.

문제점

이 방식은 최악의 경우 시간 초과가 발생할 수 있다.

이분 탐색 자체는 O(log N)이지만,

• 같은 숫자가 많을 경우 왼쪽으로 최대 N/2
• 오른쪽으로 최대 N/2

까지 탐색해야 한다.

즉, 한 번의 질의에 최대 O(N)이 걸릴 수 있다.

*만약 카드의 개수가 최대치라면? *

• 카드 하나를 찾는 데 걸리는 최악 시간: O(N)
• 질의가 M개일 때: O(N × M)

N, M이 최대 500,000일 경우 500,000 × 500,000 = 250,000,000,000

사실상 O(N²) 수준이 되어 시간 초과가 발생한다.

4. 정답 구현 방법

핵심 아이디어

정렬된 배열에서 특정 값 x의 개수는 다음처럼 구할 수 있다.

• lower_bound(x) : x가 처음 등장하는 위치
• upper_bound(x) : x보다 큰 값이 처음 등장하는 위치

따라서 x의 등장 횟수는

count(x) = upper_bound(x) - lower_bound(x)

이분탐색 upper bound / lower bound 찾기

둘 다 구조가 동일하다. 하지만 lower의 경우, 찾는 범위가 =에 포함되어야 하고, upper은 포함되지 않는다는 것이 다르다.

[lower bound]

: lower의 경우, 현재 타겟과 같은 값을 찾았다면 그건 정답일 가능성이 있다. => 그렇기에 인덱스를 옮기지 않고 hi만 내린다.

int lo = 0;
int hi = N;

while( lo < hi ) {
  int mid = (lo + hi) / 2;
  if ( value [mid] <= target )
    hi = mid;
 else 
    lo = mid + 1;
}
return lo;

[upper bound]

: upper의 경우, 현재 값이 찾는 값과 같다면, 범위에서 벗어나는 것이다. (upper은 찾는 수가 처음으로 초과되는 인덱스를 찾는다.) => 그렇기에 같은 경우는 밑의 케이스은 mid + 1을 통해 lo를 올린다.

int lo = 0;
int hi = N;

while( lo < hi ) {
  int mid = (lo + hi) / 2;
  if ( value [mid] < target ) 
    hi = mid;
 else 
    lo = mid + 1;
}
return lo;

5. 정답 코드

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

public class Main {
    static int N;
    static int[] number;

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

        N = Integer.parseInt(br.readLine());
        number = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            number[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(number);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int x = Integer.parseInt(st.nextToken());
            sb.append(upperBound(x) - lowerBound(x));
            if (i < M - 1) {
                sb.append(" ");
            }
        }

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

    static int lowerBound(int target) {
        int lo = 0;
        int hi = N;

        while (lo < hi) {
            int mid = (hi + lo) / 2;
            if (number[mid] >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    static int upperBound(int target) {
        int lo = 0;
        int hi = N;

        while (lo < hi) {
            int mid = (hi + lo) / 2;
            if (number[mid] > target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

1. 문제요약

• n개의 트럭이 다리를 건너려고 한다.
• 1초에 1씩 움직인다는 가정. 다리에 올라간 트럭 무게 총 합 <= L
• 트럭길이는 모두 1로 돋일
• 땅과 걸쳐져있는 트럭은 무게에 합하지 않음(자리 차지만)
• 모든 트럭이 건너는 최단 시간 구하기

2. 입력

• n개의 트럭 무게
• 다리길이 w
• 다리하중 L

3. 알고리즘 - 그리디

• 다리길이만큼 어레이리스트를 만듦
• 큐에 트럭 무게, 끝을 나타내는 boolean 변수 담은 클래스 넣음
• 큐에 w만큼 0을 넣음. (빈 칸이라는 의미)

4. 내 코드

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

class Info {
    int weight;
    boolean end;

    public Info(int weight, boolean end){
        this.weight = weight;
        this.end = end;
    }
}

public class Main {
    static Queue<Info> bridge;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n,w,l;

        n = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());

        bridge = new ArrayDeque<>();
        Queue<Info> truck = new ArrayDeque<>();

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            int weight = Integer.parseInt(st.nextToken());
            boolean end = i==n-1;
            truck.add(new Info(weight, end));
        }

        for(int i=0; i<w; i++){
            bridge.add(new Info(0, false));
        }

        Info nowTruck = bridge.peek();
        int time = 0;
        while (!nowTruck.end) {
            time++;
            bridge.poll();
            int nowBridgeWeight = calculateBridgeSum();
            if(!truck.isEmpty() && truck.peek().weight  + nowBridgeWeight <= l)
                bridge.add(truck.poll());
            else
                bridge.add(new Info(0,false));
            nowTruck = bridge.peek();
        }

        System.out.println(time+1);
    }

    static int calculateBridgeSum() {
        int sum = 0;
        for(Info truck : bridge) {
            sum += truck.weight;
        }
        return sum;
    }

}

5. 알게 된 점

문제를 풀면서 궁금했던 점이 있다.

바로 두 가지 변수가 들어있는 클래스에 대한 List를 Stream으로 간편하게 계산할 수 있을까? 였다.

되긴 한다!!

            int nowBridgeWeight = bridge.stream()
                    .mapToInt(info -> info.weight)
                    .sum();

그러나 스트림으로 사용할 경우, for문보다 많이 느린 것을 확인할 수 있었다.

스트림은 다음과 같은 과정을 거친다.

Collection → Spliterator → Pipeline → Terminal Operation

그렇기에 단순 더하기만 하면 되는 기존 코드보다 느려질 수 밖에 없다. 스트림은 대용량 환경에서만 유리하다는 것!!

NULL은 다음을 의미한다.

• 값이 없음
• 값이 아직 정해지지 않음
• 값이 존재하지 않음

중요한 점은

NULL ≠ 0
NULL ≠ '' (빈 문자열)

NULL은 아예 값 자체가 존재하지 않는 상태다.

2. NULL 비교는 = 로 하면 안 된다

가장 많이 하는 실수.

SELECT *
FROM DOCTOR
WHERE TLNO = NULL;

이 조건은 항상 참이 되지 않는다.

NULL은 값이 없기 때문에 = 비교 자체가 성립하지 않는다.

올바른 방법

SELECT *
FROM DOCTOR
WHERE TLNO IS NULL;

NULL이 아닌 경우:

SELECT *
FROM DOCTOR
WHERE TLNO IS NOT NULL;

3. NULL과 연산

NULL이 포함된 연산은 대부분 결과가 NULL이 된다.

SELECT 10 + NULL;   -- 결과: NULL
SELECT NULL * 5;    -- 결과: NULL

값이 없는데 계산할 수 없기 때문이다.

4. 집계 함수와 NULL

집계 함수는 NULL을 자동으로 제외한다.

예시 데이터:

SELECT AVG(score)
FROM exam;

결과는 95이다.
NULL은 계산에서 제외된다.

COUNT의 차이

SELECT COUNT(*), COUNT(score)
FROM exam;

• COUNT(*) → 전체 행 개수
• COUNT(score) → NULL 제외 개수

5. NULL 처리 함수

① IFNULL (MySQL)

SELECT IFNULL(TLNO, '번호없음')
FROM DOCTOR;

NULL이면 '번호없음'으로 바꿔준다.

② COALESCE (표준 SQL)

SELECT COALESCE(TLNO, '번호없음')
FROM DOCTOR;

• TLNO가 있으면 → 그대로 출력
• TLNO가 NULL이면 → '전화번호없음' 출력
• 인자가 여러개여도, 왼쪽 -> 오른쪽 순으로 대체재를 마련해주는 것

SELECT COALESCE(NULL, NULL, 'A', 'B');
-- 결과: A

• 여러 값 중 NULL이 아닌 첫 번째 값을 반환한다.

6. WHERE 절에서 NULL이 함정인 이유

SELECT *
FROM EMP
WHERE salary > 3000;

salary가 NULL인 행은 비교 자체가 불가능하다.
TRUE도 FALSE도 아닌 UNKNOWN이 된다.

SQL은 3값 논리를 사용한다.

• TRUE
• FALSE
• UNKNOWN

WHERE 절은 TRUE만 통과한다.

7. 정렬에서 NULL

DBMS마다 다르지만, MySQL 기준:

• ASC → NULL 먼저
• DESC → NULL 나중

명시적으로 제어하는 방법 (Oracle 등):

SELECT *
FROM EMP
ORDER BY salary DESC NULLS LAST;

8. JOIN에서 NULL 활용

LEFT JOIN에서 자주 발생한다.

SELECT *
FROM A
LEFT JOIN B ON A.id = B.id;

매칭되지 않는 B의 컬럼은 NULL이 된다.

이때 다음 조건을 사용하면:

SELECT *
FROM A
LEFT JOIN B ON A.id = B.id
WHERE B.id IS NULL;

→ A에는 존재하지만 B에는 없는 데이터만 조회할 수 있다.

실무에서 매우 자주 쓰이는 패턴이다.

9. 자주 틀리는 패턴

❌ 잘못된 예

WHERE TLNO <> NULL;

✅ 올바른 예

WHERE TLNO IS NOT NULL;

10. 핵심 요약

• NULL은 값이 아니다.
• = 비교 불가 → 반드시 IS NULL 사용.
• 연산 결과는 대부분 NULL.
• 집계 함수는 NULL 제외.
• WHERE는 TRUE만 통과.
• JOIN에서 NULL은 중요한 필터 조건이 된다.

DATE      → 2021-10-05
DATETIME  → 2021-10-05 14:32:10

2. 날짜 비교의 기본 원리

DATETIME은 문자열처럼 보이지만 실제로는 날짜 타입이다.
따라서 문자열 비교(LIKE)보다 범위 비교가 정확하다.

❌ 잘못된 방식 (문자열처럼 처리)

WHERE JOINED LIKE '2021%'

• DATE 타입을 문자열처럼 비교
• 인덱스를 못 탈 가능성 있음
• 실무에서는 권장되지 않음

✅ 올바른 방식 (범위 비교)

WHERE JOINED >= '2021-01-01'
  AND JOINED <  '2022-01-01'

이 방식의 장점:

1. 2021년 전체를 정확히 포함
2. 인덱스 사용 가능
3. 가장 안정적인 방법

3. 특정 연도/월 추출하기

YEAR 함수

WHERE YEAR(JOINED) = 2021

MONTH 함수

WHERE MONTH(JOINED) = 10

주의할 점:

컬럼에 함수를 적용하면 인덱스를 사용하기 어려워질 수 있다.

따라서 대용량 데이터에서는 범위 조건이 더 좋다.

4. BETWEEN 사용법

날짜 범위 조회

WHERE JOINED BETWEEN '2021-01-01' AND '2021-12-31'

주의:

• BETWEEN은 양 끝 값을 포함한다.
• DATETIME 타입이라면 시간까지 고려해야 한다.

예:

'2021-12-31 23:59:59'

을 포함하려면 정확히 명시해야 한다.

그래서 실무에서는 보통 다음 방식을 더 많이 사용한다:

JOINED >= '2021-01-01'
AND JOINED <  '2022-01-01'

주의점!!!

만약 날짜 리터럴은 반드시 작은따옴표로 감싸지 않으면?

SQL 서버에서는 이를 "계산식"으로 착각한다. 즉 2021 - 1 - 1 = 2019? 로 인식하게 된다.!!

5. 가장 빠른 데이터 찾기

가장 오래된 날짜 1개 조회

SELECT *
FROM ANIMAL_INS
ORDER BY DATETIME ASC
LIMIT 1;

가장 최신 날짜 1개 조회

SELECT *
FROM ANIMAL_INS
ORDER BY DATETIME DESC
LIMIT 1;

6. 집계와 함께 사용하기

연도별 가입자 수

SELECT YEAR(JOINED) AS YEAR, COUNT(*) AS CNT
FROM USER_INFO
GROUP BY YEAR(JOINED);

월별 가입자 수

SELECT MONTH(JOINED) AS MONTH, COUNT(*) AS CNT
FROM USER_INFO
GROUP BY MONTH(JOINED);

7. NULL과 날짜

날짜 컬럼이 NULL이면:

WHERE JOINED >= '2021-01-01'

조건에서 자동으로 제외된다.

NULL을 포함하고 싶다면:

WHERE JOINED IS NULL

8. 정리

1. 날짜는 문자열처럼 다루지 않는다.
2. 특정 연도 조회는 범위 조건이 가장 안전하다.
3. BETWEEN은 양 끝값을 포함한다.
4. 함수(YEAR, MONTH)는 편리하지만 인덱스에 불리할 수 있다.
5. 가장 빠른/늦은 날짜는 ORDER BY + LIMIT 1이 직관적이다.

9. 날짜 데이터 포맷하기

MYSQL

DATE_FORMAT(DATE, '%Y-%m-%d')

ORACLE

TO_CHAR(PUBLISHED_DATE, 'YYYY-MM-DD')

한 줄 요약

DATETIME은 문자열이 아니라 "비교 가능한 날짜 타입"이다.
실무에서는 LIKE 대신 범위 비교를 사용한다.

집계함수

집계함수는 여러 행(row)의 값을 모아서 하나의 값으로 계산하는 함수이다.
주로 GROUP BY와 함께 사용하며, “부서별/지역별/상품별 통계” 같은 요약 결과를 만들 때 사용한다.

대표적인 집계함수는 다음과 같다.

• COUNT(*) : 행의 개수를 센다.
• COUNT(col) : NULL이 아닌 값의 개수를 센다.
• SUM(col) : 합계를 구한다. (숫자 컬럼)
• AVG(col) : 평균을 구한다. (숫자 컬럼)
• MAX(col) : 최댓값을 구한다.
• MIN(col) : 최솟값을 구한다.

예시) 부서별 인원 수

SELECT dept, COUNT(*) AS cnt
FROM emp
GROUP BY dept;

주의) 집계함수와 함께 일반 컬럼을 출력하려면, 그 컬럼은 GROUP BY에 포함되어야 한다.

-- ❌ 오류 가능: name은 그룹 기준이 아니라 그룹(부서) 내에 여러 값이 존재할 수 있음
SELECT dept, name, COUNT(*)
FROM emp
GROUP BY dept;

-- ✅ 가능: dept+name 조합으로 그룹을 만들면 name도 한 그룹당 1개로 확정됨
SELECT dept, name, COUNT(*)
FROM emp
GROUP BY dept, name;

2. 절

WHERE 절

WHERE 절은 행(row) 단위 조건을 적용하여 데이터를 미리 걸러내는 절이다.
즉, GROUP BY로 묶기 전에 “어떤 행을 대상으로 집계/조회할지”를 결정한다.

• WHERE에는 일반 컬럼 조건을 자유롭게 쓸 수 있다.
• WHERE에는 보통 집계함수(COUNT, SUM 등)를 쓸 수 없다. (집계 전 단계라서)

예시) 개발팀만 먼저 필터링한 뒤 부서별 인원 집계

SELECT dept, COUNT(*) AS cnt
FROM emp
WHERE dept = '개발팀'
GROUP BY dept;

GROUP BY 절

GROUP BY 절은 특정 컬럼을 기준으로 여러 행을 묶어 그룹(group) 을 만드는 절이다.
그룹별로 집계함수를 적용해 “요약 결과”를 만들 때 사용한다.

• GROUP BY dept라면 결과는 부서당 1행이 된다.
• 따라서 SELECT에는 다음만 올 수 있다.
  • GROUP BY에 포함된 컬럼
  • 집계함수로 계산된 값

예시) 부서별 평균 급여

SELECT dept, AVG(salary) AS avg_salary
FROM emp
GROUP BY dept;

잘못된 예시

-- ❌ name은 같은 dept 안에 여러 값이 있어서, 그룹 결과 1행에 무엇을 넣을지 결정 불가

SELECT dept, name, COUNT(*)
FROM emp
GROUP BY dept;

HAVING 절

HAVING 절은 그룹(group) 단위 조건을 적용하는 절이다.
즉, GROUP BY로 그룹을 만든 뒤 “어떤 그룹만 남길지” 필터링한다.

• HAVING에는 보통 다음만 쓸 수 있다.
  • GROUP BY에 쓴 컬럼
  • 집계함수 결과 (COUNT, SUM, AVG 등)
• GROUP BY에 없는 일반 컬럼을 HAVING에 쓰면 오류가 날 수 있다.

예시) 부서별 인원 수 중 3명 이상인 부서만

SELECT dept, COUNT(*) AS cnt
FROM emp
GROUP BY dept
HAVING COUNT(*) >= 3;

예시) GROUP BY에 쓴 컬럼으로 HAVING 조건

SELECT dept, COUNT(*) AS cnt
FROM emp
GROUP BY dept
HAVING dept <> '인턴팀';

오류 예시

-- ❌ name은 그룹 기준도 아니고 집계값도 아니라 그룹 결과에서 확정 불가
SELECT dept, COUNT(*)
FROM emp
GROUP BY dept
HAVING name = 'Kim';

실행 순서(이해용)

일반적으로 다음 순서로 처리된다고 이해하면 된다.

FROM → WHERE → GROUP BY → HAVING → SELECT

• WHERE: 행 필터(집계 전)
• HAVING: 그룹 필터(집계 후)

SELECT가 논리적으로 GROUP BY 뒤에 처리되기 때문에, 이미 데이터가 “그룹 단위”로 바뀐 상태. 그래서 SELECT에서는 그룹 기준 컬럼이나 집계값만 안전하게 꺼낼 수 있음

1. 문제요약

• N * N 크기의 공간에 물고리 M마리와 아기 상어 1마리가 있다.
  • 아기상어의 초기 크기는 2이고, 물고기는 입력값으로 주어진다.
• 아기 상어는 자기보다 큰 물고기의 칸은 지나갈 수 없다.
• 아기 상어는 자기와 같은 크기의 물고 칸은 지나갈 수 있다.
• 아기 상어는 자기보다 작은 물고기를 이동과 동시에 먹는다. 중요포인트 : 자기의 크기와 같은 수의 물고기를 먹어야지만 크기가 1 커진다.

[아기 상어의 움직임]

• 먹을 수 있는 물고기가 여러 마리라면 거리가 가장 가까운 물고기를 먹는다.
  • 거리가 동일하다면, 가장 위에 있는 물고기, 모두 위에 있다면 가장 왼쪽 물고기를 먹는다.
• 거리 측정은 지나가야 하는 칸의 최솟값이다.
• 아기 상어의 이동은 1초 걸린다. (1칸에 1초 걸림.)

더 이상 먹을 수 있는 물고기가 없을 때까지 몇초가 지나는지 구하라.

2. 입출력

[입력]

• 공간의 크기 N(2 ≤ N ≤ 20)
• N개의 줄에 공간의 상태가 주어짐
  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

[출력]

• 더 이상 먹을 수 있는 물고기까지 없을 때 까지. 몇 초가 지났는지 구하라. ( = 상어가 얼마나 이동했는지 거리를 구하라. )

3. 알고리즘

• 필요한 전역 자료구조

  • 전체 map 저장할 int 배열 : 입력값으로 주어진 배열
  • 현재 상어의 몸무게, 먹은 물고기 카운팅 전역 변수 선언.

• bfs 시 필요한 자료구조

  • 상어보다 작고, 거리가 같은 물고기들의 위치 정보 모아줄 우선순위 큐
    • 우선순위 큐의 정렬 조건(1. 위쪽인가 3. 왼쪽인가)
  • bfs 돌아줄 ArrayDeque

• 매번 가장 최소 경로 찾는 루트 -> bfs
  • 현재 위치에서 bfs 돌리면서 첫 번째 물고기가 발견됐을 때의 거리 기록 (이후 해당 거리보다 멀다면 bfs를 돌리지 않기 위함.)
    • 먹을 수 있는 물고기가 발견된다면 우선순위큐에 저장

4. 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

import javax.print.DocFlavor.READER;


class Info implements Comparable <Info> {
    int x;
    int y;
    int dis;

    public Info (int x, int y, int dis){
        this.x=x;
        this.y=y;
        this.dis = dis;
    }

    @Override
    public int compareTo(Info o) {
        if (this.x == o.x)
            return this.y-o.y;
        return this.x-o.x;
    }
}

public class Main {
    static int N, SHARK_WEIGHT, EAT_CNT, TIME;
    static int [][] MAP;
    static int DIR[][] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        MAP = new int[N][N];

        SHARK_WEIGHT = 2;
        EAT_CNT = 0;
        TIME = 0;

        Info shark = null;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                MAP[i][j] = Integer.parseInt(st.nextToken());
                if(MAP[i][j] == 9){
                    shark = new Info(i, j,0);
                    MAP[i][j] = 0;
                }
            }
        }

        while (shark != null) {
            if(EAT_CNT >= SHARK_WEIGHT) {
                SHARK_WEIGHT++;
                EAT_CNT = 0;
            }
            shark = findFish(shark);
        }

        System.out.println(TIME);
    }

    static Info findFish(Info shark) {
        Queue<Info> pq = new PriorityQueue<>();
        Queue<Info> bfs = new ArrayDeque<>();
        boolean [][] visit = new boolean[N][N];

        shark.dis = 0;
        bfs.add(shark);
        visit[shark.x][shark.y] = true;

        int minDis = -1;

        while (!bfs.isEmpty()) {
            Info now = bfs.poll();

            for(int i = 0; i < 4; i++) {
                int nx = now.x+DIR[i][0];
                int ny = now.y+DIR[i][1];

                if(!canGo(nx, ny) || visit[nx][ny]) 
                    continue;
                if(minDis != -1 && now.dis+1 > minDis)
                    continue;
                visit[nx][ny] = true;
                Info next = new Info(nx, ny, now.dis+1);

                if(MAP[nx][ny] > 0 && MAP[nx][ny] < SHARK_WEIGHT){
                    pq.add(next);
                    if(minDis == -1)
                        minDis = next.dis;
                }
                bfs.add(next);
            }
        }

        Info fish = pq.poll();
        if(fish != null){
            EAT_CNT++;
            TIME += fish.dis;
            MAP[fish.x][fish.y] = 0;
        }

        return fish;
    }

    static boolean canGo(int nx, int ny) {
        if(nx < 0 || ny < 0 || nx >= N || ny >= N)
            return false;
        if(MAP[nx][ny] > SHARK_WEIGHT)
            return false;
        return true;
    }
}

한 시간만에 풀어서 뿌듯하다 구현 실력이 올라간 것 같다!!!

1. 문제요약

• N * N 크기의 땅이 있고, 각 땅에는 초기에 5만큼의 양분이 있다.

• 나무는 사계절을 보내며 다음과 같은 과정을 거친다.

• 봄

  • 나무가 자신의 나이만큼 현재 위치한 땅의 양분을 먹고, 나이가 1 증가한다.
  • 하나의 칸에 여러 나무가 있다면, 가장 어린 나무부터 양분을 먹는다.
  • 나이만큼 먹을 양분이 부족하다면 해당 나무는 양분을 흡수하지 않고 바로 죽는다.

• 여름

  • 봄에 죽은 나무가 양분으로 변한다. (해당 나무 나이 / 2)

• 가을

  • 나이가 5의 배수인 나무들만 번식한다. 인접한 8개의 칸에 나이가 1인 나무를 추가한다.

• 겨울

  • 땅에 양분을 추가한다. 추가되는 양분의 양은 입력값으로 주어진다.

• K년이 지난 후, 살아있는 나무의 개수를 구하라.

2. 입출력

[입력]

• 땅 크기 N, 나무 그루 수 M, 주어질 년 수 K 주어짐
• N개의 줄에 양분의 양이 주어짐. 매해 겨울마다 추가해줘야 함.
• 다음 M개의 줄에 나무의 정보 나타내는 X, Y, Z 주어짐 (위치 X,Y, 나이 Z)

3. 제한

• 1 ≤ N ≤ 10
• 1 ≤ K ≤ 1,000
• 1 ≤ A[r][c] ≤ 100
• 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10

4. 시간

• 0.3초

5. 알고리즘

단순 빡구현

나무 관련 3개의 자료구조

• 죽은 나무 정보 담을 리스트1
• 새롭게 나이를 먹은 나무 정보 담을 리스트2
• 현재 나무의 생/사 결정 위한 정보 담을 우선순위큐1

땅 관련 2개의 배열

• 매 겨울마다 추가해줄 초기 입력값 양분 배열
• 매해마다 갱신되는 양분 배열

1. 나이 순대로 우선순위큐에 나무 위치 저장.
2. 해당 큐가 빌 때까지 돌림 2.1 해당 땅에 나무 나이만큼의 양분이 있다면, 해당 땅의 양분 줄인 후, 나무 나이 추가해 리스트2에 담음 2.2 없다면, 리스트1에 담음
3. 리스트1에 담긴 나무들의 나이 / 2 만큼의 양분을 땅에 추가한다.
4. 리스트1의 size만큼 돌린다. 4.1 나이가 5배수에 해당하는 나무들의 8개의 인접 땅에 1살 나무를 추가.
5. 입력값으로 주어졌던 양분을 땅에 더해준다.

위 과정을 k년만큼 반복한 후, 최종 리스트2의 크기를 반환한다.

6. 정답 코드

위 로직대로 코드를 짜니, 쉽게 정답을 맞출 수 있었다.

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

class Info implements Comparable <Info> {
    int x;
    int y;
    int age;

    public Info(int x, int y, int age)
    {
        this.x=x;
        this.y=y;
        this.age=age;
    }

    @Override
    public int compareTo(Info o){
        return this.age-o.age;
    }
}

public class Main {
    static int N;
    static int [][] GROUND;
    static int [][] ENERGY;
    static List<Info> DEAD;
    static List<Info> LIVE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M, K;

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        ENERGY = new int[N+1][N+1];
        GROUND = new int[N+1][N+1];
        DEAD = new ArrayList<>();
        LIVE = new ArrayList<>();

        for(int i=1; i<=N; i++){ 
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++){
                ENERGY[i][j] = Integer.parseInt(st.nextToken());
                GROUND[i][j] = 5;
            }
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());

            LIVE.add(new Info(x, y, age));
        }

        while (K --> 0) {
            spring();
            summer();
            fall();
            winter();
        }

        System.out.println(LIVE.size());
    }

    static void spring() {
        Queue<Info> pq = new PriorityQueue<>();
        List<Info> tmp = new ArrayList<>();

        for(int i=0; i<LIVE.size(); i++){
            pq.add(LIVE.get(i));
        }

        while (!pq.isEmpty()) {
            Info tree = pq.poll();

            if(tree.age > GROUND[tree.x][tree.y]){
                DEAD.add(tree);
                continue;
            }
            GROUND[tree.x][tree.y]-=tree.age;
            tree.age++;
            tmp.add(tree);
        }
        LIVE = tmp;
    }

    static void summer(){
        for(Info dead : DEAD){
            GROUND[dead.x][dead.y] += (dead.age / 2);
        }
        DEAD = new ArrayList<>();
    }

    static void fall() {
        int [][] dir = {{1,0}, {-1,0}, {0,1}, {0, -1}, {1,1}, {-1,-1}, {1,-1}, {-1,1}};

        for(int i=0; i<LIVE.size(); i++) {
            Info tree = LIVE.get(i);
            if(tree.age % 5 != 0)
                continue;
            for(int j=0; j<8; j++) {
                int nx = tree.x+dir[j][0];
                int ny = tree.y+dir[j][1];
                if(nx <= 0 || ny <= 0 || nx > N || ny > N) 
                    continue;
                LIVE.add(new Info(nx, ny, 1));
            }
        }

    }

    static void winter(){
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                GROUND[i][j] += ENERGY[i][j];
            }
        }
    }

}

근데 메모리도, 시간도 너무너무너무 비효율적이었다.

그래서 가장 빠른 코드를 찾아봤는데, 나랑 정말 다른 접근법으로 푸셨길래 분석해봤다.

7. 다른 사람 풀이 코드

이 코드는 헤더 노드가 있는 원형 이중 연결리스트로 풀이한 버전이다. 코테 하면서 한 번도 이런 형태로 푼 적이 없는데, 참고하면 좋을 것 같다.

해당 코드 링크 이동

원형 이중 연결리스트

일반 연결리스트는 다음과 같이 생겼을 것이다.

A -> B -> C -> null

그러나 원형 이중 연결리스트란, 다음과 같이 연결되어있다.

![](https://velog.velcdn.com/images/jung-min-ju/post/dd408edd-035a-4ba9-962b-e445a5bad231/image.png)

모든 노드가 원형으로 연결되어있으며, 좌우로도 연결되어 있다.

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

public class Main {

    static int n;
    static int m;
    static int k;
    static int[][] winterFood;
    static int[][] soil;
    static Tree[][] trees;
    static int[] dx = {0, 0, -1, 1, 1, 1, -1, -1};
    static int[] dy = {-1, 1, 0, 0, 1, -1, 1, -1};
    static StringBuilder sb = new StringBuilder();

    static class Tree {
        int cnt = 0;
        int age = 0;
        Tree before;
        Tree next;

        public Tree() { // 헤더 트리 만들기
            before = next = this;
        }

        public Tree(int age) { // 문제에서 주어지는 트리 만들기
            this.age = age;
            cnt = 1;
        }

        public Tree(int age, int cnt) { // 번식할 트리 만들기(개수도 필요함)
            this.age = age;
            this.cnt = cnt;
        }

        // 문제에서 입력으로 주어지는 나무의 위치는 모두 다르다고 했다.
        // 이후, 나무가 번식을 하면 새로운 나무를 추가해 주어야 하는데,
        // 현재 Tree의 두번째 부분(첫번째는 편의상 빈 나무임 = 헤더)에 넣어주면 된다.

        // A(헤더)의 뒤에 B를 넣으면 된다.
        // A -> B -> C   =>    A -> D -> B -> C
        public void add(Tree tree) {
            this.next.before = tree;
            tree.next = this.next;
            tree.before = this;
            this.next = tree;
        }

        // X.delete(Y)
        // X 트리부터 Y트리 전까지 연결됨.

        // A -> D -> C -> B 가 있다고 할 때
        // A.delete(B) : A -> D
        // A.delete(C) : A -> D -> B
        // D.delete(B) : D -> C
        // X == Y라면 자기 자신만 남음.
        // X < Y라면 그대로.

        // add를 하면 나이 순서대로 정렬이 될텐데
        // 양분을 못 먹는 나무 이후로부터는 전부 죽어버린다.
        // A -> B -> C -> D 가 있을때, C부터는 양분을 못먹어서 죽어버린다고 할 때
        // A.delete(C)를 해주면 A -> B만 남게 되는 것이다.
        public void delete(Tree tree) {
            tree = tree.before;
            tree.next = this;
            this.before = tree;
        }
    }

    static void setInputs() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        winterFood = new int[n][n];
        soil = new int[n][n];
        trees = new Tree[n][n];

        for (int r = 0; r < n; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < n; c++) {
                winterFood[r][c] = Integer.parseInt(st.nextToken());
                soil[r][c] = 5;
                trees[r][c] = new Tree();
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int z = Integer.parseInt(st.nextToken());

            trees[x][y].add(new Tree(z));
        }
    }

    private static void performSpringAndSummerOperation() { // 봄 행동(여름을 곁들인)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                boolean canAbsorbSoil = true;
                Tree treeToDelete = null;
                Tree tree = trees[i][j].next;

                while (tree.age > 0) { // 나무 끝까지 탐색해서 다시 헤더로 돌아 온다면 종료
                    // 양분 섭취
                    if (canAbsorbSoil) {
                        int sum = tree.cnt * tree.age; // 해당 나무가 양분을 얼마나 섭취할 수 있니?
                        if (soil[i][j] >= sum) { // 양분 섭취가 가능하다!
                            soil[i][j] -= sum;
                            tree.age++;
                        } else { // 양분 섭취를 못해요!
                            /**
                             * 여름
                             */
                            treeToDelete = performSummerOperation(i, j, tree);
                            canAbsorbSoil = false; // 더이상 양분을 먹을 나무는 없고 전부다 토양으로 돌아가요! 슬픕니다.
                        }
                    } else { // 너흰 이제 토양으로 돌아가라.
                        soil[i][j] += tree.cnt * (tree.age / 2);
                    }

                    tree = tree.next; // 다음 트리를 탐색합니다.
                }

                // 모든 트리를 탐색했으니, 이제 제거할 트리가 있는지 찾아볼까요?
                if (treeToDelete == null) {
                    continue;
                } // 제거할 트리가 있다면?? 제거해주면 됩니다.
                trees[i][j].delete(treeToDelete);
            }
        }
    }

    static Tree performSummerOperation(int i, int j, Tree tree) { // 여름 행동
        Tree treeToDelete;
        int ableTreesCount = soil[i][j] / tree.age; // 현재 토양에서 지금 나이의 나무 몇그루가 양분을 섭취할 수 있나?

        soil[i][j] -= ableTreesCount * tree.age; // 양분을 먹었어요!
        soil[i][j] +=
                (tree.cnt - ableTreesCount) * (tree.age / 2); // 죽은 나무는 나이의 절반만큼 양분으로 돌아갑니다!

        if (ableTreesCount > 0) { // 양분을 먹은 나무가 있었다면
            tree.cnt = ableTreesCount; // tree의 cnt를 다시 갱신해준다.
            tree.age++; // 한 살 더 먹으렴
            treeToDelete = tree.next; // 이 다음 나무부터는 제거 해버린다.
        } else { // 아무도 양분을 못먹었다면 이 나무부터 제거 해버린다.
            treeToDelete = tree;
        }
        return treeToDelete;
    }

    private static void performAutumnOperation() { // 가을 행동
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Tree tree = trees[i][j].next;
                while (tree.age > 0) { // 헤더로 다시 돌아오면 종료.
                    // 나이가 5의 배수인 나무의 경우
                    if (tree.age % 5 == 0) {
                        for (int dir = 0; dir < 8; dir++) { // 8방 탐색 슛~~
                            int nx = i + dx[dir];
                            int ny = j + dy[dir];

                            if (nx < 0 || ny < 0 || nx >= n || ny >= n) { // 맵 밖으로 벗어나면 continue
                                continue;
                            }

                            if (trees[nx][ny].next.age == 1) { // 이미 해당칸에 다른칸에서 번식해온 나무가 있으면
                                // 헤더만 존재했다면 해더의 age는 0이라 조건을 만족 못해요.
                                trees[nx][ny].next.cnt += tree.cnt; // 이제 번식할 나무의 개수만 더해주면 된다.
                                continue;
                            }

                            trees[nx][ny].add(
                                    new Tree(1, tree.cnt)); // 해당 칸에 처음 번식을 하는거라면 나이는 1, 번식할 나무의 개수로 tree 생성

                        }
                    }
                    tree = tree.next; // 다음 트리 탐색
                }
            }
        }
    }

    private static void performWinterOperation() { // 겨울 행동
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                soil[i][j] += winterFood[i][j];
            }
        }
    }

    static int calculateAnswer() { // 답 계산
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Tree tree = trees[i][j].next;
                while (tree.age > 0) { // 헤더로 다시 돌아오면 종료
                    ans += tree.cnt; // 나무 count 해주기
                    tree = tree.next; // 다음 트리로 Go
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        setInputs();

        for (int year = 1; year < k + 1; year++) { // 1년부터 K년 까지

            performSpringAndSummerOperation();
            performAutumnOperation();
            performWinterOperation();
        }

        int ans = calculateAnswer();

        sb.append(ans);
        System.out.println(sb);
    }
}