일반 연습 > 기출 문제 > 나무박멸

• 삼성 SW 역량테스트 2022 상반기 오후 2번 문제
• 시뮬레이션

🔐 풀이

• 시간: 2시간 + a

아이디어

문제 그대로를 구현하면 되는 시뮬레이션 문제이다. 그중에서 제초제 뿌린 구역을 어떻게 관리하할지가 핵심이었다. "제초제가 뿌려진 곳에 다시 제초제가 뿌려지는 경우에는 새로 뿌려진 해로부터 다시 c년동안 제초제가 유지됩니다."라는 말이 있어서 visited 배열을 boolean에서 int로 바꿔주었다. c+1번 째에 제초제가 갱신되므로 값에 c+1을 넣어주었다. int로 관리함으로써 테스트케이스 7번을 마침내 통과할 수 있었다. 추가로 테스트케이스 5번에서 런타임에러를 받았는데, 이는 제초제를 뿌릴 곳이 없을 때 특정 인덱스의 값을 불러오려고 해서 발생한 문제였다.

시간복잡도

성장/번식/제초제 뿌리는 과정이 각각 N^2이고 이를 M년 만큼 수행한다

O(M * N^2)

👉 제출 코드

import java.util.*;
import java.io.*;
public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[] ddx = {-1, -1, 1, 1};
    static int[] ddy = {-1, 1, -1, 1};
    static class Pos implements Comparable<Pos>{
        int x; int y;
        int count;
        Pos(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
        @Override
        public int compareTo(Pos o) {
            if (this.count == o.count) {
                if (this.x == o.x) {
                    return this.y - o.y;
                }
                return this.x - o.x;
            }
            return o.count - this.count;
        }
        @Override
        public String toString() {
            return x + " " + y + " " + count;
        }
    }
    static int n, m, k, c;
    static int[][] trees;
    static int[][] visited; // 제초제 기록을 상수로ㅠㅠㅠㅠㅠ
    static List<Pos> candidates;
    static int ans;
    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());
        k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        trees = new int[n][n];
        visited = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                trees[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        while (m-->0) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (visited[i][j] > 0) visited[i][j]--;
                }
            }
            candidates = new ArrayList<Pos>();
            grow();
            breeding();
            spray();
        }
        System.out.println(ans);
    }
    private static void grow() {
        // 4방향 기준 개수 구하기
        int[][] tmp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (trees[i][j] == 0 || trees[i][j] == -1 || visited[i][j] != 0) continue;
                int count = 0;
                for (int d = 0; d < 4; d++) {
                    int nx = i + dx[d];
                    int ny = j + dy[d];
                    if (outOfRange(nx, ny) || visited[nx][ny] != 0) continue;
                    if (trees[nx][ny] != 0) count++;
                }
                tmp[i][j] = count;
            }
        }
        // 동시에 성장
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                trees[i][j] += tmp[i][j];
            }
        }
    }

    private static void breeding() {
        // 벽, 다른 나무, 제초제가 없어야 함
        // 번식 가능한 곳 개수만큼 나눈다
        int[][] tmp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (trees[i][j] <= 0) continue;
                int count = 0; // 번식이 가능한 칸의 개수
                List<int[]> pos = new ArrayList<>();
                for (int d = 0; d < 4; d++) {
                    int nx = i + dx[d];
                    int ny = j + dy[d];
                    if (outOfRange(nx, ny) || trees[nx][ny] != 0 || visited[nx][ny] > 0) continue;
                    count++;
                    pos.add(new int[] {nx, ny});
                }
                for (int[] p : pos) {
                    tmp[p[0]][p[1]] += trees[i][j]/count;
                }
            }
        }
        // 동시에 번식
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                trees[i][j] += tmp[i][j];
            }
        }
    }

    private static void spray() {
        // 가장 많이 박멸되는 칸에 제초제 뿌림
            // 대각선 방향으로 k칸 만큼 + 본인 거
            // bfs로 박멸되는 나무 개수 구하기
                // 벽, 나무 아예 없는 경우 거기까지만
                // c년 만큼 작용
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (trees[i][j] == 0 || trees[i][j] == -1) continue;
                int count = trees[i][j];
                for (int d = 0; d < 4; d++) {
                    for (int size = 1; size <= k; size++) {
                        int nx = i + ddx[d] * size;
                        int ny = j + ddy[d] * size;
                        if (outOfRange(nx, ny) || trees[nx][ny] == 0) break;
                        count += trees[nx][ny];
                    }
                }
                candidates.add(new Pos(i, j, count));
            }
        }
        if (candidates.size() == 0) return;
        Collections.sort(candidates);
        // 제초제 뿌리기
        Pos target = candidates.get(0);
        ans += target.count;
        visited[target.x][target.y] = c+1;
        trees[target.x][target.y] = 0;
        for (int d = 0; d < 4; d++) {
            for (int size = 1; size <= k; size++) {
                int nx = target.x + ddx[d] * size;
                int ny = target.y + ddy[d] * size;
                if (outOfRange(nx, ny)) break;
                if (trees[nx][ny] == 0) {
                    visited[nx][ny] = c+1;
                    break;
                }
                visited[nx][ny] = c+1;
                trees[nx][ny] = 0;
            }
        }
    }

    private static boolean outOfRange(int x, int y) {
        return x < 0 || x >= n || y < 0 || y >= n || trees[x][y] == -1;
    }
}

코딩테스트 연습 > SELECT > 특정 세대의 대장균 찾기

문제 설명

3세대의 대장균의 ID를 오름차순으로 정렬하기ㄹ

테이블 설명

parent_id와 id로 이루어져있고 parent_id가 NULL이면 1세대를 의미한다

🔐 풀이

아이디어

테이블을 3번 조인하거나 두 번의 서브쿼리로 parent_id와 id를 비교한다.

👉 제출 코드

방법 1: 서브쿼리

select id
from ecoli_data
where parent_id in (
    select id
    from ecoli_data
    where parent_id in (select id from ecoli_data
              where parent_id is null)
) order by id asc

방법 2: recursive

with recursive tmp as (
    select id, 1 as gen
    from ecoli_data
    where parent_id is null
    union all
    select e.id, tmp.gen+1 as gen
    from tmp join ecoli_data e
    on e.parent_id = tmp.id
)

select id
from tmp
where gen = 3
order by 1 asc

숫자 카드 2

문제 설명

주어진 배열에서 주어진 숫자의 개수를 센다.

• 예시 입력

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

• 예시 출력

  3 0 0 1 2 0 0 2

🔐 풀이

아이디어

해시 맵으로 개수를 저장해놓고 key 값으로 조회해도 되지만, 이분 탐색을 연습하고 싶어서 이분 탐색으로 풀이했다.

중복 원소의 개수를 구하기 위해서 해당 숫자가 있는 가장 왼쪽 인덱스와 해당 숫자보다 큰 수 중 가장 작은 수의 인덱스를 찾아서 빼는 방법을 사용했다.

이를 각각 lower bound, upper bound로 부르는 듯하다.

각각 이분 탐색하지 않고 구하니 임계값에 대한 처리가 어려워 각각 이분 탐색을 통해 인덱스를 구해주었다 : lowerBound, upperBound 함수.

👉 제출 코드

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

public class Main {
    static int N; // 상근이가 가지고 있는 숫자 카드의 개수
    static int[] cards; // 숫자 카드에 적혀있는 정수
    static int M;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cards = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        // 정렬
        Arrays.sort(cards);

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int k = Integer.parseInt(st.nextToken());
            sb.append(upperBound(k) - lowerBound(k)).append(' ');
        }
        System.out.println(sb);
    }
    static int lowerBound(int k) {
        // "k 값 이상"을 가지고 있는 가장 작은 인덱스(처음 만난)
        int low = 0;
        int high = N;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (cards[mid] >= k) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
    static int upperBound(int k) {
        // "k 값 초과"를 가지고 있는 가장 작은 인덱스(처음 만난)
        int low = 0;
        int high = N;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (cards[mid] > k) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

• 인텔리제이 최신 판을 깔아보니 코드를 자동완성 해주었다. 이때, mid 값을 (low + high)/2가 아닌 다른 형태로 선언하였다. 이는 해당 문제와는 관련이 없지만, high가 Integer.MAX_VALUE보다 클 때 overflow를 방지할 수 있다는 의미를 가진다.

프로세스와 스레드의 차이는?

프로세스는 메인 메모리에 적재되어 실행되는 프로그램을 의미합니다. 스레드는 프로세스가 할당받은 자원을 이용하는 실행 흐름의 단위를 의미합니다.

메모리 영역을 공유하는 모습에 차이가 있습니다.

메모리 구조는 스택, 힙, 코드, 데이터(static) 영역으로 나누어져 있는데, 프로세스는 독립적인 메모리 공간에서 동작하는 반면, 스레드는 스택을 제외한 나머지 공간을 공유한다는 차이점이 있습니다.

코드, 데이터, 힙 메모리 영역을 공유하기 때문에 어떤 스레드 하나에서 오류가 발생하면 같은 프로세스 내에 다른 스레드가 모두 강제로 종료됩니다.

메모리의 힙과 스택의 차이는?

스택은 정적 메모리 할당에 사용되며, 컴파일 시간에 크기가 결정됩니다. 함수가 호출되면 지역변수와 매개변수가 저장되는 곳으로, 함수가 종료되면 할당된 메모리가 자동으로 해제됩니다.

반면, 힙은 동적 메모리 할당(new 연산자)에 사용되며, 프로그램 실행 중(런타임)에 메모리 크기가 결정됩니다. 힙에 할당된 메모리는 개발자가 직접 관리하며, 명시적으로 해제해야 합니다.

멀티프로세싱, 멀티프로그래밍, 멀티태스킹, 멀티스레딩을 구분해주세요.

멀티프로세싱은 여러 개의 CPU 코어가 동시에 작업을 처리하는 것을 말합니다.

멀티프로그래밍은 단일 프로세스 시스템의 단점을 보완하기 위해 등장하였습니다. 여러 개의 프로그램이 CPU에서 동시에 실행된다는 의미로, CPU 사용률을 극대화시키는 것이 목적입니다.

멀티태스킹은 프로그램을 아주 작은 단위로 번갈아 처리하며 작업 응답 시간을 최소화하는 방법입니다. 이로서 유저는 동시에 실행되는 것처럼 느끼게 되고 여기서, 컨텍스트 스위칭이 발생하게 됩니다. 프로세스 간에 서로 자원을 공유하지 못하므로 IPC(Inter-Process Communication)를 구현해야 합니다.

멀티 스레딩은 하나의 프로세스가 동시에 여러 작업(스레드)를 실행하는 방법입니다. 멀티태스킹과 달리 서로 간의 자원 공유가 가능합니다.

IPC란?

프로세스들끼리 서로 데이터를 주고받는 행위 또는 그에 대한 방법을 이야기합니다. 커널 영역에서 IPC라는 내부 프로세스간 통신을 제공하게 되고, 프로세스는 커널이 제공하는 IPC 설비를 이용해서 프로세스산 통신을 할 수 있습니다.

IPC의 종류에는 메세지 전달(Message Passing)과 메모리 공유(Shared Memory)가 있습니다.

메세지 전달은 프로세스들이 커널을 통해 메세지를 전달하는 방법입니다.

커널에서 제어해주기 때문에 별도의 동기화가 필요다는 장점이 있습니다. 반대로 커널을 경유하기 때문에 속도가 상대적으로 느리다는 단점을 가지고 있습니다.

(메세지 전달에는 파이프, 메세지 큐, 소켓 등이 있습니다.)

메모리 공유는 프로세스 간 공유된 메모리를 생성하여 이용하는 방법입니다.

컨텍스트 스위칭이란?

CPU에서 실행할 프로세스 또는 스레드를 교체하는 기술입니다. 여러 프로세스나 스레드를 동시에 실행(멀티태스킹)하기 위해서 필요하고 주어진 timeslice(작업 시간)을 다 사용했거나, I/O 작업을 해야하거나, 다른 리소스를 기다려야 하는 등의 경우에 사용됩니다.

커널에 의해 실행되고 프로세스 스위칭과 스레드 스위칭이 있습니다. 이때, PCB라는 별도 공간에 프로세스 상태값을 저장하고 다시 찾아서 실행됩니다.

스레드 컨텍스트 스위칭이 더 빠른 이유는?

스레드는 메모리 영역을 공유하기 때문에 메모리에 관련된 처리 과정이 필요 없기 때문입니다. 프로세스 스위칭은 주소 체계가 다르기 때문에 가상 메모리 주소 관련 처리를 추가로 진행합니다. (MMU가 P2 메모리를 참조, TLB(버퍼) 초기화, 캐시 비워주기의 과정이 필요합니다.)

페이징과 세그멘테이션의 차이는?

멀티프로그래밍 시스템에서 다수의 프로세스를 수용하기 위해 주기억장치를 동적으로 분할하는 메모리 관리 방법입니다.

페이징은 프로세스를 일정한 크기의 페이지로 분할해서 메모리에 적재하는 방식입니다. 논리 메모리가 물리 메모리에 저장될 때 연속되어 저장할 필요가 없고, 남는 프레임에 적절히 배치되기에 외부 단편화가 생기지 않습니다. 반면, 프로세스가 사용하는 메모리 공간이 남는 경우인 내부 단편화가 일어날 수 있습니다. (내부단편화는 여백)

세그멘테이션은 가상 메모리를 서로 크기가 다른 논리적 단위로 분할한 방법입니다. 총 메모리 공간은 충분하지만 실제로 할당할 수 없는 경우 외부 단편화가 일어날 수 있습니다. (외부단편화는 적재되지 못한 공간)

메모리가 고갈되면 일어나는 현상은?

메모리가 고갈되고 프로세스들의 swap이 활발해지면서(페이지 부재 자주 일어남) CPU 이용률이 하락하게 되고, 낮아진 CPU 이용률에 OS는 오히려 프로세스를 추가하는 쓰레싱 현상이 발생합니다.

쓰레싱이 해소되지 않을 경우, Out of Memory 상태로 판단되어 중요도가 낮은 프로세스를 찾아 강제로 종료하게 됩니다.

이를 해결하기 위해 Page Fault Frequency 알고리즘을 통해 Page Fault 퍼센트의 상한과 하한을 두고 너무 자주 일어나면 메모리를 더 주고, 너무 덜 일어나면 메모리르 뺏는 방법이 있습니다. 또는 물리적인 메모리(RAM) 추가하여 해결할 수 있습니다.

데이터베이스를 정의하세요

• Stored Data: 컴퓨터에 저장되어 실시간 접근 가능
• Integrated Data: 중복된 데이터 제거
• Operational Data: 존재 가치가 확실한 자료의 모임
• Shared Data: 여러 사람이 공유하고 통합 및 관리

데이터베이스 시스템의 목적은 무엇인가요?

파일 시스템의 단점을 극복하기 위해서입니다.

(DBMS의 장점)

• 데이터의 공유
• 데이터 중복 최소화: 통합 및 관리하여 자료의 중복과 데이터 중복을 최소화할 수 있다
• 보안성: 인가된 사용자들만 접근할 수 있도록 계정 관리 또는 접근 권한을 설정할 수 있다

키(Key)의 종류에는 어떤 게 있나요?

우선, 키란 검색, 정렬시 튜플을 구분할 수 있는 속성값입니다.

• 슈퍼키: 유일성만 만족
• 후보키: 유일성 + 최소성 만족
• 후보키 중에서 하나를 기본키로 정하고, 나머지는 대체키
• 외래키는 다른 릴레이션의 기본키를 참조하는 속성

예를 들어, <학생> 릴레이션에서 '학번'이나 '주민번호'는 기본키로 사용할 수 있으므로 후보키가 될 수 있습니다. '학번'을 기본키로 정의하면 '주민번호'는 대체키가 됩니다. 이때 슈퍼키는 '학번', '주민번호', '학번+주민번호', '학번+주민번호+성명' 등으로 구성할 수 있습니다.

무결성이란 무엇입니까?

데이터의 결함이 없는 상태로, 중복이나 누락이 없는 상태인 정확성, 원인과 결과의 의미가 연속적으로 보장되어 변하지 않는 상태인 일관성이 유지되는 것을 의미합니다.

종류로는 개체 무결성, 참조 무결성, 도메인 무결성, 사용자 정의 무결성이 있습니다.

개체 무결성은 기본키와 관련된 특징으로, 모든 테이블의 기본키는 유일하며 NULL이나 중복값을 가질 수 없음을 의미합니다. 이로서, 각 행의 고유성을 보장할 수 있습니다.

참조 무결성은 외래키와 관련된 특징으로, 참조되는 테이블의 기본 키가 수정되거나 삭제될 경우 참조하는 테이블의 외래 키도 영향을 받는다는 것을 의미합니다.

• RESTRICTED/CASCADE/SET NULL

도메인 무결성은 필드의 유효한 범위, 타입, 형식을 지정하여 데이터의 일관성과 정확성을 보장합니다.

트랜잭션이란 무엇입니까?

트랜잭션은 데이터베이스관리 시스템에서 데이터를 바꾸는 작업 단위로서 ACID와 같은 특징을 가집니다.

• Atomicity (원자성) : 트랜잭션을 구성하는 연산 전체가 모두 정상적으로 실행되거나 모두 취소되어야 한다.
• Consistency (일관성) : 트랜잭션이 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 유지한다.
• Isolation (고립성) : 두 개 이상의 트랜잭션이 동시에 발생할 때, 서로의 연산에 영향을 주면 안 된다.
• Durability (영구성) : 커밋된 트랜잭션의 내용은 영구히 반영된다.

트랜잭션의 격리수준에 대해 말해주세요.

동시에 여러 트랜잭션이 처리될 때, 트랜잭션끼리 얼마나 서로 고립되어 있는지를 나타내는 것을 트랜잭션의 격리 수준이라고 합니다.

• Serializable 가장 엄격한 격리 수준으로, 트랜잭션을 순차적으로 진행시킨다. 여러 트랜잭션이 동일한 레코드에 동시 접근할 수 없으므로, 어떠한 데이터 부정합 문제가 발생하지 않는다. 하지만 동시 처리 성능이 매우 떨어지므로 극단적으로 안전한 작업이 아니라면 사용하지 않는다.

• Repeatable Read 변경 전의 레코드는 언두 공간에 백업된다. 변경 전/후 데이터가 모두 존재하여 이를 MVCC(다중 버전 동시성 제어)라고 부른다. 나중에 실행된 트랜잭션에 의해 값이 변경됐을 때 언두로그를 참고하여 조회하므로 한 트랜잭션 내에 동일한 결과를 보장하지만, 새로운 레코드를 추가하거나 삭제하는 경우 부정합이 생길 수 있는데, 이를 유령 읽기(Phantom Read)라고 한다. MySQL의 경우 갭 락을 통해 해당 문제가 잘 발생하지 않는 것으로 알 고 있다.

• Read Committed 커밋된 데이터만 조회할 수 있어서 Non-Repeatable Read 문제도 발생하는데, 이는 동일 트랜잭션에서 반복 읽기를 수행했을 때 결과 값이 바뀌는 문제이다.

• Read Uncommitted 커밋하지 않은 데이터 조차 접근할 수 있는 격리 수준으로 Dirty Read가 발생한다.

특정 프로그램을 다른 곳으로 쉽게 옮겨서 설치 및 실행하기에 좋습니다.

• 위의 이식성 외에도 일관성(버전, 환경설정, 옵션, 운영체제 등)을 가집니다.

🐳 도커란?

컨테이너를 사용해서 각 프로그램을 분리된 환경에서 실행할 수 있도록 합니다.

이미지(Image)

컨테이너를 만드는 데 사용되는 읽기 전용(read-only) 템플릿이다. 컨테이너 실행에 필요한 Dockerfile을 빌드하여 이미지를 만듭니다.

컨테이너(Container)

도커 이미지를 실행시킨 상태입니다.

• 하나의 도커 이미지로 여러 개의 도커 컨테이너를 만들 수 있습니다.
• 컨테이너 하나를 미니 컴퓨터라고 볼 수 있고, 여러 컨테이너를 포함하고 있는 컴퓨터를 호스트(host) 컴퓨터라고 합니다.

📄 도커 기본 명령어

• docker [대상] [액션]
  • 대상: container(생략 가능), image, volume, network 등
  • 액션: ls, start, run 등

• docker pull [이미지]
  • 특정 이미지(도커 허브에 있는 이미지) 다운 받기
  • 디폴트는 latest 버전이고 [이미지명]:[태그명]으로 버전 지정

• docker image ls
  • 받은 이미지 확인하기
    • REPOSITORY : 이미지 명
      • TAG: 이미지 태그명 (버전)
    • IMAGE ID
    • CREATED: 이미지가 생성된 날짜
    • SIZE

• dokcer image rm -f [이미지 ID 또는 이미지명]
  • -f가 있으면 실행 중인 컨테이너를 강제로 삭제할 수 있다
• docker images -q
  • 시스템에 있는 모든 이미지 ID를 반환한다

• docker image rm -f $(docker images -q)
  • 사용하고 있지 않은 이미지 전체 삭제

• docker run [이미지 ID 또는 이미지명]
  • 로컬 이미지가 있다면 해당 이미지로 실행하고, 없으면 도커 허브에서 다운 후 실행
  • create + start: 컨테이너 생성 및 실행

• docker ps
  • 실행 중인 컨테이너들의 목록을 확인
  • docker container ls와 같음

• docker ps - a
  • 모든 컨테이너 조회

• docker stop [컨테이너 ID 또는 컨테이너명]

• docker kill [컨테이너 ID 또는 컨테이너명]

• docker run -d -p 8080:80 nginx
  • 호스트의 8080번 포트를 컨테이너의 80번 포트로 연결
  • localhost:8080으로 접속하면 nginx 서버 접속 가능
  • -d가 있으면 백그라운드에서 실행

• docker logs -f [컨테이너 ID 또는 컨테이너명]
  • 기존의 로그 + 실시간으로 쌓이는 로그 확인
  • -f : follow의 약어

• docker exec -it [컨테이너 ID 또는 컨테이너명] dash
  • 실행 중인 컨테이너에 접속
  • -it옵션을 적어야 계속 명령어 입력 가능

대량의 테이블에서 소량의 데이터를 검색할 때 속도를 향상시키는 자료구조입니다. 인덱스 기준으로 정렬하면 테이블 검색과 정렬 속도와 그에 따른 성능을 향상시킨다는 장점이 있습니다. 반면, 인덱스를 관리하는 데 추가적인 쓰기 작업과 데이터베이스의 약 10%에 해당되는 저장공간이 필요하다는 단점이 있습니다.

어떤 경우에 인덱스를 사용하면 좋을까요?

조금 극단적으로 1개의 데이터가 있는 테이블과 100만 개의 데이터가 있는 테이블이 있다고 했을 때, 100만 개의 데이터가 있는 테이블과 달리 1개의 데이터가 있는 테이블은 풀 스캔이 더욱 효율적입니다. 100만 개의 테이블일 때 인덱스를 통해 읽어 들이는 양이 많다면 디스크 I/O가 많이 발생하기 떄문에 처리 시간이 늦어질 수도 있습니다.

또한, DML 연산을 수행할 때 인덱스는 정렬되어 있는 상태를 유지한다는 특징을 가집니다. UPDATE와 DELETE 연산 시 기존 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해줍니다. INSERT와 UPDATE 연산 시 새로운 데이터에 대한 인덱스를 추가하며 정렬 연산이 이루어집니다.

결론적으로 규모가 작지 않은 테이블에서 DML 연산이 자주 발생하지 않는 칼럼, JOIN, WHERE이나 ORDER BY에 자주 사용되는 칼럼, 데이터의 중복도가 낮은 칼럼, 유니크한 값을 가지고 있는 칼럼 등의 경우에 인덱스를 사용하면 좋다는 것을 알 수 있습니다.

클러스터드 인덱스(Clustered Index)란?

데이터가 테이블에 물리적으로 저장되는 순서를 정한 인덱스입니다.

PK 설정 시 해당 칼럼으로 클러스터드 인덱스가 만들어집니다. PK의 특징과 같이, 테이블 당 1개씩만 허용되며 DML 연산 시 항상 정렬 상태를 유지하는 특징을 가지고 있습니다. 물리적으로 정렬되어 있어서 검색 속도는 빠르지만 DML 연산은 느립니다.

클러스터드 인덱스는 트리로 저장되어, Root 페이지와 Leaf 페이지(= 데이터 페이지)로 구성됩니다. 실제 행 데이터를 해당 열로 정한 후에 Root 페이지를 만들게 됩니다. Leaf 페이지에는 실제 데이터를, Root 페이지에는 Leaf 페이지의 주소로 구성되어 데이터를 검색할 때 Root 페이지를 통해 Leaf 페이지의 실제 데이터에 접근합니다.

DML 연산이 느려지는 이유는 리프 페이지가 모두 차있을 때 새로운 데이터가 들어오면 페이지 분할이 일어나며 데이터 페이지 전체를 다시 정렬해야 하기 때문입니다.

넌 클러스터드 인덱스(Non-Clustered Index)란?

클러스터드 인덱스와 달리 데이터의 행에 독립적이며 인덱스가 데이터에 함께 저장되는 것이 아니라 별도의 장소에 저장됩니다. 또한, 하나의 테이블에서 여러 개의 넌 클러스터드 인덱스를 설정할 수 있습니다.

인덱스 페이지의 Leaf 페이지가 Index로 구성한 칼럼과 위치 포인터(RID)로 구성됩니다(= Leaf 페이지가 정렬됨). 즉, 인덱스로 Leaf 페이지에 접근하면 Leaf 페이지의 RID 정보로 실제 데이터에 접근하게 됩니다(= 실제 데이터는 정렬되지 않음).

클러스터드 인덱스보다 거쳐야 하는 단계가 많아 검색 속도는 비교적 느리지만, DML 연산은 비교적 빠릅니다.

인덱스 알고리즘, B-Tree

데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되는 자료구조로 Balanced-Tree를 의미합니다.

노드 안 데이터는 정렬된 상태로 구성되며 항상 양쪽 자식의 밸런스를 유지하므로, 리프 노드가 모두 같은 레벨에 있는 특징을 가집니다. 따라서 검색에 걸리는 시간이 일정하다는 장점을 지닙니다: O(logN).

노드 하나에 여러 데이터가 저장될 수 있으며 데이터와 데이터 사이의 범위에 따라 자식 노드를 가집니다. 이때 자식 노드는 부모 노드의 (key 개수 + 1) 만큼의 노드 개수를 가지게 됩니다.

왜 B-Tree를 사용할까?

• 항상 정렬된 상태를 유지해서 부등호 연산에도 빠르게 탐색할 수 있다

• 하나의 노드에 여러 데이터를 담을 수 있어 빠른 메모리 접근이 가능하고 참조 포인터가 적다

탐색 시간이 가장 빠른 해시 테이블과 또 다른 밸런스 트리 중 RedBlack-Tree와 비교해보겠습니다.

해시 테이블에서 단 하나의 데이터를 탐색하는데 걸리는 시간이 O(1)입니다. 하지만, 우리는 데이터베이스에서 등호뿐 아니라 부등호도 사용할 수 있습니다.

즉, 해시 테이블에서는 값이 정렬되어 있지 않아서 특정 기준보다 작거나 큰 값을 찾기에 매우 비효율적입니다.

RedBlack-Tree는 하나의 노드에 하나의 데이터 요소만을 저장하지만, B-Tree는 하나의 노드에 여러 개의 데이터 요소를 저장합니다. 자식 노드로 접근할 때 참조 포인터로 접근을 하게 되는데 하나의 노드가 가지는 데이터 개수가 많아질수록 포인터 개수가 줄어들어서 B-Tree가 더 효율적입니다.

코딩테스트 연습 > GROUP BY > 언어별 개발자 분류하기

문제 설명

DEVELOPERS 테이블에서 GRADE별 개발자의 정보를 조회합니다.

GRADE는 다음과 같이 정해집니다.

• A : Front End 스킬과 Python 스킬을 함께 가지고 있는 개발자
• B : C# 스킬을 가진 개발자
• C : 그 외의 Front End 개발자

GRADE가 존재하는 개발자의 GRADE, ID, EMAIL을 조회하는 SQL 문을 작성해 주세요. 결과는 GRADE와 ID를 기준으로 오름차순 정렬합니다.

테이블 설명

SKILLCODES의 CODE와 DEVELOPERS의 SKILL CODE는 2진수로 표현했을 때 각 bit로 구분될 수 있도록 2의 제곱수로 구성되어 있습니다.

🔐 풀이

아이디어

답지를 참고했다..

비트 연산자(&)를 사용하여 developers의 skill_code와 skillcodes의 코드 값을 연산하여 0이 아닌 경우 GRADE를 부여합니다.

1. front end 역량이 있는 개발자 코드의 합을 구합니다.
2. null을 제외한 값을 출력해야하므로 가상테이블을 하나 더 만듭니다.

👉 제출 코드

with a as (
    select sum(code) code
    from SKILLCODES
    group by category
    having category = 'Front End'
), b as (
    select case 
        when skill_code & (select code from a)
            and skill_code & (select code from skillcodes where name = 'Python') then 'A'
        when skill_code & (select code from skillcodes where name = 'C#') then 'B'
        when skill_code & (select code from a) then 'C'
        end as grade,
        id, email
    from DEVELOPERS
    order by grade, id
)

select *
from b
where grade is not null

코딩테스트 연습 > GROUP BY > 특정 조건을 만족하는 물고기별 수와 최대 길이 구하기

문제 설명

FISH_INFO에서 평균 길이가 33cm 이상인 물고기들을 종류별로 분류하여 잡은 수, 최대 길이, 물고기의 종류를 출력하는 SQL문을 작성해주세요. 결과는 물고기 종류에 대해 오름차순으로 정렬해주시고, 10cm이하의 물고기들은 10cm로 취급하여 평균 길이를 구해주세요.

테이블 설명

id, parent_id 칼럼을 가지는데, 최초 대장균 개체의 parent_id는 NULL 값입니다.

🔐 풀이

아이디어

fish_type 별로 평균 길이를 구한다

• 이때 length가 null인 경우 10으로 계산한다 "IF문 사용"
• IF(조건문, 참일때 값, 거짓일 때 값)
• 평균 길이가 33cm 이상인 물고기들을 조회한다 "HAVING절 조건 걸기"

👉 제출 코드

select count(id) fish_count, max(length) max_length, fish_type
from fish_info
group by fish_type
having avg(if (length is null, 10, length)) >= 33
order by fish_type

코딩테스트 연습 > SELECT > 특정 세대의 대장균 찾기

문제 설명

3세대의 대장균의 ID(ID) 를 출력하는 SQL 문을 작성해주세요. 이때 결과는 대장균의 ID 에 대해 오름차순 정렬해주세요.

테이블 설명

id, parent_id 칼럼을 가지는데, 최초 대장균 개체의 parent_id는 NULL 값입니다.

🔐 풀이

아이디어

3세대 대장균의 아이디를 조회하면 되므로 1세대 대장균 > 2세대 대장균 > 3세대 대장균을 조인을 통해 순서대로 구해줍니다.

👉 제출 코드

with first_gen as (
    select id
    from ecoli_data
    where parent_id is null
), second_gen as (
    select e.id
    from first_gen join ecoli_data e
    on first_gen.id = e.parent_id
)

select e.id
from second_gen join ecoli_data e
on second_gen.id = e.parent_id
order by 1

프로그래머스 Lv5 멸종위기의 대장균 찾기(MySQL)

• 재귀 쿼리를 사용하여 각 세대를 구한다면 더 간단하게 풀이할 수 있습니다.

HTTP/1.0

한 연결당 하나의 요청을 처리해서 요청을 처리하기 위해서 커넥션을 계속 생성합니다.

💥 RTT 증가

서버에 접근할 때마다 3 way handshake를 합니다.

• RTT(Round Trip Time)란? syn을 보내고 syn+ack 받는 한 과정

해결 방법

• 이미지 스플리팅: 한번에 다운 받고 위치 조정
• 코드 압축 : 공백제거 등 용량을 줄임
• 이미지 Base64 인코딩: 이미지 자체를 인코딩시켜 서버와의 연결을 줄임

HTTP/1.1

keep-alive 옵션으로 TCP 초기화를 한 번만 해도 커넥션을 재사용할 수 있습니다. 커넥션이 되면 순차적으로 데이터를 요청하고 응답합니다.

💥 HOL(Head Of Line) Blocking

앞서 전송된 요청이 오래 걸리면 그 다음 요청의 응답이 늦어지는 문제가 발생합니다.

HTTP/2.0

⭐️ 멀티플래싱

여러 스트림으로 데이터를 요청하고 응답해서 병렬적으로 동시에 처리 가능합니다.

• HTTP의 HOLB 해결
• TCP 자체의 HOLB 미해결: 패킷이 유실되거나 오류가 있을 때 재전송하는데 이 재전송한 패킷에 지연이 발생하면 HOLB 문제가 발생합니다.

헤더 압축

• 허프만 코딩으로 HPACK 압축 형식
• 빈도가 높은 건 적은 비트 수로 저장
• header를 하나의 프레임으로 전송

서버 푸시

• 클라이언트 요청 없이 서버 측에서 리소스를 보낸다
• 예를 들어 html을 요청했을 때 html에다가 css 파일도 푸시

HTTPS

HTTP에 TLS 혹은 SSL을 사용하여 암호화된 버전입니다.

• 제 3자가 메세지를 도청하거나 변조하지 못하도록 하여 보안성을 높였습니다
• SEO(검색 엔진 최적화) 품질 증가에 도움이 됩니다

⭐️ 동작 방식

SSL 핸드쉐이크를 통해 대칭키를 생성합니다.

1. Client - Client Hello 아래의 정보를 서버에게 보낸다.
   • 브라우저가 사용하는 SSL 버전 정보
   • 브라우저가 지원하는 암호화 방식 모음(cipher suite)
   • 브라우저가 생성한 임의의 난수
2. Server - Server Hello
   • 서버가 선택한 암호화 방식(cipher suite)
   • 서버의 공개키가 포함된 SSL 인증서(CA의 비밀키로 암호화되어 발급된다)
   • 서버가 생성한 임의의 난수
3. Client - 서버의 SSL 인증서 확인
   • CA 공개키로 복호화하여 위조되지 않았는지 확인한다
4. Client - Premaster Secret 생성 클라이언트와 서버의 난수를 활용해서 Premaster Secret을 만들고 SSL 인증서에 있는 서버의 공개키로 암호화하여 이를 서버로 전송한다
5. Server - Premaster Secret 복호화 서버의 개인키(비밀키)를 활용하여 세션 키를 생성한다. 여기서 세션키가 HTTPS에서 사용되는 대칭키이고 이 세션키를 통해서 브라우저와 서버 간 데이터를 암복호화하여 주고 받는다
6. SSL Handshake 종료

HTTP/3

QUIC 기반 동작

TCP + TSL + HTTP 기능을 모두 구현한 프로토콜로 높은 성능과 신뢰성을 충족시킵니다. UDP 위에서 빌드됩니다.

RTT 감소

TCP 연결(1-RTT)에 TLS(2-RTT)를 이용해서 통신을 하면 총 3-RTT가 발생하였습니다. QUIC으로 통신을 시작할 때는 1-RTT만 소요됩니다. QUIC 내에 TLS 인증서를 내포하고 있기 때문에 최초 연결 과정에서 인증 정보와 데이터를 함께 전송하게 되기 때문입니다.

TCP의 HOLB 해결

스트림 자체를 독립적으로 여러개 나누어 처리하도록 하였습니다.

🍔 입력부터 렌더링 되기까지 절차

1. 사용자가 브라우저에 URL 주소를 입력한다.

2. URL 중에서 도메인 네임 부분을 DNS 서버에 검색한다.

3. DNS 캐싱을 활용하여 도메인 주소와 대응하는 IP 주소를 찾는다.

DNS 캐싱은 도메인 요청했다면 로컬 PC에 자동 저장되는 것을 말합니다. OS가 해당 도메인의 IP 주소를 확인하기 위해 가장 먼저 hosts 파일을 확인합니다.

4. 캐싱된 기록에 도메인 주소가 없다면 DNS Server가 계층적인 구조로 도메인 이름을 찾고 IP 주소로 변환한다.

DNS resolver가 root name server에서 top-level(.com)으로 second-level(.naver)으로 third-level(www) 순으로 요청합니다. 이후 도메인 이름에 따른 IP 정보를 획득합니다.

5. IP 라우팅을 통해 실제 서버를 찾는다.

ARP로 MAC addr을 획득합니다.

6. 브라우저는 서버와 TCP 연결한다.

https로 통신하므로 TCP 연결을 구축합니다. 해당 과정에는 3-way handshake와 TLS handshake가 포함됩니다. http/3인 경우에는 QUIC 기반이므로 TCP 연결을 따로 진행하지 않습니다(즉 http/2까지).

7. TCP 연결에 성공하면 브라우저가 웹 서버에게 http request를 보낸다.

8. WAS와 Database에서 웹 페이지 작업을 처리한다.

동적인 컨텐츠를 WAS에게 요청하고 컨텐츠를 다운로드 받습니다. 처음 다운로드 시작하는 것을 Time To First Byte라고 합니다.

9. 요청을 처리한 결과를 http response로 브라우저에게 전송한다.

웹 페이지, status code, 쿠키, 개인정보 등을 포함합니다.

10. 브라우저는 HTML을 렌더링하여 화면에 띄운다.

HTML/CSS/JS 및 이미지, 폰트 등 리소스를 페이지에 렌더링합니다. 서버와의 세션이 종료되면 4-way handshake로 종료합니다.

🍕 URI와 URL의 차이점

URI(Uniform Resource Identifier)

• www.naver.com
• 리소스의 이름만 나타냅니다

URL(Uniform Resource Locator)

• www.naver.com/user/1
• 자원의 위치 뿐만 아니라 자원에 대한 고유 식별자를 포함합니다
• URI의 하위 개념입니다

💻 문제

코딩테스트 연습 > SELECT > 대장균 크기에 따라 분류하기 2

• rank() 활용

문제 설명

대장균 개체의 크기(SIZE_OF_COLONY)를 내림차순으로 정렬했을 때 _상위 0% ~ 25% 를 'CRITICAL', 26% ~ 50% 를 'HIGH', 51% ~ 75% 를 'MEDIUM', 76% ~ 100% 를 'LOW' 라고 분류_합니다. 대장균 개체의 ID(ID) 와 분류된 이름(COLONY_NAME)을 출력하는 SQL 문을 작성해주세요. 이때 결과는 개체의 ID 에 대해 오름차순 정렬해주세요 .

테이블 설명

ID와 SIZE_OF_COLONY만을 활용합니다.

🔐 풀이

아이디어

RANK 함수를 활용하여 등수를 할당하고 등수를 전체 개수로 나눈 것에 100을 곱하여 퍼센트를 구합니다. 구한 퍼센트 정보에 따라 CASE WHEN으로 COLONY_NAME 값을 할당합니다.

👉 제출 코드

with t1 as (
    select id, size_of_colony, rank() over(order by size_of_colony desc) as ranking
    from ecoli_data
), t2 as (
    select id, size_of_colony, ranking, (ranking / (select count(*) from ecoli_data)) * 100 as per
    from t1
), t3 as (
    select id, size_of_colony, ranking, case 
        when per <= 25 then 'CRITICAL'
        when per > 25 and per < 50 then 'HIGH'
        when per > 50 and per <= 75 then 'MEDIUM'
        else 'LOW'
    end as colony_name
    from t2
)

select id, colony_name
from t3
order by id

🥑 순위함수

다른 순위함수를 알아보겠습니다.

NTILE()

지정된 수 만큼의 등급으로 나누어 각 등급의 번호를 출력합니다. 문제에서 총 데이터 수는 4의 배수라고 정의하였으므로 4만큼 등급을 나누어 아래와 같이 풀이할 수 있습니다.

with t1 as (
    select id, ntile(4) over (order by size_of_colony desc) as colony_level
    from ecoli_data
)

select id, case
    when colony_level = 1 then 'CRITICAL'
    when colony_level = 2 then 'HIGH'
    when colony_level = 3 then 'MEDIUM'
    else 'LOW'
    end as colony_name
from t1
order by 1

ROW_NUMBER()

동등 순위를 인식하지 않고 매번 증가되는 번호를 출력합니다. 1 2 3 4 5

DENSE_RANK()

동등 순위는 같게 나오고 그 다음 순위를 다음 번호로 출력합니다. 1 2 3 3 4

RANK()

동등 순위는 같게 나오고 그 다음 순위를 다음 번호를 뺀 그 다음 번호로 출력합니다. 1 2 3 3 5

💻 문제

코딩테스트 연습 > SELECT > 멸종위기의 대장균 찾기

• 재귀 쿼리 활용

문제 설명

각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력하는 SQL문을 작성해주세요. 이때 결과는 세대에 대해 오름차순 정렬해주세요. 단, 모든 세대에는 자식이 없는 개체가 적어도 1개체는 존재합니다.

테이블 설명

id, parent_id 칼럼을 가지는데, 최초 대장균 개체의 parent_id는 NULL 값입니다.

🔐 풀이

아이디어

세대 정보를 어떻게 관리할 수 있을까에 대해 찾아보다가 WITH RECURSIVE (재귀 쿼리) 찾았습니다.

WITH RECURSIVE로 초기 테이블을 작성하고, 내부에서 해당 테이블을 사용할 수 있으며 UNION을 사용해서 활용합니다.

-- 예시
with recursive tmp as (
    # Non-Recursive 문장
    select 1 as n
    union all -- **
    # Recursive 문장
    select n + 1
    from tmp -- 테이블 사용
    where n < 12 -- 정지 조건
)

select n
from recursive;

이를 사용하여 세대 값을 카운팅합니다. 초기조건은 parent_id가 null일 때 1세대로, 재귀 조건에서는 세대 값을 1씩 증가시켜줍니다.

이때, parent_id 칼럼도 사용해서 세대별 자식이 없는 parent_id를 식별해줍니다.

👉 제출 코드

with recursive tmp as (
    select id, parent_id, 1 as generation
    from ecoli_data
    where parent_id is null
    union all
    select s.id, s.parent_id, tmp.generation + 1
    from tmp join ecoli_data s
    on tmp.id = s.parent_id
)

select count(*) count, generation
from tmp
where id not in (
    select distinct parent_id
    from tmp
    where parent_id is not null)
group by generation
order by 2

일반 연습 > 기출 문제 > 술레잡기

• 삼성 SW 역량테스트 2022 상반기 오전 1번 문제
• 시뮬레이션

🔐 풀이

• 시간: 2시간 20분

아이디어

이 문제의 핵심은 아무래도 술래를 달팽이 모양으로 옮기는 데 있습니다.

시간에 따라서 위치를 바뀌므로 값을 전역변수로 두고 계속 갱신해주는 방법으로 접근했습니다.

규칙적으로 돌아가는데 그게 아닌 예외 경우를 조건 처리해서 값을 할당해주었습니다. 예외 처리해야하는 부분은 방향이 바뀌는 부분으로 조금 수학적으로 접근해보았습니다.

예외의 경우는 (0, 0) (N/2, N/2) 좌표와 제 1사분면에서 y = x + 1을 만족하는 좌표 그리고 제 2, 4사분면에서 x + y = N-1을 만족하는 좌표, 제 3사분면에서 y = x를 만족하는 좌표 이렇게 접근해주었습니다.

이 밖에 코드 리뷰를 통해서 술래의 위치를 관리해주는 방법을 깨달았습니다. 비슷한 맥락으로 어차피 술래가 가는 곳은 정해져있으니 미리 K만큼 (2차원 배열이나 Queue 등에) 저장해두고 시간에 맞춰서 꺼내쓰는 방법입니다. K의 범위가 100 이하이기 때문에 시간에서도 문제가 없을 것이라 생각합니다.

추가로 저는 도망자의 정보를 정적인 배열로 관리해주었기 때문에 도망자의 구조체에 alive 변수를 추가하여 잡혔는지 아닌지에 대한 정보를 관리하였고 이동할 때나 술래잡기할 때 잡혔는지 여부에 대한 정보를 확인하고 처리해주었습니다.

시간복잡도

K번 동안 술래와 도망자가 이동하는데 술래는 O(1)이고 도망자는 M명이므로 O(M)입니다.

O(KM)

👉 제출 코드

import java.util.*;
import java.io.*;
public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int ans;
    static int N, M, H, K; // n은 홀수
    static boolean[][] trees;
    static Node[] people;
    static int X, Y, D; // 술래의 위치
    static boolean reverse; 
    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());
        H = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        trees = new boolean[N][N];
        people = new Node[M];
        X = N / 2; Y = N / 2;
        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 tmp = Integer.parseInt(st.nextToken());
            // 도망자 종류 두 가지
                // 좌우로 움직이는 사람 오른쪽 보고 시작
                // 상하로 움직이는 사람 아래 보고 시작
            int d = tmp == 1 ? 1 : 2;
            people[i] = new Node(x, y, d, true);
        }
        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            trees[x][y] = true;
        }
        // 나무랑 도망자 중복 위치 가능

        for (int i = 0; i < K; i++) {
            for (int j = 0; j < M; j++) {
                // 술래와 거리가 3 이하이고 살아있는 도망자에 대해서
                if (people[j].alive && getDist(X, people[j].x, Y, people[j].y) <= 3) {
                    moveRunner(j);
                }
            }
            moveIt();
            go(i+1);
        }
        System.out.println(ans);
    }
    public static void moveRunner(int num) {
        // 바라보고 있는 방향으로 1칸 이동
        Node p = people[num];
        int nx = p.x + dx[p.d];
        int ny = p.y + dy[p.d];
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
            p.d = (p.d + 2) % 4; // 방향 바꾸기
            nx = p.x + dx[p.d];
            ny = p.y + dy[p.d];
            if (X == nx && Y == ny) return;
            p.x = nx; p.y = ny; // 술래 없을 때 이동
        } else {
            if (X == nx && Y == ny) return;
            // 술래 없을 때 이동 (나무 있어도)
            p.x = nx; p.y = ny;
        }
    }
    public static void moveIt() {
        // 시간을 기준으로 위치가 바뀜 -> 값을 할당하자 즉, 움직이고 해당 위치에 대해 방향 갱신하여 관리
        X += dx[D];
        Y += dy[D];
        // 이동 후 방향 틀어지는 지점이면 방향을 바로 틀어줌
        if (X == N / 2 && Y == N / 2) {
            D = (D + 2) % 4;
            if (reverse) reverse = !reverse;
        } else if (X == N/2-1 && Y == N /2 ) {
            if (reverse) {
                D = (D - 1 + 4) % 4;
            } else {
                D = (D + 1) % 4;
            }
        } else if (X == 0 && Y == 0) {
            D = (D + 2) % 4;  // 반대 방향
            reverse = true;
        } else if (X >= N / 2 || Y >= N / 2) {
            if (X == Y || X + Y == N -1) {
                // 2, 3, 4사분면에 대해서
                if (reverse) {
                    D = (D - 1 + 4) % 4;
                } else {
                    D = (D + 1) % 4;
                }
            }
        } else if (X < N /2 && Y < N / 2) {
            // 1사분면
            if (X + 1 == Y) {
                if (reverse) {
                    D = (D - 1 + 4) % 4;
                } else {
                    D = (D + 1) % 4;
                }
            }
        }
        // 이외의 경우는 방향 유지
    }
    public static void go(int turn) {
        int runnerCnt = 0; // 잡힌 도망자 개수
        // 술래가 바라보고 있는 방향으로 3칸
        List<int[]> checkPoint = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            int nx = X + dx[D] * i;
            int ny = Y + dy[D] * i;
            // 범위 밖 확인 + 나무가 있는 칸은 안 보임
            if (nx < 0 || nx >= N || ny < 0 || ny >= N || trees[nx][ny]) continue;
            checkPoint.add(new int[] {nx, ny});
        }
        // 술래 개수 세고 잡기
        for (int i = 0; i < checkPoint.size(); i++) {
            int[] pos = checkPoint.get(i);
            for (int num = 0; num < M; num++) {
                if (people[num].alive && people[num].x == pos[0] && people[num].y == pos[1]) {
                    runnerCnt++;
                    people[num].alive = false;
                }
            }
        }
        ans += turn * runnerCnt;
    }
    public static int getDist(int x1, int x2, int y1, int y2) {
        return Math.abs(x1-x2) + Math.abs(y1-y2);
    }
    static class Node {
        int x, y, d;
        boolean alive;
        Node (int x, int y, int d, boolean alive) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.alive = alive;
        }
        @Override
        public String toString() {
            return x + " " + y + " " + d;
        }
    }
}

일반 연습 > 기출 문제 > 싸움땅

• 삼성 SW 역량테스트 2022 하반기 오전 1번 문제
• 시뮬레이션

🔐 풀이

아이디어

이 문제의 핵심은 사람의 위치를 잘 추적하는 것이라고 생각합니다. 6번 테스트케이스에서 막혀서 꽤 오랜 시간을 썼는데 디버깅해보니 사람의 위치가 중복되어서 먹히는 부분을 발견하였습니다.

즉, 기존의 위치와 움직일 위치의 상태를 잘 관리해주는 것이 중요했습니다. 이를 중복적으로 검사하는 과정에서 다소 불필요한 코드가 있을 수 있습니다.

사람은 한 칸에 두 명 이상 저장되는 경우는 없으므로(부딪혀도 싸운 후에 결국 한 칸당 한 명 위치하게 됩니다) 2차원 배열 map과 사람 정보(Player)를 1차원 배열로 관리하였습니다.

반면, 총은 한 곳에 두 개 이상이 될 수 있고 공격력이 가장 쎈 총을 주워가는 과정에서 정렬을 사용해야 하기 때문에 List로 구성된 2차원 배열로 운영하였습니다.

이외에 필자가 삽질한 부분 🥲

1. 움직일 수 있을 때까지 90도로 계속 회전

• next dir는 for문을 통해 간단히 구현할 수 있습니다.
• 회전하다가 빈칸인 순간 이동하면 break를 통해 종료합니다.

2. List를 내림차순으로 정렬

• Collections.reverse()가 내림차순인 줄 알고 있었습니다..
• 내림차순 정렬은 Collections.sort(, Collections.reverseOrder())

시간복잡도

라운드 k 동안 m명의 플레이어가 이동하며 총을 줍거나 싸웁니다. n개의 총 개수가 필요시 정렬됩니다.

O(k * m * nlog(n))으로 추정

👉 제출 코드

import java.util.*;
import java.io.*;
public class Main {
    // 상 우 하 좌 (오른쪽 90도로 회전, 방향 바꾸기)
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[] ans;
    static int n, m, k;
    // guns 정보 관리
    static List<Integer>[][] guns;
    // player 정보 관리
    static Player[] players;
    static int[][] map;
    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());
        k = Integer.parseInt(st.nextToken());
        // 총 정보 저장
        guns = new ArrayList[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                guns[i][j] = new ArrayList<>();
            }
        }
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                guns[i][j].add(Integer.parseInt(st.nextToken()));
            }
        }
        // 플레이어 정보 저장
        players = new Player[m+1];
        map = new int[n][n];
        for (int i = 1; i < m+1; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            int d = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            players[i] = new Player(x, y, d, s, 0);
            map[x][y] = i;
        }
        ans = new int[m+1];
        for (int round = 0; round < k; round++) {
            // 1 ~ n번 플레이어 순서대로
            for (int i = 1; i < m+1; i++) {
                move(i);
                if (!existPlayer(i)) {
                    getGuns(i);
                } else {
                    fight(i);
                }
            }
        }
        for (int i = 1; i < m+1; i++) {
            System.out.print(ans[i] + " ");
        }
        System.out.println();
    }
    public static void fight(int i) {
        Player p1 = players[i];
        int j = map[p1.x][p1.y];
        Player p2 = players[map[p1.x][p1.y]];
        int s1 = p1.cap + p1.gun;
        int s2 = p2.cap + p2.gun;
        // 초기 능력치 + 총의 공격력 비교하여 싸움
        // 값이 같으면 높은 초기 능력치를 가진 사람이 이김
        int win = 0; int L = 0;
        if (s1 == s2) {
            if (p1.cap > p2.cap) {
                win = i;
                L = j;
            }
            else {
                win = j;
                L = i;
            }
        } else if (s1 > s2) {
            win = i;
            L = j;
        } else {
            win = j;
            L = i;
        }
        // 이긴 플레이어는 각 플레이어의 (초기 능력치 + 총의 공격력)의 차이만큼 포인트 획득
        ans[win] += Math.abs(s1-s2);

        // 진 플레이어는 총을 해당 격자에 내려두고 원래 가진 방향으로 한 칸 이동
        Player loser = players[L];
        guns[loser.x][loser.y].add(loser.gun);
        players[L].gun = 0;
        move2(L);
        // 이긴 플레이어는 승리한 칸에 있는 총 중 가장 높은 공격력을 가진 총 획득하고 나머지는 그대로
        getGuns(win);
    }
    public static void move2(int num) {
        Player p = players[num];
        // 본인이 향하고 있는 방향대로 한 칸 이동
            // 다른 플레이어가 있거나 격자 범위 밖이면
            // 오른쪽으로 90도 회전하여 빈칸 보이는 순간 이동
        for (int i = 0; i < 4; i++) {
            int nd = (p.dir + i) % 4;
            int nx = p.x + dx[nd];
            int ny = p.y + dy[nd];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] != 0) continue;
            else {
                p.dir = nd;
                map[p.x][p.y] = 0; // 원래 잇던 곳
                p.x = nx; p.y = ny;
                map[p.x][p.y] = num; // 일하는 곳
                break;
            }
        }
        // 이동 후 총 있으면  (2-1) 동작
        getGuns(num);
    }
    public static void move(int num) {
        Player p = players[num];
        // 본인이 향하고 있는 방향대로 한 칸 이동
        int nx = p.x + dx[p.dir];
        int ny = p.y + dy[p.dir];
        // 격자를 벗어나는 경우 정반대로 방향 바꾸어 이동
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
            int nd = (p.dir + 2) % 4;
            nx = p.x + dx[nd];
            ny = p.y + dy[nd];
            p.dir = nd;
        }
        // player 정보 업데이트
        map[p.x][p.y] = 0;
        p.x = nx; p.y = ny;
        // map[p.x][p.y] = num; // 이건 있는지 확인하고 난 후
    }
    public static void getGuns(int k) {
        // 총 있다면 총 획득
        Player p = players[k];
        if (guns[p.x][p.y].size() != 0) {
            Collections.sort(guns[p.x][p.y], Collections.reverseOrder());
            // System.out.println(guns[p.x][p.y]);
            if (p.gun == 0) {
                p.gun = guns[p.x][p.y].get(0);
                guns[p.x][p.y].remove(0);
            } else {
                // 더 공격력이 센 총을 획득하고 원래 가지고 있던 건 그 자리에 둠
                if (p.gun < guns[p.x][p.y].get(0)) {
                    int tmp = guns[p.x][p.y].get(0);
                    guns[p.x][p.y].remove(0);
                    guns[p.x][p.y].add(p.gun);
                    p.gun = tmp;
                }
            }
        }
        // 플레이어 정보 업데이트
        map[p.x][p.y] = k;
    }
    public static boolean existPlayer(int k) {
        // 해당 칸에 플레이어가 있는지 확인
        Player p = players[k];
        return map[p.x][p.y] != 0;
    }
    static class Player {
        int x, y, dir;
        int cap;
        int gun;
        Player(int x, int y, int dir, int cap, int gun) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cap = cap;
            this.gun = gun;
        }
    }
}

일반 연습 > 기출 문제 > 왕실의 기사 대결

• 삼성 SW 역량테스트 2023 하반기 오전 1번 문제
• 시뮬레이션, 너비 우선 탐색

🔐 풀이

아이디어

이 문제의 핵심은 명령 받은 기사가 움직일 때 이동하려는 위치에 다른 기사가 있다면 연쇄적으로 밀려나가는 부분을 구현하는 것이었다고 생각합니다.

연쇄적으로 움직일 수 있는지 확인하기 위해 기사들의 방패 영역을 인덱스로 관리하는 2차원 배열 loc을 활용하였습니다.

추가로 bfs로 움직이게 되는 기사를 탐색하는 동시에 moved라는 Stack을 만들어서 연쇄적으로 움직이는 기사의 인덱스를 저장하여 관리하였습니다. Stack의 LIFO 특징 사용하여 loc 배열을 편리하게 업데이트해주었습니다.

시간복잡도

Q번 동안 기사 별로 이동 가능 여부를 검사하고 이동 후의 상태를 갱신합니다.

O(Q * N^2)

추가사항

아래 코드에서 AutoUnBoxing & AutoBoxing이 적용되고 있습니다.

• 기본 자료형과 Wrapper 클래스 간에는 서로 암묵적 형변환이 가능합니다.

👉 제출 코드

import java.util.*;
import java.io.*;
public class Main {
    // 상 우 하 좌
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map; // 체스판
    static int[][] loc;// 기사 위치 기반 number 할당 : 밀리는지 여부 판단하기 위함
    static K[] knights;
    static int[] damages;
    static int L, N, Q;
    static Stack<Integer> moved; // LIFO!!
    static Queue<Integer> q;
    static void go(int idx, int dir) {
        if (knights[idx].cnt > 0) {
            bfs(idx, dir);
            update(idx, dir);
        } else {
            return;
        }
    }
    static void calc() {
        int ans = 0;
        for (int i = 1; i < N+1; i++) {
            if(knights[i].cnt > 0) {
                ans += damages[i];
            }
        }
        System.out.println(ans);
    }
    static void update(int order, int dir) {
        while(!moved.isEmpty()) {
            Integer idx = moved.pop();
            K cur = knights[idx];
            // 옮기기 전 위치 없애기
            remove(cur);
            // knights update
            cur.x += dx[dir];
            cur.y += dy[dir];
            // 옮긴 거 갱신 + 대미지 입히기
            int damage = 0;
            for (int i = cur.x; i < cur.x + cur.h; i++) {
                for (int j = cur.y; j < cur.y + cur.w; j++) {
                    loc[i][j] = idx;
                    // 명령받은 기사는 대미지 안 받음
                    if (order != idx && map[i][j] == 1) damage++;
                }
            }
            if (cur.cnt > damage) {
                cur.cnt -= damage;
                damages[idx] += damage;
            } else {
                cur.cnt = 0;
                remove(cur);
            }
        }
    }
    static void remove(K cur) {
        // loc에서 기사 넘버 없애기
        for (int i = cur.x; i < cur.x + cur.h; i++) {
            for (int j = cur.y; j < cur.y + cur.w; j++) {
                loc[i][j] = 0;
            }
        }
    }
    static void bfs(int idx, int dir) {
        moved = new Stack<>();
        q = new ArrayDeque<>();
        q.add(idx);
        while (!q.isEmpty()) {
            Integer kk = q.poll();
            moved.add(kk); // 움직이는 대상이 되는 기사 저장
            if (!canMove(kk, dir)) {
                moved = new Stack<>();
                return;
            }
        }
    }
    static boolean canMove(Integer idx, int dir) {
        K cur = knights[idx];
        for (int i = cur.x; i < cur.x + cur.h; i++) {
            for (int j = cur.y; j < cur.y + cur.w; j++) {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if (nx < 0 || nx >= L || ny < 0 || ny >= L || map[nx][ny] == 2) return false;
                if (loc[nx][ny] == idx) continue; // 원래 기사의 영역인 경우
                if (loc[nx][ny] != 0) {
                    if (!q.contains(loc[nx][ny])) q.add(loc[nx][ny]);
                }
            }
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken()); // 체스판 크기
        N = Integer.parseInt(st.nextToken()); // 기사 수
        Q = Integer.parseInt(st.nextToken()); // 명령 수
        map = new int[L][L];
        loc = new int[L][L];
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < L; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        knights = new K[N+1];
        for (int i = 1; i < N+1; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken()); // 초기 체력
            knights[i] = new K(r, c, h, w, k);
            for (int x = r; x < r + h; x++) {
                for (int y = c; y < c + w; y++) {
                    loc[x][y] = i;
                }
            }
        }
        damages = new int[N+1];
        // 왕이 특정 기사에게 명령을 내린다
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken()); // 기사 number
            int d = Integer.parseInt(st.nextToken());
            go(idx, d);
        }
        // 대결이 끝나고 생존한 기사들이 받은 대미지의 합
        calc();
    }
    static class K {
        int x, y;
        int h, w;
        int cnt; // 대미지
        K(int x, int y, int h, int w, int cnt) {
            this.x = x;
            this.y = y;
            this.h = h; // 세로
            this.w = w; // 가로
            this.cnt = cnt;
        }
    }
}

천재지변으로 인해 일부 데이터가 유실되었습니다. 입양을 간 기록은 있는데, 보호소에 들어온 기록이 없는 동물의 ID와 이름을 ID 순으로 조회하는 SQL문을 작성해주세요.

✏️ 풀이

• 두 테이블 조인하기
  • 외래키인 ANIMAL_ID를 기준으로
  • 필자는 NAME으로 했다가 헤맴
• 조인은 INNER JOIN과 OUTER JOIN으로 나뉨
  • ANIMAL_INS에서 유실된 거니까 ANIMAL_OUTS 쪽으로 OUTER 조인
  • 필자는LEFT (OUTER) JOIN 사용
• 유실 조건은 ANIMAL_INS에 ANIMAL_ID가 없을 때
• 문제 조건에 맞게 정렬

👉 제출 코드

SELECT O.ANIMAL_ID, O.NAME
FROM ANIMAL_INS I RIGHT JOIN ANIMAL_OUTS O
ON I.ANIMAL_ID = O.ANIMAL_ID
WHERE I.ANIMAL_ID IS NULL
ORDER BY 1

FOOD_PRODUCT와 FOOD_ORDER 테이블에서 생산일자가 2022년 5월인 식품들의 식품 ID, 식품 이름, 총매출을 조회하는 SQL문을 작성해주세요. 이때 결과는 총매출을 기준으로 내림차순 정렬해주시고 총매출이 같다면 식품 ID를 기준으로 오름차순 정렬해주세요.

✏️ 풀이

• 두 테이블 조인하기
• 생산일자가 2022년 5월인 식품들 추출
• 총매출은 모든 식품 가격 * 주문량의 합
• 문제 조건에 맞게 정렬

👉 제출 코드

SELECT P.PRODUCT_ID, P.PRODUCT_NAME, SUM(P.PRICE * O.AMOUNT) AS TOTAL_SALES
FROM FOOD_PRODUCT P JOIN FOOD_ORDER O
ON P.PRODUCT_ID = O.PRODUCT_ID
WHERE O.PRODUCE_DATE LIKE '2022-05%'
GROUP BY PRODUCT_ID
ORDER BY 3 DESC, 1

✏️ 풀이

• 세 테이블 조인하기
• 조건 1: 자동차 종류가 '세단' 또는 'SUV'

  CAR_TYPE IN ('세단', 'SUV)

• 조건 2: 2022년 11월 1일부터 2022년 11월 30일까지 대여 가능
  • 해당 기간에 대여 중이면 안 됨
  • 예외 처리
    • 대여 시작일 또는 대여 종료일이 해당 기간 안에 있는 경우
    • 대여 시작일이 범위 시작 이전이고 대여 종료일이 범위 끝 이후인 경우
• 조건 3: 30일간 대여 금액(할인 적용 금액)이 50만원 이상 200만원 미만

  DURATION_TYPE = '30일 이상' AND ROUND(DAILY_FEE * (1 - DISCOUNT_RATE / 100) * 30) BETWEEN 500000 AND 2000001

👉 제출 코드

SELECT DISTINCT(C.CAR_ID), C.CAR_TYPE, ROUND(DAILY_FEE * (1 - DISCOUNT_RATE / 100) * 30) AS FEE
FROM CAR_RENTAL_COMPANY_CAR C
JOIN CAR_RENTAL_COMPANY_RENTAL_HISTORY H
ON C.CAR_ID = H.CAR_ID
JOIN CAR_RENTAL_COMPANY_DISCOUNT_PLAN P
ON C.CAR_TYPE = P.CAR_TYPE
WHERE C.CAR_TYPE IN ('세단', 'SUV')
AND C.CAR_ID NOT IN (SELECT CAR_ID
                    FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY
                    WHERE START_DATE BETWEEN '2022-11-01' AND '2022-11-30 59:59:59'
                    OR END_DATE BETWEEN '2022-11-01' AND '2022-11-30 59:59:59'
                    OR START_DATE <= '2022-11-01' AND END_DATE >= '2022-11-30') # **
AND P.DURATION_TYPE = '30일 이상'
AND ROUND(DAILY_FEE * (1 - DISCOUNT_RATE / 100) * 30) BETWEEN 500000 AND 2000001 # 이상 이하
ORDER BY 3 DESC, 2, 1 DESC