• S와 T 두 문자열이 주어짐.
• 두 문자열은 모두 A, B로만 이루어져 있고, 다음 두 연산을 사용할 수 있음.
  1. 문자열 뒤에 A를 추가
  2. 문자열 뒤에 B를 추가하고, 문자열 전체를 뒤집음
• 이 연산을 여러 번 사용해서 문자열 S를 문자열 T로 만들 수 있으면 1, 없으면 0을 출력하는 문제

// [input]
A // S
BABA // T

// [output]
1 // or 0

2. 스크래치

정방향 (S → T)

• 정방향은 길이를 1씩 늘리는 방법
• 매 단계마다 2개의 선택지가 있음 1) 뒤에 A를 붙이기 or 2) 뒤에 B를 붙이고 뒤집기
• S의 길이가 n, T의 길이가 m이면 총 m-n번 연산을 해야 함 ⇒ 가능한 연산 수 2^(m-n)
• • 문자열 뒤집는 연산
• 모든 경우를 만들어 보는 방법(완전 탐색)은 시간/ 메모리적 한계

역방향 (T → S)

• 역방향은 매번 길이를 1씩 줄임
• 역연산의 조건 1) 끝이 A일 때만 마지막 A 제거 2) 시작이 B일 때만 첫 B 제거 후 뒤집기 기능
• 메 단계마다 2가지 경우가 아니라, 조건이 맞을 때만 연산 수행 가능
• 역방향 풀이가 유리한 이유?
  • 깊이가 최대 m-n으로 고정됨 (길이가 계속 줄어듦)
  • 항상 2가지 경우가 아닌 조건부이므로 분기가 줄어듦
  • 중복 문자열은 visited로 차단 가능
  • DFS/ BFS로 T를 S 길이까지 줄여서 같아지는지 검사

3. 풀이

주요 로직

역방향으로 문자열(cur)을 한 단계씩 검사

• cur의 마지막 글자가 A라면 (….A) → 정방향 연산에서 A를 붙였던 경우이므로 마지막 A를 제거
• cur의 첫 글자가 B라면 (B…..) → 정방향 연산에서 뒤에 B를 붙이고 뒤집었던 경우이므로 첫 글자 B를 지우고 뒤집어서 다시 복구
• 길이가 1씩 줄어들으므로 DFS / 백트래킹으로 T를 S 길이까지 줄이며 확인하기

4. 코드

주요 로직

1) 전역 변수: visited

static Set<String> visited = new HashSet<>();

• Set 타입: 같은 값 중복 저장 X → 이미 값이 들어있는지를 O(1)로 빠르게 연산 가능
• DFS를 돌 떄 같은 문자열 상태가 나오면 함수 실행을 막음
• 현재 문자열 cur 상태에서 가능한 연산을 visited에 저장 → 같은 cur이 나오면 계속 볼 필요 X

2) dfs 탈출조건

• (1) 전역 변수 found가 true인 경우 S와 길이가 같고, 값이 같을 때
• (2) !visited.add(cur) 이
• (3) 길이가 S와 같아질 경우 더 줄이면 길이가 달라져 절대 S가 될 수 없음

public class Main {
    static String S,T;
    static Set<String> visited = new HashSet<>();
    static boolean found = false;
    public static void main(String[] args) throws IOException {

        // [input]
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = br.readLine().trim();
        T = br.readLine().trim();

        // [logic]
        dfs(T);

        // [output]
        System.out.println(found?1:0);

    }

    static void dfs(String cur) {
        if(found) return;

        if (visited.contains(cur)) return;
        visited.add(cur);

        if(cur.length() == S.length()) {
            if(cur.equals(S)) found = true;
            return;
        }

        // 마지막 글자가 A이면
        if(cur.charAt(cur.length()-1)=='A') {
            dfs(cur.substring(0,cur.length()-1)); // 마지막 글자 A 지우고 다시 탐
        }

        // 첫 글자가 B이면
        if(cur.charAt(0)=='B') {
            String trimmed = cur.substring(1); // == substring(1,cur.length())
            String next = new StringBuilder(trimmed).reverse().toString();
            dfs(next);
        }
    }
}

5. De-fault

1) visited 배열이 왜 필요한가?

• 길이가 매번 1씩 줄어들면서 서로 다른 경로로 줄여오다가 같은 문자열 상태인 경우가 생김
• visited가 없으면 해당 문자열에서 시작되는 하위 탐색을 똑같이 수행하기 때문에 낭비가 커짐
• 역 연산은 2가지 방법이 가능 (끝이 A일 경우, B로 시작하는 경우)
• 어떤 문자열은 두 조건을 동시에 맞목할 수 있고, 두 연산을 다른 순서로 적용하면서 내려오다 보면 결과가 같은 문자열로 합쳐질 수 있음
• Set 자료 구조 이용 visited는 이미 탐색한 문자열 상태를 저장해두고, 같은 cur가 다시 나오면 재탐색을 막는 가지치기 용도 → 방문 여부 확인 & 없으면 기록하는 데 평균적으로 빠른 자료구조는 HashSet

e.g. BAA

[1]
BAA -> BA (끝이 A)
BA -> A (B제거 후 뒤집기)

[2] 
BAA -> AA (B제거 후 뒤집기)
AA -> A (끝이 A)

2) StringBuilder를 사용하는 이유

• String은 immutable이므로 문자열을 뒤집거나 붙이는 작업을 String으로 처리하면 내부적으로 새 문자열이 계속 만들어져 비용이 커질 수 있음
• StringBuilder는 mutable이라서 내부 버퍼에서 문자를 처리하여 reverse() 같은 연산을 효율적으로 수행할 수 있음

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요. 알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂

• 주어진 N 길이의 수열에서 같은 숫자가 K번 이하로만 나오도록 하는 가장 긴 부분 수열의 길이를 구하는 문제
• ⇒ 같은 값이 K번 이하로만 등장하도록 유지하면서 연속 구간을 최대로 늘리는 문제*
• [제약 조건] 연속 조건 & 등장 횟수

// [input]
9 2 // N K
1 1 2 1 2 2 1 1 2 // 수열

2. 스크래치

0) 문제 풀이

• 문제 유형: 투 포인터
• 각 숫자의 등장 횟수를 관리해야 하므로 빈도수 배열 / 맵을 사용
• right 포인터로 구간을 확장하며 숫자 등장 횟수를 카운팅
• 어떤 숫자의 빈도가 K를 초과하면 left포인터를 이동시키면서 초과한 숫자를 줄임
• 구간 길이 갱신

3. 풀이

주요 알고리즘

• 슬라이딩 윈도우 (투 포인터) + 빈도 카운팅

문제 쪼개기

1. freq[x] 배열을 입력값 최대의 크기로 설정
2. left, right 포인터를 0에서 시작
3. right를 0 ~ N-1까지 1씩 늘리며 구간 확인 [left, right]
   • 숫자의 등장 횟수를 카운팅: freq[x]로 현재 구간에서 x가 몇 번 나왔는지 카운팅
   • K를 초과하면 left를 이동시키며 등장횟수를 -1
4. 조건을 만족하는 구간의 길이 갱신하기 (right - left + 1)
5. right가 끝까지 이동할 때까지 반복

4. 코드

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

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

        // [input]
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = 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());
        }

        // [logic]
        // 입력값의 크기의 카운팅 배열 만들기
        int[] freq = new int[100001];
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < N; right++) {
            freq[arr[right]]++;

            // 겹치는 원소가 K개를 초과하면
            while (freq[arr[right]] > K) {
                freq[arr[left]]--;
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        System.out.println(maxLen);
    }
}

5. De-fault

freq[arr[right]]++;

while (freq[arr[right]] > K) {
    freq[arr[left]]--;
    left++;
}

• right를 하나씩 늘리면서 구간 [left, right] 안에 포함된 원소들의 등장 횟수를 freq에 기록한 후, 어떤 값 x가 K을 초과하여 등장했을 때 로직을 처리하는 부분이 어려웠음.
• 처음에 직관적으로는 ‘K번 횟수를 넘긴 그 값이 있는 위치를 찾아서 그 원소가 K번 이하로 나와야 하는게 아닌가?’라는 생각이 들었음
• 왜 left를 오른쪽으로 한 칸씩 밀어야 하는가? 연속 부분 수열을 유지하면서 조건을 만족시키는 유일한 축소 방법이기 때문
• 문제의 핵심은 연속 부분 수열(구간)만 허용하는 점임. right를 하나 늘렸을 때 freq[arr[right]] > K 이면 해당 구간은 조건을 위반한 상태가 됨.
• 연속 구간을 유지하면서 이 위반 상태를 없애는 방법은 왼쪽 포인터 left를 오른쪽으로 밀면서, 하나씩 구간 밖으로 내보내는 것
• 중간에 있는 원소를 선택해 빼버리면 연속 부분 수열이 아니게 되기 때문에 오직 left ++를 통해서 구간을 줄일 수 있음 왼쪽으로 계속 밀다 보면 언젠가는 K번의 등장 횟수를 초과한 원소와 같은 값 하나가 잘려나감
• 이 시점에 freq[arr[right]] 이 다시 K이하로 떨어지고 해당 구간은 조건을 반족하게 됨 이 때 이 순간의 구간길이 right - left + 1 max 값 갱신

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요. 알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂

• 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시

문제 조건

• 속한 노래가 많이 재생된 장르를 먼저 수록함. (장르별 재생 횟수 내림차순)
• 장르 내에서 많이 재생된 노래를 먼저 수록함. (노래 재생 횟수 내림차순)
• 장르 내에서 재생 횟수가 같은 노래들은 고유 번호가 낮은 노래를 먼저 수록함.(재생 횟수 비교 -> 노래 id 비교)

  genres: ["classic", "pop", "classic", "classic", "pop"]    
  plays:    [500, 600, 150, 800, 2500]
  return: [4, 1, 3, 0]

2. 스크래치

풀이: 해시맵 (Hash Map)

0) Song 클래스 정의

1) [for문] 장르별 총 재생 횟수 & 각 장르별 노래 목록 정리 (장르 내부 정렬)

• 장르별 총 재생수 계산 genrePlayMap: Map<String, Integer> 타입에 <장르, 재생 횟수> 값 담기
• 장르별 노래 목록 정렬 genrePQMap: Map<String, PriorityQueue<Song> 타입에 <장르, 장르별 노래 목록의 PQ> 값 담기

2) 장르 순서 정렬 (장르 <-> 장르)

• genrePlayMap의 keySet을 통해 장르들의 키 값을 ArrayList로 감싸List<String> genreOrder에 담기
• sort 함수를 통해 내림차순하여 인기 장르부터 순서대로 정렬

3) 장르 순서대로 상위 2곡씩 꺼내기

• 결과를 담을 List<Integer> result 선언
• List<String> genreOrder를 for문으로 순회하며 각 장르의 pq에서 2번씩 poll
• List<Integer> result를 stream을 통해 int[] 배열로 만들기
  

3. 코드

import java.util.*;

class Solution {

    // 0. Song 클래스 정의 
    static class Song {
        int id;
        int plays;

        Song(int id, int plays) {
            this.id = id;
            this.plays = plays;
        }
    }

    public int[] solution(String[] genres, int[] plays) {

        Map<String, Integer> genrePlayMap = new HashMap<>();
        Map<String, PriorityQueue<Song>> genrePQMap = new HashMap<>();

        // 1. 장르별 총 재생수 & 곡 리스트 구성 
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int playCount = plays[i];

            // 장르별 총 재생수 관리
            if (genrePlayMap.containsKey(genre)) {
                int currentTotal = genrePlayMap.get(genre);
                genrePlayMap.put(genre, currentTotal + playCount);
            } else {
                genrePlayMap.put(genre, playCount);
            }

            // 장르별 PQ가 없다면 만들기
            if (!genrePQMap.containsKey(genre)) {
                genrePQMap.put(genre, new PriorityQueue<>(
                    (s1, s2) -> {
                        if (s1.plays == s2.plays) return s1.id - s2.id; // id 오름차순
                        return s2.plays - s1.plays;                     // plays 내림차순
                    }
                ));
            }

            // 있다면 장르별 PQ에 곡 추가
            genrePQMap.get(genre).offer(new Song(i, playCount));
        }

        // 2. 장르 정렬 (총 재생수 내림차순)
        List<String> genreOrder = new ArrayList<>(genrePlayMap.keySet());
        genreOrder.sort((a, b) -> genrePlayMap.get(b) - genrePlayMap.get(a));


        // 3. PQ에서 상위 곡 2개만 꺼내기
        List<Integer> result = new ArrayList<>();

        for (String g : genreOrder) {
            PriorityQueue<Song> pq = genrePQMap.get(g);

            if (!pq.isEmpty()) result.add(pq.poll().id);
            if (!pq.isEmpty()) result.add(pq.poll().id);
        }

        // [output]
        return result.stream().mapToInt(i -> i).toArray();
    }
}

4. De-fault

시간 복잡도

TIL

1) 람다식을 통한 Comparator 작성

• PriorityQueue, List 정렬 등 Comparator 사용 시 람다식 작성을 통해 가독성을 높임.

  // 기존 방식
  Comparator<Integer> comp = new Comparator<Integer>() {
    @Override
    public int compare(Integer a, Integer b) {
        return b - a;
    }
  };
  

// 람다식 방식 Comparator comp = (a, b) -> b - a;

### 2) Stream을 통한 타입 변환
- Stream API는 컬렉션 데이터를 처리하는 파이프라인 기능임.
- 문제에서 `List<Integer>` -> `int[]` 타입 변환
```java
return result.stream()
             .mapToInt(i -> i)
             .toArray();

• 리스트를 스트림으로 변환한 후

• Integer 객체를 기본 int로 언박싱하여 (IntStream 생성)

• toArray()를 통해 IntStream을 int[]로 변환함.

  
  

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요. 알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂

• n개의 컴퓨터가 있을 때, 컴퓨터들이 연결되어 있는 정보를 담은 2차원 배열이 주어짐.
• 연결된 컴퓨터들을 하나의 네트워크로 간주할 때 총 네트워크의 개수를 반환해야 함.

// [input]
 n (1 ≤ n ≤ 200) : 컴퓨터의 개수
computers (n × n 배열): 연결된 컴퓨터들에 대한 정보. (1: 연결)

2. 스크래치

풀이: 그래프 탐색 (DFS)

• 각 컴퓨터(노드)에서 연결된 다른 컴퓨터들을 재귀적으로 방문함.

1. 모든 컴퓨터를 순회하면서 아직 방문하지 않은 컴퓨터라면 → 먼저 네트워크 수를 ++ → 그 컴퓨터와 연결된 컴퓨터를 dfs 함수를 호출하면서 모두 방문 처리하여 같은 네트워크로 묶음
2. 메인 반복문으로 돌아가 아직 방문하지 않은 컴퓨터가 있다면 → 네트워크 수 ++ → dfs로 같은 네트워크로 묶는 과정을 반복

3. 코드

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (!visited[i]) { // 아직 방문하지 않은 컴퓨터면
                answer++; // 네트워크 개수 추가
                dfs(i, visited, computers, n); // 연결된 모든 컴퓨터 찾기
            }
        }
        return answer;
    }

        // dfs: 연결된 컴퓨터 방문 처리
    void dfs(int current, boolean[] visited, int[][] computers, int n) {
        visited[current] = true; // 현재 컴퓨터 방문 처리

           // 현재 컴퓨터와 연결된 다른 컴퓨터 체크 
        for (int i = 0; i < n; i++) {
            if (computers[current][i] == 1 && !visited[i]) {
                dfs(i, visited, computers, n); // 그 컴퓨터로 이동 -> 다시 연결 확인
            }
        }
    }
}

4. De-fault

시간 복잡도

• DFS 시간 복잡도: O(n^2) (n: 컴퓨터 수)

개선 방향

• Union-Find 방식을 사용하면 네트워크의 개수를 세는 작업을 더 빠르게 할 수 있음 이 방법은 O(n)에 가까운 시간 복잡도로 해결할 수 있으며, 트리 구조로 연결을 관리하기 때문에 탐색 속도가 빠름.

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요. 알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂

2-1. B-Tree (Balanced Tree)

1) B-Tree의 정의와 특징

• B-Tree는 이름처럼 균형 잡힌 탐색 트리(Search Tree) 자료구조임.
• DB의 인덱스나 파일 시스템에서 디스크 I/O를 최소화하여 대용량 데이터를 효율적으로 관리하기 위해 설계됨.
• 하나의 노드가 2개 이상의 데이터(Key)와 2개 이상의 자식 노드를 가질 수 있는 다진 트리 구조임. (M-way Tree)

2) 이진 탐색 트리와의 차이점

3) 균형 트리의 개념

• 균형이란 삽입, 삭제 등의 작업이 발생해도 트리의 높이가 한쪽으로 치우치지 않고 일정하게 유지되는 것을 의미함.
• B-Tree는 항상 균형을 유지하여, 어떤 데이터를 검색하든지 루트 노드에서 리프 노드까지의 경로 길이(트리 높이)가 같도록 보장함
• 이 덕분에 최악의 경우에도 검색 시간 복잡도가 O(log n)으로 안정적임. (BST는 최악의 경우 O(N))

2-2. B-Tree의 계층적 구조

B-Tree의 모든 노드는 기본적으로 같은 구조를 가지지만, 트리의 계층에 따라 역할이 구분됨.

1) 루트 노드 (Root Node)

• 트리의 가장 위에 있는 유일한 노드이자 모든 탐색의 시작점dla.
• 트리가 비어있지 않은 한 반드시 존재하며, 다른 노드와 달리 키 개수와 자식 노드 개수에 대한 최소 제한 조건이 완화될 수 있음.

2) 내부(브랜치) 노드 (Internal/Branch Node)

• 루트 노드와 리프 노드 사이에 위치하며, 탐색 경로를 안내하는 역할을 함.
• 항상 자식 노드를 가지는 노드
• 키(Key): 다음 탐색 경롤를 결정하기 위한 기준값
• 자식 포인터(Pointer): 하위 노드들을 가리키는 주소값

3) 리프 노드 (Leaf Node)

• 트리의 가장 낮은 레벨에 위치하며, 실제 데이터 또는 데이터의 위치를 담고 있는 노드
• 자식 노드를 가지지 않으며 B-Tree에서는 모든 리프 노드가 항상 동일한 깊이(Level)에 위치하여 균형을 유지함.

2-3. 키와 포인터

1) B-Tree 차수 (Order)

• B-Tree에서 하나의 노드가 가질 수 있는 최대 자식 수를 차수($M$) 또는 Order라고 함

• 키 개수와의 관계

  • 차수가 M인 B-Tree는 하나의 노드에 최대 M-1개의 키(데이터)를 저장할 수 있음.

  • 노드의 키 개수가 N개라면, 자식 포인터(자식 노드를 가리키는 포인터)는 N+1개를 가짐.

  • 이 차수(M)가 클수록 노드당 담는 키가 많아지므로 트리의 높이는 더욱 낮아져 디스크 I/O에 유리해짐.

  • e.g. 4차 B-Tree (M=4)

    최대 자식 수: 4개, 최대 키 개수: 4-1 = 3개

2) 노드의 저장 형태

차수가 M인 B-Tree의 한 노드는 $P_1, K_1, P_2, K_2, \dots, P_n, K_n, P_{n+1}$로 구성됨.

• n : 현재 노드가 가지고 있는 키(데이터)의 개수
• $Ki$: 데이터 (키) 값, 키 값은 정렬된 상태로 저장됨
• $Pi$ : 자식 노드를 가리키는 포인터 (주소)

3) 탐색 구조의 원리

• 키의 역할 (K)
  • 노드 내에서 해당 키의 왼쪽에 있는 모든 키는 $Ki$보다 작고, 오른쪽에 있는 모든 키는 크거나 같도록 트리를 분할하는 경계 역할을 함.
• 포인터의 역할 (P)
  • $P1$은 $K1$보다 작은 값을 가진 자식 노드를 가리킴

루트 노드에서 원하는 데이터를 검색할 때 매 노드마다 많은 수의 키를 비교하고 하나의 포인터를 따라 내려가므로, 트리의 높이가 낮아져 디스크 I/O 횟수를 최소화할 수 있음.

3. B+Tree의 기초

3-1. B+Tree란 무엇인가?

• B+Tree는 자체 균형(self-balancing)이 가능한 트리 자료구조의 한 종류로, 특히 대용량 데이터를 저장하는 디스크 환경에서 최적화된 구조

• 범위 검색 최적화 리프 노드가 순차적으로 연결되어 있어, 시작점만 찾으면 리스트를 따라 순차적으로 데이터를 빠르게 탐색할 수 있음.

• 디스크 I/O 최소화 내부 노드가 키와 자식 노드의 포인터만 저장하여 노드 하나에 더 많은 키를 담을 수 있음. 이는 트리의 높이를 낮춰 데이터를 찾기 위해 디스크에 접근하는 횟수를 획기적으로 줄여줌.

• DB에서 레코드를 빠르게 검색, 삽입, 삭제할 수 있도록 돕는 인덱스를 구현하는 데 가장 널리 사용됨.
• 디스크 접근 횟수를 최소화하여 검색 성능을 향상시키는 것이 주된 목적임.

3-2. B+Tree의 시간 복잡도 및 균형 유지 원리

B+Tree는 대용량 디스크 환경에 최적화된 자료구조로, 모든 주요 연산에서 일관되고 효율적인 로그 시간 복잡도를 제공하며, 이를 노드 분할(Split) & 병합(Merge)을 통해 균형있게 유지함.

1) B+Tree의 시간 복잡도

B+Tree의 시간복잡도는 트리의 높이(h)에 의해 결정됨.

트리의 차수와 전체 데이터 레코드의 개수(n)을 사용할 때, 높이 h는 $O(\log_m n)$에 비례함

2) B+Tree의 균형 유지 원리 (Self-Balancing Principle)

B+Tree는 데이터의 삽입과 삭제가 빈번하게 일어나더라도 트리의 모든 리프 노드가 항상 같은 깊이에 위치하도록 유지하여 검색 성능의 일관성을 보장함.

이 메커니즘을 통해 B+Tree는 데이터의 동적인 변화에도 불구하고 항상 로그 시간 복잡도를 유지하며 효율적인 인덱스 역할을 수행할 수 있음.

이 균형을 유지하는 주요 매커니즘은 노드 분할과 노드 병합/재분배임.

(1) 삽입 시 균형 유지: 노드 분할 (Node Split)

데이터를 삽입하여 특정 노드의 키 개수가 최대 허용 개수를 초과했을 때 발생함.

• 꽉 찬 노드를 두 개의 노드로 나눔.
• 나눠진 두 노드를 구분하는 중간 키(Median Key)를 선택함.
• 이 중간 키는 부모 노드로 승격되어 인텍스 엔트리로 사용되고, 부모 노드의 키 개수 규칙을 따르면서 분할된 두 자식 노드를 가리키게 됨

[전파, Propagation]

승격된 키로 부모 노드 또한 최대 키 개수를 초과하면, 이 과정은 루트 노드까지 재귀적으로 반복될 수 있음.

루트노드까지 분할되면 트리의 높이가 1 증가함.

(2) 삭제 시 균형 유지: 병합 및 재분배(Merge & Redistribution)

데이터를 삭제하여 특정 노드의 키 개수가 최소 허용 개수 미만이 되었을 때 발생함.

• 재분배(Redistribution)

  형제 노드에게서 키를 빌려와 최소 개수를 충족시키려고 시도함.

  이웃 노드가 여유 키를 가지고 있다면, 부모 노드의 키를 포함하여 키를 재분배하고 균형을 맞춤.

• 병합 (Merge)

  형제 노드마저 키가 부족하여 빌려줄 수 없다면, 해당 노드와 형제 노드를 하나로 함침.

[전파, Propagation]

두 노드가 병합되면, 부모 노드에서 해당 두 노드를 연결하던 인덱스 키가 제거됨.

이 제거로 인해 부모 노드가 최소 키 개수 미만이 되면, 이 과정은 루트 노드까지 재귀적으로 반복, 병합되어 키가 하나도 남지 않게 되면 트리의 높이가 1 감소함.

1-1. 인덱스란 무엇인가?

1) 인덱스의 정의와 역할

• 인덱스는 DB 테이블에 대한 검색 성능을 높이기 위해 특별한 자료구조로 구성된 매커니즘
• 마치 책의 목차나 색인과 같이, 원하는 데이터를 찾기 위해 테이블 전체를 훑어볼(Full Table Scan) 필요 없이 빠르게 해당 데이터가 위치한 곳을 찾아줌.
• 핵심 역할은 I/O(Input/Output) 횟수를 줄이는 것, 디스크 I/O는 성능 저하의 주범이므로, 이를 줄여 검색 속도를 획기적으로 향상시킴.

2) 왜 인덱스를 사용하는가?

• 검색 속도 향상
  • 특정 조건에 맞는 데이터를 찾을 때, 인덱스를 사용하면 테이블의 특정 범위만 빠르게 탐색할 수 있음.
• 정렬 및 그룹화 용이
  • 데이터를 정렬 (ORDER BY)하거나 그룹화(GROUP BY)할 때 이미 인덱스 자체가 정렬된 상태이므로, 별도의 정렬 작업 없이 인덱스를 활용하여 처리 속도를 높임.
• 고유성 보장
  • NIQUE 인덱스를 설정하면 해당 컬럼의 데이터 중복을 방지하여 데이터의 무결성을 보장할 수 있음

3) 인덱스가 CRUD 성능에 미치는 영향

인덱스는 검색(Read) 성능은 높여주지만, 데이터 변경(Write) 작업에는 추가 비용을 발생시킴.

인덱스가 많아질수록 검색(Read) 성능은 좋아지지만, 삽입/수정/삭제(Write) 시의 부하가 커지므로, 테이블 전체적인 작업 부하를 고려하여 적절한 개수와 컬럼에만 인덱스를 설정해야 함.

• CREATE (삽입)
  • 새로운 데이터가 삽입될 때, 데이터 레코드뿐만 아니라 인덱스 페이지에도 새로운 키를 삽입하는 작업이 추가로 발생함.
• READ
  • 인덱스를 통해 필요한 레코드에 빠르게 접근하므로, 가장 큰 성능 이점을 얻는 작업임.
• UPDATE
  • 인덱스가 설정된 컬럼의 값이 변경될 경우, 기존 인덱스를 삭제하고 새로운 인덱스를 삽입하는 두 가지 작업이 발생하여 비용이 큼.
• DELETE
  • 데이터 레코드를 삭제하고, 해당 레코드에 대한 인덱스 항목도 함께 삭제해야 하므로 추가 작업이 필요함.

1-2. 클러스터형 인덱스 & 비클러스터형 인덱스

DB에서 데이터를 저장하고 찾는 방식에 따라 인덱스는 크게 클러스터형과 비클러스터형으로 나뉨.

이 둘은 데이터의 물리적 정렬 방식과 인덱스 리프 노드에 무엇이 저장되는지에 차이가 있음.

클러스터형 인덱스 (Clustered Index)

• 정의 & 특징

  • 테이블의 물리적인 데이터 행을 인덱스 키 값의 순서대로 정렬하여 저장하는 방식
  • 데이터 자체가 묶여 한 가지 방식으로만 물리적으로 정렬되어서 저장됨.
  • 테이블당 오직 하나만 생성할 수 있음.
  • 대부분의 DB에서는 PK를 지정하면 자동으로 클러스터형 인덱스가 생성됨.

• 구조적 특징

  • 인덱스의 리프 노드가 곧 실제 데이터 레코드 자체임.
  • 인덱스를 탐색하는 것 자체가 실제 데이터에 도달하는 것을 의미함.

• 장점

  • 인덱스 검색 후 추가적인 데이터 조회 과정이 필요 없어 검색 속도가 매우 빠름
  • 데이터가 이미 순서대로 물리적으로 인접하게 저장되어 있기 때문에 범위 검색(Range Query)에 매우 효율적임.

• 단점

  • 데이터 삽입 밑 수정 시. ㅔ이터의 물리적 위치를 재정렬해야 하는 경우가 생겨 부하가 큼.
  • 인덱스의 크기가 곧 테이블의 크기와 같기 때문에 인덱스를 생성하는 데 시간이 오래 걸림.

비클러스터형 인덱스 (Secondary/Non-Clustered Index)

• 정의 & 특징

  • 데이터의 물리적 정렬과는 별개로, 인덱스만 따로 정렬하여 관리하는 방식
  • 테이블당 여러 개를 생성할 수 있음
  • PK가 아닌 일반 컬럼에 생성하는 모든 인덱스가 여기에 해당됨.

• 구조적 특징

  • 인덱스의 리프 노드에는 데이터 레코드 자체가 아닌, 해당 데이터를 찾을 수 있는 주소값(포인터)이 저장됨.
    • MySQL InnoDB: 클러스터형 인덱스의 기본 키 값이 주소값으로 저장됨.
    • SQL Server 등: 물리적 위치 주소(RID)나 클러스터 키 값 등이 저장됨.
  • 따라서 검색 과정은 인덱스 검색 → 주소값 획득 → 데이터 레코드 재조회 (Lookup)의 2단계로 이루어짐

• 장점

  • 데이터 삽입 / 수정 시 데이터 레코드의 물리적 위치를 변경할 필요가 없어 클러스터형 인덱스보다 부하가 적음.
  • 테이블당 여러 개를 만들 수 있어 다양한 컬럼 조합으로 검색 성능을 높일 수 있음.

• 단점

  • 인덱스를 통해 데이터의 주소를 얻은 후 실제 데이터를 다시 한 번 찾아가는 추가적 작업(Lookup)이 필요하므로, 클러스터형 인덱스보다 검색 속도가 약간 느릴 수 있음.

• m * n 크기의 격자 모양
• 집의 좌표 (1,1), 학교의 좌표 (m,n)
• int[][] puddles 좌표가 주어짐
• 오른쪽, 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 return

제한 사항

• 1 <= n, m <= 100
• puddles는 0개 이상 10개 이하
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않음

2. 스크래치

문제 유형 파악: 동적 계획법(DP)

• ** 최적 부분 구조를 가짐** 큰 문제의 해답이 작은 문제의 해답들로 구성되는 경우! 집 ~ 목표 지점까지의 최단 경로의 경우의 수는 그 이전 지점들로 오는 경우의 수들의 합으로 결정됨 문제의 제약 조건: 오른쪽 또는 아래쪽으로만 이동 가능 => 해당 칸으로 이동하는 경우의 수 = 왼쪽에서 오는 경우 + 위쪽에서 오는 경우

• DFS 탐색으로 푸는 경우 모든 경로를 단순 재귀 호출 (DFS)로 탐색한다면, 여러 경로를 탐색하는 과정에서 동일한 중간지점까지 도달하는 경우의 수를 반복해서 계산하게 됨 DP를 사용할 경우 한 번 계산된 결과를 메모이제이션해두고, 필요할 때마다 저장된 값을 재활용하여 계산 속도를 높임.

  
  

3. 풀이

[로직] 문제 쪼개기

1) DP 배열 정의 & 초기화

        // 1. dp 배열 선언 
        int[][] dp = new int[n][m];

        // 2. 물 웅덩이에 -1 표시 (0-based index)
        for(int[] puddle: puddles){
            int x = puddle[0]-1;
            int y= puddle[1]-1;
            dp[y][x] =-1;
        }

        // 3. 시작위치 표시: 집(0,0)에 1 표시
        if(dp[0][0]!=-1){
            dp[0][0]=1;
        }else{
            return 0;
        }

• dp 2차원 배열: 1-based index -> 0-based index
• dp 배열 선언 시 사이징 (열, 행) => (행, 열) 문제에서 m : 가로 길이 => 열, n : 세로 길이 => 행 학교의 (행,열)위치 좌표가 (3,4)이지만 (4,3)으로 표기됨 이것을 다시 (행, 열)로 바꾸어서 문제 풀기

2) DP 테이블 채우기

    for(int i=0; i< n; i++){
            for(int j=0; j<m; j++){
                int leftPaths=0;
                int topPaths=0;

                // 0) 시작점 채워져 있음 -> pass
                if(i==0 && j==0) continue;

                // 1) 물 웅덩이라면
                if(dp[i][j]==-1){
                    dp[i][j]=0; // 경로 개수 = 0
                    continue; // 다음 칸으로
                }

                // 3) + 위쪽 칸 경로 개수
                if(i>0){
                    topPaths = dp[i-1][j];
                }
                // 4) + 왼쪽 칸 경로 개수
                if(j>0){
                    leftPaths=dp[i][j-1];
                }

                // 5) !! 합산 & 모듈러 연산
                dp[i][j] = (topPaths + leftPaths) % mod;
            }
        }

• 2차원 배열을 2중 for문으로 순회하면서 탐색 좌표가 물웅덩이이거나 시작점이면 건너뜀 (continue)
• 위쪽 경로의 경우의 수를 구할 때 경계 확인: i>0 (i=0 위의 행이 없기 때문)
• 왼쪽 경로의 경우의 수를 구할 때 경계 확인: j>0 (j=0 왼쪽의 행이 없기 때문)

3) 출력

answer = dp[n-1][m-1];
return answer;

4. 코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {

        final int mod = 1000000007;
        int answer = 0;

        // !!
        // m : 가로 길이 => 열
        // n : 세로 길이 => 행
        // 학교의 위치: (m,n)-> (4,3) => (3,4)
        // 1. dp 배열 선언 
        int[][] dp = new int[n][m];

        // 2. 물 웅덩이에 -1 표시 (0-based index)
        for(int[] puddle: puddles){
            int x = puddle[0]-1;
            int y= puddle[1]-1;
            dp[y][x] =-1;
        }

        // 3. 시작위치 표시: 집(0,0)에 1 표시
        if(dp[0][0]!=-1){
            dp[0][0]=1;
        }else{
            return 0;
        }

        // 4. dp 테이블 채우기
        for(int i=0; i< n; i++){
            for(int j=0; j<m; j++){
                int leftPaths=0;
                int topPaths=0;

                // 0) 시작점 채워져 있음 -> pass
                if(i==0 && j==0) continue;

                // 1) 물 웅덩이라면
                if(dp[i][j]==-1){
                    dp[i][j]=0; // 경로 개수 = 0
                    continue; // 다음 칸으로
                }

                // 3) + 위쪽 칸 경로 개수
                if(i>0){
                    topPaths = dp[i-1][j];
                }
                // 4) + 왼쪽 칸 경로 개수
                if(j>0){
                    leftPaths=dp[i][j-1];
                }

                // 5) !! 합산 & 모듈러 연산
                dp[i][j] = (topPaths + leftPaths) % mod;
            }
        }

        answer = dp[n-1][m-1];

        return answer;
    }
}

5. De-fault

fault-1. 2차원 배열의 인덱싱

• 문제 문제에서 (m,n)으로 주어졌을 때 바로 dp[m][n]으로 배열을 생성하면 인덱스가 꼬임
• 해결 문제에서 (n,m) & 1-based index => (m, n) & 0-based index로 바꾸기

fault-2. 자료형과 오버 플로우

• 문제 경로의 개수가 int 범위를 쉽게 초과할 수 있음.
• 해결 DP 배열을 long 타입으로 선언하고, 덧셈 연산 후 반드시 % 1000000007 모듈러 연산을 적용하는 방식을 고려.
  

fault-3. 경계 및 물웅덩이 처리

• 문제 맨 위 줄(i=0)이나 맨 왼쪽 줄(j=0)에서 DP[i-1][j]나 DP[i][j-1]를 참조하면 ArrayIndexOutOfBoundsException 발생.
• 해결 if (i > 0) 및 if (j > 0) 조건문을 사용하여 경계 밖 참조를 막음. 물웅덩이는 미리 0으로 설정하여, 덧셈에 포함되더라도 경로 개수 합산에 오류를 일으키지 않도록 함.

시간 복잡도: O(N*M)

1. *DP 배열을 순회하는 2중 for문 * (O(N*M)) N,M <= 100
2. 각 칸의서의 연산 (O(1))

1-1. ACID의 정의

• ACID의 정의: 데이터베이스 트랜잭션의 안정성 및 신뢰성을 보장하는 4가지 핵심 속성 (Atomicity, Consistency, Isolation, Durability)의 약자임.

  A: Atomicity (원자성)

  C: Consistency (일관성)

  I: Isolation (격리성)

  D: Durability (지속성)

• 각 속성의 상호 관계

  4가지 속성은 독립적이지만, 트랜잭션의 성공을 위해 서로 상호 보완적임.

  이 중 하나라도 깨지면 트랜잭션이 실패하거나 데이터 문제가 발생함.

• 트랜잭션의 정의 & ACID의 관계

  트랜잭션: 데이터베이스의 상태를 변화시키는 하나의 논리적 작업 단위

  ACID는 이 트랜잭션이 성공적으로 완료되기 위한 필수 조건

1-2. 왜 필요한가?

• 데이터 유실, 불일치 등의 문제 발생 시나리오 방지

  트랜잭션 처리 중 시스템 오류가 발생했을 때 데이터 불일치나 유실을 막기 위해 필수적임

  e.g. 은행 계좌 이체 중 송금은 완료되고 입금이 되지 않는 심각한 오류를 방지함.

• 특히 금융 거래 등 중요 시스템에서의 역할

  금융, 예약 시스템 등 데이터의 정확성과 신뢰성이 절대적으로 요구되는 시스템에서 시스템 신뢰도를 보장함.

2. A: 원자성 (Atomicity)

All or Nothing

트랜잭션 내의 모든 작업은 하나의 단위로 실행되며, 일부만 실행되거나 실패하지 않음을 보장함.

• 작동 원리:
  • 트랜잭션 내 모든 작업은 하나로 묶여 처리됨.
  • 성공 시 모든 작업 커밋 (Commit), 실패 시 모든 작업 롤백 (Rollback) 처리됨.
• 핵심 목표: 트랜잭션의 부분 완료 방지를 통해 데이터의 불일치 또는 불완전한 상태를 방지함.
• 원자성 위반 시 문제: 부분 업데이트 (Partial Update) 발생

3. C: 일관성 (Consistency)

*트랜잭션 전후 데이터베이스가 *유효한 상태를 유지함.

• 데이터베이스에 정의된 제약 조건 (Constraints)을 반드시 준수해야 함.

• 작동 원리:

  • 트랜잭션이 아무리 복잡해도 외래 키, 도메인 제약, 무결성 제약 등 모든 데이터 규칙을 준수함.
  • 트랜잭션 전후 데이터베이스는 항상 유효한 상태임.

• 핵심 목표: 데이터베이스의 논리적 규칙을 깨지 않도록 보장함.

• 일관성 위반 시 문제: 데이터베이스 제약 조건 파괴

  e.g. 외래 키를 위반하거나 계좌 잔액이 마이너스가 되는 경우 시스템이 잘못된 상태로 처리됨

4. I: 격리성 (Isolation)

여러 트랜잭션이 동시에 실행되어도 서로 독립적으로 보이도록 보장함.

각 트랜잭션은 다른 트랜잭션의 영향을 받지 않음을 보장함.

• 핵심 목표: 데이터 부정합을 방지하는 동시성 제어
• 격리성 위반 시 문제: 동시성 제어 문제
  • Dirty Read (더티 읽기): 롤백될 데이터를 읽는 문제.
  • Non-Repeatable Read (반복 불가능 읽기): 같은 데이터를 두 번 읽었을 때 값이 달라지는 문제.
  • Phantom Read (유령 읽기): 트랜잭션 내에서 새로운 데이터가 추가/삭제되어 보이는 문제.

격리 수준 (Isolation Levels)

동시성 문제를 다루기 위해 표준화된 4가지 레벨이 있음 (낮은 수준 → 높은 수준)

• Read Uncommitted: 커밋되지 않은 데이터도 읽을 수 있어 Dirty Read 가능.
• Read Committed: 커밋된 데이터만 읽을 수 있음.
• Repeatable Read: 같은 데이터에 대해 반복해서 읽었을 때 값이 같아야 함 (Non-Repeatable Read 방지).
• Serializable: 모든 트랜잭션이 순차적으로 실행되는 것처럼 보임 (가장 엄격).

5. D: 지속성 (Durability)

*트랜잭션이 *커밋된 후의 데이터는 영구적으로 기록되어 유실되지 않음을 보장함.

커밋된 데이터는 시스템 장애나 정전이 발생해도 보존됨.

• 작동 원리

  • 커밋 후, 데이터는 주로 로그 파일 기록 및 디스크 쓰기 메커니즘을 통해 안전하게 영구 저장됨.
  • 메모리뿐만 아니라 영구 저장 장치 (디스크)에 기록되는 것을 의미함.

• 핵심 목표: 데이터 영구 보존 보장

• 지속성 위반 시 문제: 커밋된 데이터 유실 (Lost Commit)

  e.g. 시스템 장애 발생 시, 커밋 직후의 데이터가 디스크에 기록되지 못하고 메모리에서 사라져 데이터가 유실됨.

6. ACID-I ) 격리주준별 보장 범위 및 성능 Trade-off

1) Read Uncommitted (가장 낮은 격리 수준)

• 보장 범위

  가장 낮음: 커밋되지 않은 데이터의 읽기를 허용

• 발생 가능한 문제

  • Dirty Read (오염된 데이터 읽기): 다른 트랜잭션이 Rollback할 데이터를 읽음.
  • Non-Repeatable Read 및 Phantom Read 모두 발생 가능

• 성능 Trade-off:

  • 성능 우수 (가장 빠름): Lock 사용을 최소화하여 동시성이 가장 높음.

2) Read Committed (중간 격리 수준, 대부분의 DBMS 기본값)

• 보장 범위

  Dirty Read 방지: 커밋된 데이터만 읽도록 보장함.

• 발생 가능한 문제

  • Non-Repeatable Read 및 Phantom Read 발생 가능

• 성능 Trade-off

  • 성능 균형: 적절한 Lock 사용으로 Dirty Read를 막으면서도 합리적인 동시성을 유지함.

3) Repeatable Read (높은 격리 수준)

• 보장 범위

  Dirty Read 방지.

  Non-Repeatable Read 방지:

  트랜잭션 내에서 같은 데이터를 여러 번 읽을 때 항상 동일한 값을 보장함.

• 발생 가능한 문제

  • Phantom Read 발생 가능: SELECT 조건에 맞는 행의 수는 달라질 수 있음.

• 성능 Trade-off

  • 성능 저하: 읽기 작업에도 Lock을 걸어 트랜잭션 종료 시까지 유지하므로 동시성 저하가 발생함.

4) Serializable (가장 높은 격리 수준)

• 보장 범위

  Dirty Read, Non-Repeatable Read, Phantom Read 모두 방지 (데이터 정합성 최고).

  모든 트랜잭션이 순차적으로 실행되는 것과 같은 효과를 보장함.

• 발생 가능한 문제

  • 없음: Isolation이 완벽하게 보장됨.

• 성능 Trade-off

  • 성능 매우 저하 (가장 느림): 광범위하고 엄격한 Lock 사용으로 인해 동시성 처리 성능이 크게 감소하고 Deadlock 가능성이 증가합니다.

1-1. 정규화란 무엇인가?

DB 설계는 데이터의 중복을 최소화하고, 일관성 & 무결성을 유지하기 위한 기본 과정이고, 정규화는 이 설계의 핵심 기법임.

정규화?

데이터의 일관성 확보 및 중복을 최소화하기 위해 테이블을 구조화하는 과정

1-2. 이상 현상

DB가 잘못 설계되어 데이터가 중복적으로 쌓여있으면, 데이터를 다룰 때 심각한 문제가 발생함

정규화되지 않은 테이블에서 자주 발생하는 문제를 ‘이상현상’이라 부름

삽입 이상 (Insertion Anomaly)

불필요한 데이터 없이는 삽입이 불가능한 문제

갱신 이상 (Update Anomaly)

동일한 데이터가 여러 곳에 중복 저장되어, 수정할 때 일부만 수정되고 일부는 누락되는 현상

삭제 이상 (Deletion Anomaly)

특정 데이터를 삭제했을 때, 필요한 정보까지 함께 삭제되는 문제

1-3. 정규화 목적과 필요성

• 중복 최소화
• 데이터 무결성 향상
• 구조적 일관성 확보
• 쿼리 성능 & 유지보수 용이성 확보

2. 정규화를 위한 핵심 개념: 함수 종속성과 키

1) 함수 종속성 (FD, Functional Dependency)

하나의 속성이 다른 속성의 값을 고유하게 결정짓는 관계

• 정의: A가 B를 결정한다 A → B 특정 속성이 다른 속성 값을 결정하는 관계 (e.g. 학생ID → 학생이름)

함수 종속성의 종류

1) 완전 함수 종속 (Full Functional Dependency)

복합키 전체에 의해 다른 속성이 결정되는 경우

• (학생 ID, 과목코드) → 성적 성적은 학생 ID, 과목코드 모두 필요

2) 부분적 함수 종속 (Partial Functional Dependency)

복합키 일부만으로 다른 속성이 결정되는 경우

• (학생 ID, 과목코드) → 학생 이름 학생 이름은 학생 ID에만 종속되어 있으므로, 복합키 전체에 종속되지 않음

3) 이행적 종속 (Transitive Functional Dependency)

A → B, B → C이면 A → C 관계가 성립하는 경우

• 학번 → 학과 코드, 학과코드 → 학과명 학번 → 학과명 (이행적 종속)

함수 종속성 & 정규화의 관계

정규화는 함수 종속성을 분석하고, 그 관계를 기준으로 테이블을 분리하는 과정을 수행함.

2) 키

정규화의 모든 단계는 결국 어떤 속성이 어떤 키에 종속되는가를 기준으로 판단하기 때문에 키는 정규화의 축이라고 할 수 있음

후보키 (Candidate Key)

• 한 릴레이션에서 각 튜플(행)을 유일하게 식별할 수 있는 최소 속성 집합
• 여러 개 존재할 수 있음
• e.g. (주민등록번호), (이메일), (전화번호) — 모두 유일하다면 후보키

기본키 (Primary Key)

• 후보키 중에서 대표로 선택된 하나의 키
• NULL이거나 중복될 수 없음
• 데이터 무결성의 중심이 되는 키

대체키 (Alternate Key)

• 후보키 중 기본키로 선택되지 않은 나머지 키
• e.g. 이메일이나 전화번호를 대체키로 설정 가능

외래키 (Foreign Key)

• 다른 테이블의 기본키를 참조하는 속성
• 테이블 간의 관계(Relationship) 를 표현
• e.g. 주문.회원ID → 회원.회원ID

정규화 & 키

정규화는 속성들이 키에 대해 어떻게 종속되어 있는가를 기준으로 단계가 나뉨

함수 종속성을 판단하려면 먼저 기준 키가 명확해야 함

3. 정규형 (Normal Forms) 단계별 이해

테이블에 존재하는 불필요한 종속성을 제거해 중복과 이상(anomalies)을 줄이는 단계별 규칙이자 레벨

각 정규형은 ‘어떤 종류의 종속을 없애야 하는가?’로 정의되고, 해당 정의를 만족시키지 못하면 테이블을 분해하여 해결함.

• 1NF (원자값) ⊂ 2NF (부분 중복 제거) ⊂ 3NF (간접 중복 제거) ⊂ BCNF (모든 결정자=후보키)
• 정규화의 장단점
  • 장점: '이상 현상'이 제거되고, '데이터 중복'이 최소화되어 무결성 보장
  • 단점: 테이블 분리로 인한 JOIN 연산 증가로 성능 저하 가능성
• 비정규화(Denormalization) 성능 향상을 위해 의도적으로 중복을 허용하거나 정규형을 낮추는 전략

1) 제1 정규형 (1NF) - 원자성 (Atomicity)

테이블의 모든 속성 값이 원자값(Atomic Value)을 가져야 함.

반복 그룹, 배열, 리스트와 같은 비원자 값을 허용하지 않음. 하나의 컬럼에 여러 값이 포함될 수 없음 - "축구, 농구" (X)

학생(학번, 이름, 전화번호)
행: (1001, '홍', '010-1111-2222,010-3333-4444')  → 1NF 위반

2. 제2 정규형 (2NF) - 부분 중복 제거

1NF를 만족하고, 부분 함수 종속이 제거되어야 함.

복합키의 일부에만 종속되는 속성이 있어서는 안 됨

수강(학번, 과목코드, 학생이름, 성적)
기본키 = (학번, 과목코드)
학생이름 → 학번에만 종속  → 부분 종속(2NF 위반)

3. 제 3정규형 (3NF) - 이행적 종속 제거

2NF를 만족하고, 이행적 종속이 제거되어야 함

학생(학번, 학과코드, 학과명)
학번 → 학과코드, 학과코드 → 학과명  → 학번 → 학과명 (이행적 종속)

• 학생(학번 → 학과코드 → 학과명) → 학과명은 학과코드에만 종속 → 학과 테이블 분리

4. BCNF (Boyce-Codd Normal Form): 강력한 3NF

제3 정규형(3NF)을 만족하고, 모든 결정자가 후보키여야 함.

모든 결정자( 어떤 속성 집합 X가 Y를 결정할 때 X )는 후보키(Candidate Key) 여야 함.

강의(교수, 과목, 강의실)
FD: 과목 → 교수   (한 과목은 특정 교수 전담)
FD: 교수, 과목 → 강의실

과목은 후보키가 아님(과목만으로 행을 식별 못함), 그런데 과목 → 교수 이므로 BCNF 위반

1. 기본 개념 이해 (What & Why?)

SQL Injection이란?

사용자의 입력값이 데이터로 처리되지 않고, 개발자가 의도하지 않은 DB를 조작하는 SQL 쿼리(명령어)의 일부로 실행되는 웹 보안 취약점

• 정상적인 상황 웹사이트가 사용자에게 ID를 물어보면, 사용자는 my_user_id 같은 데이터(값)를 입력 서버는 이 값을 받아 "이 ID를 가진 사용자를 찾아줘"라는 쿼리를 실행
• 공격 상황 공격자는 my_user_id 대신 admin' OR '1'='1 같은 명령어(쿼리문)를 입력 서버가 이 입력을 제대로 거르지 못하면, 이 값이 그대로 쿼리문에 포함되어 개발자가 의도하지 않은 명령이 실행됨.

왜 발생하는가? (핵심 원인)

동적 쿼리(Dynamic Query)

사용자 입력을 검증 없이 문자열로 이어붙여(+ 또는 concat) 쿼리문을 만들 때 주로 발생함

공격자는 쿼리문의 구문(Syntax)를 깨뜨리는 특수문자를 삽입하여 쿼리를 조작함

2. 주요 공격 유형 (Types)

공격자가 “어떻게” 정보를 빼내는지에 따라 유형이 나뉨.

1) In-band

공격자가 보낸 쿼리의 결과를 현재 웹 페이지 화면을 통해 직접 볼 수 있을 때 사용함

Union-based

UNION 연산자는 두 개 이상의 SELECT문 결과를 하나로 합치는 명령어

공격자는 이를 악용해 원래 쿼리 결과에 추가로 다른 테이블의 데이터를 붙여서 탈취

• e.g. 게시판 검색 쿼리를 조작하여 users 테이블의 id, pw를 탈취 …WHERE title=’검색어’ UNION SELECT id, pw FROM users;

Error-based

고의로 SQL 쿼리 오류를 발생시켜, 반환되는 오류 메시지를 통해 데이터베이스의 구조(테이블명, 컬럼명 등)를 알아내는 방식

만약 서버가 DB 오류 메세지를 화면에 그대로 노출하도록 설정되어 있다면, 공격자는 이 오류 메세지를 통해 DB의 버전, 테이블 이름, 칼럼명 등 민감한 DB 구조 정보를 알아낼 수 있음

2) Inferential (Blind SQL Injection)

추론 방식, 서버가 공격 결과나 메세지를 전혀 보여주지 않고, 단지 정상/ 오류 페이지만 보여줄 때 사용하는 고난도 기법

공격자는 참/ 거짓 반응 또는 응답 시간의 차이를 이용해 데이터를 한 글자씩 빼냄

Boolean-based

참 / 거짓일 때의 페이지 반응이 다른 점을 이용함

• 공격: ‘admin 계정의 비밀번호 첫 번째 글자가 a인가?’의 쿼리를 보냄
• 결과: 게시물이 존재하는 경우 페이지가 뜨면 → T
• 공격: admin 계정의 비밀번호 첫 번째 글자가 b인가?
• 결과: 게시물이 없습니다의 페이지가 뜨면 → F
• 이런 식으로 한 글자, 한 글자 모든 비밀번호를 알아냄 (느리지만 자동화 스크립트로 가능)

Time-based

DB에 내장된 SLEEP(), WAITFOR 등의 함수를 사용해, 응답 시간을 기준으로 데이터를 유추

• 공격: 첫 글자가 'a'이면 5초 대기
• 결과: 서버 응답이 5초 이상 걸리면 → T / 서버 응답이 즉시 오면 → F
• 응답 시간을 측정하여 데이터를 빼냄

3. 방어 기법 (Prevention)

1) Prepared Statement (매개변수 기반 쿼리)

작동원리

쿼리의 틀(Template) & 사용자 값(Data)을 분리해서 DB에 전송함.

DB는 쿼리 틀을 먼저 컴파일하고, 값은 나중에 대입하므로 입력값이 절대로 명령어로 해석되지 않음.

1. 컴파일 (틀 전송) 먼저 SELECT * FROM users WHERE id = ? AND pw = ?; 와 같이, 값이 들어갈 자리를 ? (placeholder)로 표시한 '쿼리 틀'을 DB로 보냄 DB는 이 틀을 미리 컴파일 / 분석함
2. 실행 (값 전송) DB는 이미 틀을 분석해두었기 때문에, 나중에 전송된 admin’—값을 명령어로 절대 해석하지 않음 ? 자리에 들어가야 할 단순한 문자열 데이터로만 취급함

• Java의 PreparedStatement (JDBC), Python의 cursor.execute(query, params), PHP의 PDO 등

2) ORM (Object-Relational Mapping)

• ORM은 내부적으로 Prepared Statement를 사용하여 SQL Injection을 원천적으로 방어해 줍니다. 개발자가 userRepository.findById("admin"); 처럼 객체지향 코드를 작성하면, 내부적으로 안전한 Prepared Statement를 생성하여 DB와 통신함. 개발자가 실수로 동적 쿼리를 만들 여지를 원천적으로 줄임.
• Java(Spring)의 JPA/Hibernate, Python의 SQLAlchemy 등

입력값 검증 (Input Validation)

서버단에서 사용자의 입력이 예상된 형식인지 검사

최소 권한 원칙 (Least Privilege)

DB에 접속하는 웹 애플리케이션 계정에 필요한 최소한의 권한만 부여함

웹사이트는 데이터를 읽고(SELECT), 쓰고(INSERT), 수정(UPDATE)할 뿐 테이블을 삭제(DROP)할 필요는 없음

DROP 권한을 아예 주지 않으면, 공격자가 DROP TABLE 쿼리를 주입해도 권한 없음 오류로 실패하게 됨

2개 이상의 테이블을 연결해 데이터를 조회하는 방법

여러 테이블에 분산된 데이터를 논리적으로 결합해 하나의 결과 집합으로 만드는 연산

두 테이블의 조인을 위해서 PK와 FK 관계로 맺어져야 함.

SELECT 컬럼명
FROM 테이블A
JOIN 테이블B ON 테이블A.공통컬럼 = 테이블B.공통컬럼;

• 공통컬럼은 두 테이블의 관계를 연결하는 키 역할을 함

2. JOIN 유형

내부조인은 두 테이블 모두 데이터가 있어야 결과가 나오지만, 외부 조인은 한쪽에만 데이터가 있어도 결과가 나옴

1) INNER JOIN

두 테이블 모두에서 조건이 일치하는 행만 가져옴

SELECT 열목록
FROM 첫번째테이블
 INNER JOIN 두번째테이블
 ON 조인조건
 WHERE 검색조건

2) LEFT JOIN (OUTER)

왼쪽 테이블의 모든 데이터 + 오른쪽 테이블의 일치하는 데이터 (없으면 NULL)

SELECT 열목록
FROM 첫번째테이블
    LEFT/RIGHT/FULL OUTER JOIN 두번쨰테이블
    ON 조인조건
    WHERE 검색조건

3) RIGHT JOIN

오른쪽 테이블의 모든 데이터 + 왼쪽 테이블의 일치하는 데이터 (없으면 NULL)

4) FULL JOIN

양쪽 테이블의 모든 데이터를 결합 (일치하지 않는 부분은 NULL)

5) CROSS JOIN

모든 경우의 수(카티전 곱)를 결합

한 쪽 테이블의 모든 행과 다른 쪽 테이블의 모든 행을 조인하여 모든 가능한 조합은 반환함.

ON 조건절이 필요없음.

6) SELF JOIN

같은 테이블을 두 번 참조하여 스스로 조인하는 기법

테이블에 별칭(Alias)을 붙여서 구분함.

주로 계층형 데이터를 다룰 때 사용함.

SELECT e.name AS employee, m.name as manager
FROM employess e
JOIN emplyees m
ON e.manager_id = m.id;

3. JOIN 조건

1) ON

• 모든 JOIN 유형에서 사용 가능
• 조인을 수행할 때 사용됨 (테이블을 결합할 때의 조건)
• LEFT/RIGHT/FULL JOIN등에서 일지하지 않는 데이터는 NULL로 채워짐.
• JOIN 이후에도 WHERE로 추가 필터링 가능함.

SELECT * FROM users u
JOIN orders o
ON u.id = o.user_id;

2) USING

• 두 테이블에 컬럼 이름이 동일할 때만 사용 가능함.
• 결합 시 동일 이름의 컬럼을 하나의 컬럼으로 합쳐서 반환함.

SELECT *
FROM employees
JOIN departments
USING (dept_id);

3) WHERE

• JOIN이 끝난 후에 결과 행을 필터링함.
• 보통 INNER JOIN에서 사용됨.
• ON 없이 WHERE만 사용할 수 있음.

3. NULL 처리의 이해

JOIN 조건에서 NULL은 비교 불가능함.

SQL에서 NULL은 ‘값이 없음’이기 때문에 비교연산자 != , = 로 비교 불가함

-- WHERE을 사용하는 경우
WHERE dept_id IS NULL; 

INNER JOIN에서의 NULL

INNER JOIN은 두 테이블의 조건이 일치해야 하므로, NULL이 있는 경우 비교가 불가능해 조인되지 않음.

SELECT e.name, d.name 
FROM emplyoees e
INNER JOIN departments d
ON e.dept_id = d.id;
-- dept_id가 null인 직원에 대해서는 조인되지 않음

LEFT JOIN에서의 NULL

오른쪽 테이블에 매칭이 없을 경우, NULL로 채움

SELECT e.name, d.name
FROM empployees e
LEFT JOIN departments d
ON e.dept_id = d.id;

[employess]

[deparments]

[result]

RIGHT JOIN에서의 NULL

SELECT *
FROM employees e
RIGHT JOIN departments d
ON e.dept_id = d.id;

[employess]

[deparments]

1. SQL & NoSQL

SQL (Structured Query Laguage)

• 관계형 DB
• 데이터를 테이블 기반 구조로 저장하는 관계형 데이터베이스
• e.g. MySQL, PostgreSQL, Oracle, SQL Server

NoSQL (Not Only SQL)

• 비관계형 DB
• 비정형 또는 반정형 데이터를 저장하는 유연한 데이터베이스
• MongoDB, Redis, Cassandra, DynamoDB

2. 구조적 차이점

SQL

• 모든 데이터는 정형화된 스키마를 따라야 함.
• 데이터는 행과 열로 구성된 테이블에 저장됨.
• 테이블 간 관계를 외래키(FK)로 연결함
• 데이터 중복을 최소화하기 위해 정규화를 수행함.

NoSQL

• 비정형 데이터도 저장 가능함. (JSON, Key-Value, Graph등)
• 테이블 대신 컬렉션, 문서, Key-Value Store 형태로 저장함.
• 관계 대신 중첩 구조로 데이터 내포 가능함.
• 데이터 중복을 허용하여 읽기 성능을 극대화함.

3. 트랜잭션 관리

트랜잭션이란 DB에서 한 번에 수행되어야 하는 논리적 작업 단위임.

여러 쿼리를 하나의 작업처럼 묶어서 성공 / 실패를 함께 처리함.

SQL의 트랜잭션 관리 방식: ACID 원칙

NoSQL의 트랜잭션 관리 방식: BASE 원칙

• 개체-관계 다이어그램 DB 설계를 시작할 때, 시스템의 데이터 구조 & 데이터 간의 관계를 시각화하는 핵심 도구
• 무엇이 있고(엔티티), 서로 어떻게 연결되어 있는지(관계)를 도식화한 그림

1. ERD의 주요 구성 요소

2. ERD 작성 단계

(1) 요구사항 분석

• 비즈니스 로직이나 서비스 기능을 분석하여 어떤 데이터가 필요한지 파악
• e.g. 사용자가 상품을 주문함 → User, Product, Order 엔티티 도출

(2) 엔티티 식별

• 관리할 대상을 추출 (명사형)
• User, Product, Order, Payment

(3) 속성 정의

• 각 엔티티의 세부 속성 (칼럼)을 정의
• User: user_id, email Product: product_id, name, price

(4) 관계 설정

• 엔티티 간의 관계를 파악
• User ↔ Order (1: N)
• Order ↔ Product (N: M)

(5) 관계의 카디널리티 명시 (Cardinality)

• 관계의 유형을 명확히 표현함
• 1:1, 1:N, N:M

(6) 정규화

• 데이터 중복을 줄이고 구조를 효율화하기 위해 정규화 과정을 거침
• 1NF: 각 컬럼은 원자값을 가짐 2NF: 부분 종속 제거 3NF: 이행 종속 제거

(7) 다이어그램 시각화

• draw.io, ERD cloud,…

3. ERD 작성 시 주의할 점

• 엔티티 이름은 단수형 명사로 작성 (User)
• 모든 엔티티에 PK 지정
• 외래키 관계 명확히 표시
• 중복 데이터 제거 후 정규화
• 실제 비즈니스 로직과 일치하는지 검증

4. ERD 작성 방법

주식별자 (PK)

각 엔티티의 인스턴스를 유일하게 구분할 수 있는 속성

• 중복 불가(Unique), NOT NULL
• 주로 id, —-_id 형태로 명명

외래 식별자 (FK)

다른 엔티티의 주식별자를 참조하는 속성, 두 엔티티 간의 관계를 나타냄

• 부모 테이블의 기본키를 참조
• 데이터 간 참조 무결성 유지

NOT NULL

• 특정 속성이 반드시 값을 가져야 하는 제약 조건 (데이터 누락 방지)
• ERD에서 속성명 앞에 NN / NOT NULL로 표시

관계 표기법

• 관계의 종류 (Cardinality)

| 관계 | 설명 | 예시 |
| --- | --- | --- |
| **1:1 (One-to-One)** | 하나의 엔티티 인스턴스가 다른 하나와만 연결 | 한 사람은 하나의 여권만 가짐 |
| **1:N (One-to-Many)** | 하나의 인스턴스가 여러 개와 연결 | 한 사용자 → 여러 주문 |
| **N:M (Many-to-Many)** | 여러 인스턴스가 서로 여러 개와 연결 | 학생 ↔ 강좌 (수강) |

• 관계의 필수 / 선택 여부 (Participation)

| 기호 | 의미 | 예시 |
| --- | --- | --- |
| ─│ | 반드시 존재 (Mandatory, 필수 참여) | 사용자는 반드시 주문을 가져야 함 |
| ─O | 없어도 됨 (Optional, 선택 참여) | 사용자가 주문이 없을 수도 있음 |

• Crow’s Foot 표기법 엔티티 간의 관계를 선과 기호로 표현하는 방법 관계의 카디널리티를 직관적으로 표현

  기호	의미	설명
  ─│	1 (One and only one)	반드시 하나 존재
  ─O	0 또는 1 (Zero or one)	선택적으로 하나 존재
  ─<	여러 개 (Many)	하나 이상 존재
  ─O<	0개 이상 (Zero or many)	선택적 다수

DB 설계에서 데이터의 정합성(Intergrity)을 유지하고, 무결성(Consistency)을 보장하기 위해 사용되는 규칙

• 제약 조건은 테이블에 삽입, 업데이트, 삭제되는 데이터가 특정 조건을 만족하도록 강제하는 규칙

제약 조건을 사용해야 하는 이유

• 데이터 무결성 유지: 데이터의 유효성 & 일관성
• 참조 무결성 유지: 외래 키
• 비즈니스 로직 강제: CHECK
• 중복 데이터 방지: UNIQUE

1. NOT NULL

컬럼에 NULL 값이 들어가는 것을 방지

• 해당 칼럼에는 값이 반드시 존재해야 함
• 중요한 데이터가 누락되는 것을 방지하기 위해 사용됨

CREATE TABLE Employees (
    employee_id INT NOT NULL,
    name VARCHAR(100) NOT NULL,
    hire_date DATE
);

2. UNIQUE

컬럼에 중복된 값이 들어가는 것을 방지

• 해당 컬럼은 유일한 값만 저장할 수 있게됨
• 중복 데이터를 방지하고, 데이터의 고유성을 보장함

CREATE TABLE Users (
    user_id INT NOT NULL UNIQUE,
    email VARCHAR(100) UNIQUE
);

3. PRIMARY KEY

테이블에서 각 레코드를 고유하게 식별할 수 있는 칼럼

• 기본키는 반드시 고유하며, NULL 값을 허용하지 않음

CREATE TABLE Customers (
    customer_id INT PRIMARY KEY,
    name VARCHAR(100)
);

4. FOREIGN KEY

다른 테이블의 기본 키나 고유 키를 참조하여 테이블 간의 관계를 정의

• 두 테이블 간의 참조 무결성을 유지하며 한 테이블의 값이 다른 테이블에 존재하는 값이어야 한다는 규칙을 강제

CREATE TABLE Orders (
    order_id INT PRIMARY KEY,
    customer_id INT,
    order_date DATE,
    FOREIGN KEY (customer_id) REFERENCES Customers(customer_id)
);
# Orders 테이블의 customer_id가 Customers 테이블의 customer_id를 참조하도록 외래 키 제약을 설정

5. CHECK

칼럼의 값이 지정된 조건을 만족하는지 검사 → 데이터 유효성 보장

• 비즈니스 규칙 반영에 유용함 수치, 날짜 등의 값에 대해 범위 조건을 지정하거나, 문자열 패턴을 확인하는 데 사용

CREATE TABLE Employees (
    employee_id INT PRIMARY KEY,
    salary DECIMAL(10, 2),
    CHECK (salary >= 0) # salary는 음수가 될 수 없음
);

6. DEFAULT

칼럼에 값이 입력되지 않았을 경우 기본값을 자동으로 삽입

• 데이터 입력 시 해당 칼럼이 비어있으면 기본값이 자동을 삽입됨

CREATE TABLE Orders (
    order_id INT PRIMARY KEY,
    order_status VARCHAR(20) DEFAULT 'Pending'
);

7. INDEX

칼럼에 인덱스를 생성하는 기능

• 인덱스를 사용하면 조회 성능이 향상되지만, 삽입/ 업데이트 성능은 다소 저하될 수 있음 → 주로 검색 성능을 최적화하는 데 사용됨
• 기본키, 고유키는 자동으로 인덱스를 생성하지만 명시적으로 인덱스를 생성할 수도 있음

CREATE INDEX idx_employee_name ON Employees (name);
# Employees 테이블의 name 컬럼에 대해 인덱스를 생성 (검색 성능 향상)

1. 기본키 (Primary Key)

후보 키 중에서 데이터베이스 설계자가 대표로 선택한 단 하나의 키

• 유일성 (Unique): 중복 X
• NOT NULL
• 기본 키 칼럼은 레코드를 고유하게 식별 → 데이터 무결성 유지의 중요 요소

2. 외래키 (Foreign Key)

다른 테이블의 기본 키를 참조 하는 키

• 두 테이블 간의 관계를 정의
• 외래키를 사용하면 참조 무결성을 유지할 수 있으며, 외래키는 참조하는 테이블의 기본 키나 고유 키와 연결됨
• 외래 키가 참조하는 값은 참조되는 테이블에서 존재하는 값이어야 함 (참조 무결성 보장)
• 외래 키 칼럼은 중복 허용
• Null 값 허용 X

3. 후보 키 (Candidate Key)

테이블에서 레코드를 유일하게 식별할 수 있는 키

• 유일성 & 최소성을 만족하는 키 → Null 값 허용 X
• 기본 키는 후보 키 중 하나를 선택한 것 후보 키는 기본 키가 될 수 있는 모든 후보임 (여러 개 일 수 있음)

4. 대체 키 (Alternate Key)

후보 키 중에서 기본 키로 선택되지 않은 나머지 키

• 기본키 외에 레코드를 유일하게 식별할 수 있는 다른 후보 키들
• 대체키도 유일성을 보장하고, Null값 허용 X

5. 슈퍼 키 (Super Key)

테이블의 각 행을 유일하게 식별할 수 있는 하나 이상의 열(Column) 집합

• 슈퍼키는 기본키, 후보키, 대체키 등을 포함한 더 넓은 범위의 키
• 유일성만 만족하면 됨 → 불필요한 열이 포함될 수 있음
• e.g. 학생 테이블 학번 - 주민번호 - 이름 학번 : 슈퍼키 주민번호: 슈퍼키 학번, 이름: 슈퍼키 주민번호, 이름, 학번: 슈퍼키

6. 고유 키 (Unique Key)

테이블의 특정 칼럼이나 칼럼 조합에 대해 중복을 허용하지 않도록 하는 키

• 중복 값을 허용하지 않음
• 하나의 테이블에 여러 개의 고유 키 설정할 수 있음
• Null 값 허용 (기본키와 차이점)

1-1. DB(Database)

: 데이터를 효율적으로 저장하고 관리할 수 있도록 설계된 시스템

• ⇒ 데이터를 체계적으로 저장하고 관리하는 논리적 집합
• 목표: 데이터의 저장, 검색, 갱신을 효과적 / 효율적으로 처리하기 위함.

1-2. DBMS (Database Management System)

데이터를 효율적으로 관리하고, 데이터를 안전하게 저장하며, 여러 사용자들이 데이터베이스에 접근할 수 있도록 제어 / 관리를 수행하는 소프트웨어

• ⇒ 데이터베이스를 생성, 관리, 조작할 수 있게 해주는 소프트웨어
• DB를 직접 관리하지 않고, DBMS가 중간에서 요청을 처리함.
• DBMS는 데이터의 CRUD를 효율적이고 안전하게 수행함.
• 목표: 데이터베이스 내의 데이터를 효율적으로 관리하고, 이를 손쉽게 조작하고, 다수의 사용자가 동시에 데이터를 처리할 수 있도록 동시성 제어를 제공함.

CRUD

데이터베이스에서 데이터를 다룰 떄 수행하는 4가지 기본 작업

2. SQL

SQL, Structured Query Language

DBMS에게 지시를 내리는 명령어의 전체 집합

크게 데이터 정의, 조작, 제어, 트랜젝션 관리 기능 포함

2-1.DDL (Data Definition Language)

데이터 구조를 정의하는 언어

스키마와 테이블 구조를 만드는 역할을 수행함.

2-2. DML (Data Manipulation Language)

데이터를 조작하는 언어

CRUD와 직접적으로 관련 있음

2-3. DCL (Data Control Language)

데이터 접근 권한을 제어하는 언어 사용자, 권한, 보안 관련 제어를 담당

2-4. TCL (Transaction Control Language)

트랜젝션 단위를 제어하는 언어

데이터 조작(DML)의 변경 시점을 관리

3. 테이블 & 스키마

3-1. DB 테이블

: DB에서 데이터를 구조적으로 저장하는 기본 단위

각 테이블은 하나의 엔티티를 나타내며, 행 & 열로 이루어져 있음.

• 행 (Row, Tuple, Record) 테이블에서 하나의 레코드 / 튜플을 나타냄. 각 행은 테이블 내에서 하나의 개별 데이터를 나타내며, 여러 열(속성)을 포함함. (학생 테이블 - 한 명의 학생이 하나의 행을 차지)
• 열 (Column, Attribute) 테이블에서 데이터를 속성 단위로저장하는 부분 각 열은 특정 속성의 데이터를 저장함. (학생 테이블 - 이름, 나이, 학번)

3-2. 스키마

스키마란?

: 테이블의 구조와 제약 조건을 정의한 설계도

• DB내에 포함될 데이터의 구조, 테이블, 속성(필드), 관계, 제약 조건 등을 정의하는 것
• 스키마 설계는 DB가 어떻게 구성될지에 대한 논리적 구조를 정의하며, DB 설계에서 매우 중요한 단계
• 스키마는 DB를 효율적이고 일관성 있게 관리하고 무결성을 보장하기 위해 살용됨
• 스키마 & DB 스키마 ⇒ 데이터의 구조적 설계도 데이터베이스 ⇒ 그 설계대로 채워진 실제 데이터 공간

스키마의 구성 요소

• 테이블 구조 각 테이블의 칼럼(속성)과 데이터 타입
• 테이블 간의 관계 1:1, 1:N, M:N 등
• 제약 조건
• Primary Key*, Foreign Key, Unique, Not Nul
• 뷰(View), 인덱스(Index), 프로시저(Stored Procedures) 등

스키마 3계층

사용자, 설계자, 시스템의 관점을 분리하여 DB를 설계하고 관리하는 표준적인 방식

스키마를 3단계로 나누는 가장 큰 이유는 데이터 독립성을 확보하기 위함임.

• 논리적 데이터 독립성 개념 스키마가 변경되어도, 기존 외부 스키마는 영향을 받지 않는 것을 의미함. DB의 논리적 구조가 확장되거나 변경되어도, 기존에 사용하던 프로그램 코드를 수정할 필요가 없음.
• 물리적 데이터 독립성 내부 스키마가 변경되어도, 개념 스키마와 외부 스키마는 영향을 받지 않는 것을 의미함. DB 관리자가 성능 튜닝을 위해 물리적 구조를 바꿔도, 사용자나 애플리케이션은 동일하게 DB를 사용할 수 있음.

1. 외부 스키마 (External Schema)

   [관점] 최종 사용자 / 응용 프로그램

   개별 사용자나 특정 애플리케이션이 필요로 하는 DB의 일부를 정의한 것

   전체 DB 중 사용자가 보게 될 창 / 뷰로 생각할 수 있음.

   e.g. 쇼핑몰 DB) 고객 - 자신의 주문 내역만 볼 수 있고, 배송팀- 배송지 주소와 상품명만 볼 수 있음.

   • 하나의 DB에 여러 개의 외부 스키마가 존재할 수 있음
   • DB의 전체 구조를 숨기고, 사용자가 필요한 부분에만 간단하게 접근할 수 있게 함.
   • 서브 스키마라고도 불림

2. 개념 스키마 (Conceptual Schema)

   [관점] DBA(DB 관리자 / 설계자)관맂

   DB의 전체적인 논리적 구조를 정의한 것

   DB에 무엇이 저장되는지 나타냄 : 어떤 엔티티가 있고, 어떤 속성을 가지며, 개체들 간 어떤 관계를 가지는지?

   스키마 / ERD로 그리는 대상

   • DB에 단 하나만 존재함
   • 데이터의 무결성, 보안 규칙, 제약 조건 등 모두 이곳에 정의됨
   • 물리적 저장 방식(내부 스키마)이나 개별 사용자 뷰(외부 스키마)와는 독립적임

3. 내부 스키마 (Internal Schema)

   [관점] DBMS / 시스템 프로그래머

   데이터가 하드디스크와 같은 물리적 저장 장치에 실제로 어떻게 저장되는지 정의한 것

   데이터의 물리적인 저장 구조, 파일 구성 방식, 인덱스 생성 방법, 데이터 압축 등을 다룸

   DB의 성능, 효율성에 직접적인 영향을 줌

   • DB에 단 하나만 존재함
   • 물리적 스키마(Physical Schcema)라고도 부름
   • 개념 스키마와 논리적 구조가 실제로 어떻게 구현될지 구체적으로 명시함

3-3. 스키마 설계

스키마 설계는 데이터의 논리적 관계와 제약을 설계하는 과정임.

1. 데이터 무결성 & 정확성 확보
   • PK 정의 모든 테이블의 각 행은 고유하게 식별할 수 있는 기본 키를 가져야 함.
   • 정확한 데이터 타입 설정 데이터를 가장 잘 표현할 수 있는 타입을 사용하여야 함. e.g. 나이 (INT)
   • 제약조건 적극 활용 NOT NULL, UNIQUE, FK,…
2. 데이터 중복 최소화 (정규화, Normalization)
   • 정규화 (Normalization) 중복된 데이터를 최소화 & 데이터 무결성을 유지하기 위해 데이터를 적절히 분할하는 과정 보통 1NF (제1정규형)부터 5NF(제5정규형)까지 여러 단계로 나뉘어 데이터 구조를 최적화 정규화는 데이터 중복을 피하고 갱신 / 삭제 이상 문제를 예방하는 데 유리하지만, 조인 연산이 많아져서 성능에 영향을 미칠 수 있음.
     • 1NF: 각 컬럼에 원자값(Atomic Value)만을 포함하여 데이터를 중복하지 않도록 함.
     • 2NF: 부분 종속성을 제거하여 데이터 무결성을 강화함.
     • 3NF: 이행적 종속성을 제거하여 데이터의 의존 관계를 단순화함.
     • BCNF(보이스-코드 정규형): 3NF보다 한 단계 더 엄격한 정규화
3. 명확성 & 일관성 유지
   • 일관된 이름 규칙 (Naming Convention) 테이블 이름: 복수형 / 단수형 중 하나로 통일 (복수형이 일반적) 컬럼 이름: 보통 snake_case 직곽적인 이름 & 주석 추가 (설명)
4. 성능 & 확장성 고려

데이터와 사용자가 많아졌을 때도 시스템이 원활하게 동작하도록 설계해야 함.

• 적절한 인덱스 설계 WHERE 절에서 자주 조회되거나, JOIN의 연결고리가 되는 컬럼에서는 인덱스를 생성하여 조회속도를 향상시킴. 단 ,인덱스는 INSERT / UPDATE 성능을 저하시킬 수 있으므로 무분별한 사용 X
  • 반정규화의 전략적 사용 정규화(원칙 2)를 철저하게 지킬 경우 JOIN이 많아져 성능이 저하될 수 있음. 조회 성능을 높이기 위해 의도적으로 중복을 허용하거나 테이블을 합침. (반정규화) 반정규화는 정규화를 충분히 거친 후 성능상 이점이 확실할 때만 선택적으로 적용되어야 함.

• 2N 길이의 컨베이어 벨트 (N *2) 로봇을 올리는 위치: 1번칸(인덱스: 0) 로봇을 내리는 위치: N번칸(인덱스: N-1)
• 로봇을 내린다? 벨트에서 완전히 제거 (밑 라인으로 이동 X)
• 각 칸은 내구도를 가짐 로봇을 올리는 위치에 올리거나, 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 1만큼 감소함
• 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료 → 몇 번째 단계에서 진행이 멈추는가?

컨테이너 벨트의 작동 과정

1. 컨베이어 벨트의 회전 벨트는 각 칸 위에 있는 로봇과 함께 회전함
2. 회전 후 로봇의 이동 가장 먼저 올라간 로봇부터, 회전 방향으로 1칸 이동 가능하다면 이동, 아니라면 가만히 있음

• 로봇의 이동 조건: 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 함

3. 로봇 올리기 올리는 위치의 내구도가 0이 아니면 가능
4. 내구도가 0인 칸의 개수 ≥ K → 종료

• 내구도 감소 조건: 로봇을 올리는 위치에 올리거나 / 로봇이 어떤 칸으로 이동할 경우, 그 칸의 내구도 —

// [input]
3 2
1 2 1 2 1 2

// [output]
2

2. 스크래치

문제 유형 파악: 시뮬레이션

주어진 환경에서 여러 작업을 순차적으로 실행

상태 변화와 규칙에 따라 동작을 구현

1. 상태 변화 관리 & 규칙의 순차적 처리

• 컨베이어 벨트의 회전 → 벨트의 내구도, 로봇의 위치가 변화함
• 회전 이후 로봇 이동, 로봇 추가, 로봇 제거의 작업이 발생

1. 종료 조건

• 문제에서 주어진 K ≤ 내구도가 0인 칸의 개수

3. 풀이

[로직] 문제 쪼개기

// [input]

// [logic]
// 로봇의 배열 & 스텝수 정의
boolean[] robots = new boolean[N];
int step = 0; 

while(true) {
    // 스텝 수 증가
    step ++;

    // 1. 벨트 회전 -> 내구도, 로봇 배열 변화

    // 2. 회전 후 로봇의 이동 조건 확인 -> 이동 가능하다면 & 이동 후 로봇의 위치 & 내구도 처리

    // 3. 로봇 올리기 조건 확인

    // 4. 종료 조건 확인 -> break를 통해 while문 탈출
}

// [output]: step 수 출력

1. 벨트 회전

            int last = belt[2*N-1];
            System.arraycopy(belt, 0, belt, 1, 2*N-1); // System.arraycopy(src,srcPos,dest,destPost, length)
            belt[0] = last;

            boolean[] newRobots = new boolean[N];
            for(int i=0; i<N-1; i++) newRobots[i+1] = robots[i];
            robots = newRobots;
            robots[N-1] = false; // 마지막 위치에 오면 내림

• belt 배열 회전 마지막 원소 값을 저장한 후, 원ㅇ본 배열을 복사해 0번째 인덱스에 마지막 원소값 씌우기
• robots 배열 변화 새로운 배열 newRobots 배열에 1칸씩 당겨진 값을 저장
• 마지막 위치(N-1인덱스)에서의 로봇 제거

2. 로봇의 이동

            for(int i=N-2; i>=0; i--){
                if(robots[i] && !robots[i+1] && belt[i+1]>0){
                    robots[i]=false;
                    robots[i+1]=true;
                    belt[i+1]--;
                }
            }
            robots[N-1] = false;

• 가장 먼저 올라간 로봇부터 뒤로 1칸씩 이동 → 뒤에서부터 for문으로 처리
• i번째 위치 한 로봇 → i+1의 위치로 옮기기
• 옮긴 위치 (i+1)의 내구도 감소시키기
• for문으로 모든 로봇을 옮긴 후 N-1에 위치한 로봇 제거하기 (내리기)

3. 로봇 올리기

            if(belt[0]>0 && !robots[0]){
                robots[0]=true;
                belt[0]--;
            }

• 조건: 0번 인덱스의 내구도가 0보다 크고 로봇이 없을 경우
• 로봇을 올리고 내구도 1 감소시키기

4. 종료 조건

                int zeroCount = 0;
            for(int val : belt) if(val==0) zeroCount++;
            if(zeroCount >= K) break;

4. 코드

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

        // [input]
        String[] tmp = br.readLine().split(" ");
        N = Integer.parseInt(tmp[0]);
        K = Integer.parseInt(tmp[1]);

        // 0-based
        String[] temp = br.readLine().split(" ");
        int[] belt = new int[2*N];

        for(int i=0; i<N*2; i++) {
            belt[i] = Integer.parseInt(temp[i]);
        }

        // [logic]
        boolean[] robots = new boolean[N];

        int step = 0;
        while(true){
            step++;

            // 1. 벨트 회전
            int last = belt[2*N-1];
            System.arraycopy(belt, 0, belt, 1, 2*N-1); // System.arraycopy(src,srcPos,dest,destPost, length)
            belt[0] = last;

            boolean[] newRobots = new boolean[N];
            for(int i=0; i<N-1; i++) newRobots[i+1] = robots[i];
            robots = newRobots;
            robots[N-1] = false; // 마지막 위치에 오면 내림

            // 2. 로봇 이동
            for(int i=N-2; i>=0; i--){
                if(robots[i] && !robots[i+1] && belt[i+1]>0){
                    robots[i]=false;
                    robots[i+1]=true;
                    belt[i+1]--;
                }
            }
            robots[N-1] = false;

            // 3. 로봇 올리기
            if(belt[0]>0 && !robots[0]){
                robots[0]=true;
                belt[0]--;
            }

            // 4. 종료 조건
            int zeroCount = 0;
            for(int val : belt) if(val==0) zeroCount++;
            if(zeroCount >= K) break;
        }

        // 출력
        System.out.println(step);


    }
}

5. De-fault

fault-1. 배열의 회전: 내구도 배열

배열 회전 방법

1. 배열 복사 (System.arraycopy(src,srcPos,dest,destPost, length) )
2. 큐(Deque) 자료구조 사용

              // 배열을 오른쪽으로 1칸 회전
        int last = deque.removeLast();  // 마지막 요소 제거
        deque.addFirst(last);           // 마지막 요소를 첫 번째로 추가

        // 배열을 왼쪽으로 1칸 회전
        int first = deque.removeFirst();  // 첫 번째 요소 제거
        deque.addLast(first);             // 첫 번째 요소를 마지막으로 추가

fault-2. 로봇을 이동시킬 때: for문 처리

로봇의 이동은 벨트가 회전한 후 뒤에서 앞으로 이동해야 하므로 for문을 뒤에서부터 작성해야 함

뒤에서부터 처리해야 하는 이유?

앞에서부터 처리할 경우 이미 이동한 로봇을 덮어쓰게 되어 로봇이 이동하지 않는 오류가 발생

시간 복잡도

1. 벨트 회전 (O(N)) System.arraycopy(belt, 0, belt, 1, 2*N-1)를 사용한 배열의 회전
2. 로봇 이동 (O(N)) 한 번에 벨트의 크기 N 만큼 반복
3. 로봇 올리기 (O(1)) 한 번의 조건 체크와 연산
4. 종료 조건 체크 (O(N)) belt 배열을 1번 순회

⇒ 각 시뮬레이션 단계에서 수행하는 연산은 최대 O(N) 시간이 걸림

시뮬레이션을 최대 K번 반복해야 하기 때문에, 전체 시간 복잡도는 O(N * K)

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요. 알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂

1-1. 파일 시스템이란?

사용자가 데이터를 효율적으로 저장, 접근, 관리할 수 있도록 해주는 핵심 메커니즘이자, 보조 기억 장치(하드 디스크, SSD 등)의 물리적인 공간을 논리적인 파일과 디렉토리 형태로 추상화해주는 체계

• 파일 시스템의 궁극적인 목저은 보조 기억 장치에 저장된 데이터를 사용자가 편리하게 이용하도록 돕는 것

핵심 특징 및 역할

1. 커널 영역 동작 파일 시스템의 핵심 기능(메모리 할당, 디스크 I/O 등)은 안정성이 중요한 커널 모드에서 실행됨
2. 목적 (CRUD) 파일의 생성(Create), 읽기(Read), 수정(Update), 삭제(Delete) 기능을 원활하고 안정적으로 수행함
3. 계층적 구조 파일을 관리하기 쉬운 트리 구조로 구성하여 파일 탐색 및 분류를 용이하게 함
4. 보조 저장소 관리 파일 자체 뿐만 아니라, 파일을 저장하는 디스크 공간(빈 공간, 할당된 공간)도 효율적으로 관리함
5. 무결성 메커니즘 시스템 충돌이나 전원 문제 발생 시에도 데이터의 손상(파일 무결성)을 최소화하고 복구할 수 있는 메커니즘(e.g. 저널링)을 제공

2. 파일과 디렉토리

2-1. 파일 (File)

• 사용자가 인식하는 정보의 논리적인 저장 단위
• 파일은 이름, 속성(유형, 크기, 생성 시간, 접근 권한 등), 데이터를 가짐
• OS는 이러한 속성은 파일 제어 블록 (FCB, File Control Block)에 저장하여 관리함

파일의 구성 요소

• 메타 영역 (Metadata Area):
  • 파일 자체의 데이터가 아닌, 파일을 설명하는 정보(속성)를 저장합니다.
  • 포함 내용: 파일 이름, 파일의 데이터가 저장된 위치 주소, 크기, 소유자, 접근 권한, 생성/수정/접근 시간, 삭제 여부 등.
  • 이 메타 정보를 저장하는 대표적인 구조가 FCB (File Control Block) 또는 Inode (아이노드)입니다.
• 데이터 영역 (Data Area):
  • 실제 파일의 내용(바이너리 코드, 텍스트, 이미지 등)이 저장되는 영역입니다.

2-2. 디렉토리 (Directory)

• 파일을 계층적으로 묶어 구조화하고 관리하는 도구
• 파일 이름과 해당 파일을 찾기 위한 정보를 매핑하여 저장함

디렉토리 구조

1. 단일 레벨 디렉토리 (Single-Level Directory) 모든 파일이 하나의 디렉터리 아래에 저장됨
2. 2단계 디렉토리
3. 계층적/트리 구조 디렉토리

3. 파일 할당 방식

파일 시스템은 파일의 논리적인 블록을 디스크의 물리적인 블록에 어떻게 대응시켜 저장할지를 결정함

1. 연속 할당(Contiguous Allocation)

   파일의 모든 데이터 블록을 디스크의 연속된 물리적 블록에 저장함

   [+] 순차 접근 및 직접 접근이 매우 빠르고, 구현이 단순함

   [-] 파일 크기 변경이 어렵고, 외부 단편화 문제가 심각하게 발생함

2. 연결 할당(Linked Allocation) 파일의 각 데이터 블록을 디스크에 흩어져 저장됨 각 블록은 다음 블록의 주소를 포인터 형태로 저장하여 연결함 [+] 외부 단편화가 발생하지 않고, 파일 크기 변경이 용이함 [-] 직접 접근이 불가능하고 순차 접근만 가능하며, 포인터 저장 공간으로 인한 낭비가 발생하고, 포인터 손상 시 데이터 접근이 끊어지는 신뢰성 문제

3. 인덱스 할당(Indexed Allocation) 파일의 모든 디스크 블록 주소를 모아놓은 인덱스 블록을 사용함 파일 접근 시 인덱스 블록을 먼저 참조하여 데이터의 위치를 파악함 [+] 직접 접근이 가능하고, 외부 단편화가 없음 [-] 인덱스 블록을 위한 추가적인 공간이 필요하며, 대용량 파일의 경우 인덱스 블록을 관리하는 것이 복잡해짐

1. 메모리

프로세스가 메모리를 어떻게 사용하는가 → OS가 이를 어떻게 효율적으로 관리하는가

1-1. 메모리 계층 구조

CPU~디스크까지 어떤 계층이 있는가?

1-2. 지역성의 원리 (Principle of Locality)

모든 메모리 관리 기법의 핵심 전제

CPU가 데이터를 접근할 때 특정 영역을 집중적으로 접근하는 경향

• 시간적 지역성: 최근에 사용된 데이터는 곧 다시 사용될 가능성이 높음
• 공간적 지역성: 현재 참조된 주소와 가까운 주소의 내용이 곧 참조될 가능성이 높음

2. 캐시 메모리 (Cache Memory)

CPU는 왜 캐시가 필요한가? → CPU 속도 vs RAM 속도의 차이 (메모리 병목 문제)

CPU의 메모리 접근 속도를 보완하기 위한 하드웨어적 메모리 관리 기법

OS가 직접 개입하지 않으며, CPU와 MMU 수준에서 관리됨

2-1. 기본 동작

• 캐시 라인(Cache Line): 캐시가 데이터를 저장하는 최소 단위
• Cache Hit (적중) / Miss (실패): 데이터가 캐시에 있을 때와 없을 때의 처리

2-2. 주소 매핑 기법

데이터가 RAM에서 캐시로 올라올 때 어느 위치에 저장될지 결정하는 방법

• 직접 매핑 (Direct Mapping): 가장 단순하지만 충돌(Conflict Miss)이 자주 발생합니다.
• 완전 연관 매핑 (Fully Associative Mapping): 충돌은 적지만 비용이 높고 탐색이 느립니다.
• 집합 연관 매핑 (Set-Associative Mapping): 두 방식의 절충안이며 현대 시스템에서 주로 사용됩니다.

1-2. 메인 메모리 & 프로세스 주소 공간

RAM이 어떻게 사용되는가?

• 프로그램 실행 시 Code / Data / Heap / Stack 구조로 메모리 배치
• 프로세스마다 독립된 주소 공간을 가짐
• 논리 주소(Logical)와 물리 주소(Physical)의 구분 등장
• 여기서 OS는 논리 주소 → 물리 주소 매핑을 관리해야 함

➡ 이 논리 주소 매핑을 효율적으로 관리하기 위한 기술이 가상 메모리

논리 주소 vs 물리 주소

• 논리 주소(Logical Address): CPU가 생성하는 주소 (가상 주소, Virtual Address)
• 물리 주소(Physical Address): 실제 RAM 상의 주소

운영체제는 논리 주소 → 물리 주소 변환을 통해 프로세스마다 독립적인 주소 공간을 제공하며, 이것이

가상 메모리 시스템의 핵심 동작 원리

MMU (Memory Management Unit)

MMU는 CPU 안에 내장된 하드웨어로, 주소 변환(Address Translation) 을 수행함

• 논리 주소를 물리 주소로 변환
• 페이지 테이블(Page Table) 참조
• 접근 권한 체크(읽기/쓰기/실행 여부)
• 캐시 및 TLB 관리

주소 공간의 구조

프로세스가 실행될 때, 운영체제는 프로세스마다 독립적은 주소공간을 제공함

주소공간은 일반적으로 다음 4개의 영역으로 구성됨

메모리 바인딩

주소를 결정하는 시점에 따라 3가지로 구분됨

3. 가상 메모리 (Virtual Memory)

메모리 용량을 확장하고, 프로세스 간 메모리 독립성을 보장하는 OS 관리 기법

왜 필요한가? 물리적 메모리 한계 극복, 메모리 보호, 다중 프로그래밍 효율성 증대

• 물리적으로 전재하지 않는 메모리를 마치 존재하는 것처럼 사용 → 셀제 RAM보다 큰 공간을 사용하는 프로그램도 문제없이 실행할 수 있도록 하는 논리적 메모리 확장 기법
• 프로세스마다 독립된 논리적 주소 공간을 제공하고, 필요한 데이터만 실제 물리 메모리(RAM)에 적재

[주소 공간 구조]

프로세스는 OS로부터 가상 주소 공간(Virtual Address Space)을 할당받는데

이 가상 주소는 실제 물리 주소로 직접 연결되지 않고,

MMU(Memory Management Unit)가 페이지 테이블(Page Table)을 통해 변환(mapping)

3-1. 기본 동작: 페이징 기법 (Paging)

가상 메모리는 일반적으로 페이징 기법을 사용함

• 가상 메모리와 물리 메모리를 같은 크기의 블록 단위로 나눔
  • 가상 메모리의 단위 → 페이지(Page)
  • 물리 메모리의 단위 → 프레임(Frame)
• 페이지와 프레임은 1:1로 매핑됨

⇒ 즉, OS는 필요할 때만 디스크에서 데이터를 메모리에 수요에 따라(Demand Paging)

4. 페이징 & 세그멘테이션

페이징과 세그멘테이션 모두 프로세스의 메모리 공간을 비연속적으로 물리 메모리에 할당하여 가상 메모리를 구현하는 기법

두 기법의 주요 차이점은 메모리를 나누는 단위와 기준에 있음

1) 페이징 (Paging)

메모리를 고정된 크기의 조각(Page/ Frame)으로 나누어 관리하여 외부 단편화를 완전히 제거함

대신 페이지 크기 때문에 발생하는 내부 단편화가 존재함

장점 (Pros)

1. 외부 단편화 제거: 메모리가 고정된 크기의 프레임 단위로 관리되어 외부 단편화가 발생하지 않음
2. 단순한 메모리 관리: 할당/해제가 프레임 단위로 이루어져 빈 공간 관리가 단순함
3. 프로그래머 투명성: 주소 변환이 OS와 MMU에 의해 처리되어 프로그래머는 신경 쓸 필요가 없음

단점 (Cons)

1. 내부 단편화 발생: 프로세스 크기가 페이지 크기의 정수배가 아닐 경우, 마지막 페이지에서 사용되지 않는 공간이 발생함
2. 페이지 테이블 오버헤드: 모든 프로세스가 페이지 테이블을 유지해야 하므로, 테이블 저장 공간 및 크기 관리 비용이 발생함
3. 느린 주소 변환: 물리 주소 변환을 위해 최소 두 번의 메모리 접근이 필요하여 속도가 느려짐 (TLB를 통해 완화됨)

2) 세그멘테이션 (Segmentation)

프로그램의 코드, 데이터, 스택 등 의미 있는 논리적 단위(Segment)로 나누어 관리함

사용자 관점의 메모리 구조를 반영하지만, 크기가 가변적이라 외부 단편화 문제가 발생할 수 있음

장점 (Pros)

1. 내부 단편화 최소화/제거: 세그먼트 크기가 논리적 크기와 정확히 일치하여 내부 단편화가 발생하지 않음
2. 효율적인 보호 및 공유: 코드/데이터 등 논리적 단위로 분할되어 공유 및 접근 권한 설정이 용이함
3. 프로그래머 편의성: 프로그램 구조에 따라 메모리를 구성하므로 디버깅 및 관리가 직관적임

단점 (Cons)

1. 외부 단편화 발생: 세그먼트 크기가 가변적이어서, 메모리 할당/해제 시 크기가 다른 빈 공간이 발생함
2. 복잡한 메모리 관리: 외부 단편화 해결을 위해 메모리 압축(Compaction) 등 복잡한 기법이 요구됨
3. 가변적인 크기 관리: 가변적인 세그먼트 크기에 맞춰 적합한 빈 공간을 찾는 최적화 과정이 복잡함

페이지 교체 알고리즘

프로세스가 접근하려는 페이지가 물리 메모리(RAM)에 없을 때 페이지 폴트(Page Fault) 발생

→ 해당 페이지를 디스크에서 물리 메모리로 가져와야 하는데

물리 메모리의 모든 프레임이 이미 사용중인 경우, OS는 현재 메모리에 있는 페이지 중 하나를 희생시켜 공간을 확보함 (Swap Out)

이 때 어떤 페이지를 희생시킬것인가를 결정하는 규칙이 페이지 교체 알고리즘

• 목표: 페이지 폴트 발생 확률의 최소화 가장 오랫동안 사용되지 않을 것으로 예상되는 페이지를 교체 대상으로 선택해야 함

주요 알고리즘

페이지 교체 알고리즘은 대체로 지역성의 원리에 기반하여 작동함

1) OPT (Optimal, 최적) 알고리즘

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체함
• 페이지 폴트율이 가장 낮음 다른 알고리즘 성능 평가의 기준(Benchmark)이 됨
• [+] 이론적으로 최상의 성능을 보장함
• [-] CPU가 미래 접근 순서를 미리 알 수 없어 실제 구현은 불가능함

2) FIFO (First-In, First-Out, 선입선출)

• 물리 메모리에 가장 먼저 들어온(가장 오래된) 페이지를 교체함
• 구현이 매우 간단함 페이지 유입 시간만 추적함
• [+] 단순한 구현
• [-] 오래되었어도 자주 사용되는 페이지를 교체할 수 있어 효율이 나쁨 ’벨라디의 모순(Belady's Anomaly)' 현상 발생 가능성이 있음

3) LRU (Least Recently Used, 최소 최근 사용)

• 가장 오랫동안 사용되지 않은 페이지를 교체함 (시간적 지역성 기반 예측)
• OPT 다음으로 좋은 성능을 보임. 가장 이상적인 실용 알고리즘으로 평가됨
• [+] 지역성의 원리를 잘 반영하여 페이지 폴트율이 낮음
• [-]모든 페이지의 최근 사용 시간 기록에 필요한 하드웨어적 오버헤드가 매우 큼

4) LFU (Least Frequently Used, 최소 빈도 사용)

• 물리 메모리 페이지 중 가장 적게 사용된 횟수를 가진 페이지를 교체함
• 페이지의 사용 빈도에 초점을 맞춤
• [+] 오랫동안 메모리에 있었더라도 자주 사용된 페이지를 보호함
• [-] 초기에 집중 사용 후 현재는 사용되지 않는 페이지가 계속 메모리에 남는 문제 발생 가능함

1-1. 교착 상태란?

2개 이상의 스레드가 서로가 가지고 있는 자원을 기다리며 영원히 멈춰 버리는 상태 (순환 대기)

→ 자원 취득 순서 / 타임 아웃 / 검출 알고리즘 필요

• e.g. 식사하는 철학자 문제

[교착 상태를 해결하기 위해서]

1. 교착 상태가 발생했을 때 상황을 표현
2. 교착 상태가 일어나는 근본적 이유 이해

1-2. 자원 할당 그래프

교착상태가 어떤 조건에서 발생하는지 파악할 수 있음

• 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

c.f. 식사하는 철하자의 자원할당그래프

• 교착 상태가 일어난 그래프는 자원할당그래프가 원의 형태를 띄고 있음

  

1-3. 교착 상태 발생 조건 (Coffman의 4가지 조건)

교착 상태는 아래 4가지 조건이 모두 동시에 만족될 때 발생함

1. 상호 배제 (Mutual Exclusion) 자원은 한 번에 오직 하나의 프로세스만 사용할 수 있음
2. 점유와 대기(hold & wait) 자원을 할당 받은 상태에서 다른 자원을 기다리고 있는 상태
3. 비선점 (No Preemption) 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗을 수 없음
4. 원형 대기 (Circular Wait) 프로세스들이 원의 형태로 자원을 대기하는 형태

1-4. 교착 상태 해결 방법

교착 상태를 해결하는 방법으로는 크게 3가지가 있음

: 예방, 회피, 검출 후 회복

1) 교착 상태 예방 (Prevention)

애초에 교착 상태가 발생하지 않도록

교착 상태 조건(4가지) 중 하나를 없애기

1. 상호 배제 X → 모든 자원을 공유 가능하게 만들기 현실적으로 모든 자원을 공유하는 것은 불가능함

2. 점유와 대기 X → 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분 → 자원의 활용률을 낮출 수 있는 방식

3. 비선점 조건 X → 선점이 가능한 자원 (e.g. CPU)에 한해 효과적 → 모든 자원이 선정 가능한 것은 아님

4. 원형 대기 조건 X → 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당

   

   하지만 모든 자원에 번호를 붙이는 작업은 어려움 어떤 자원에 어떤 번호를 부여하는지에 따라 활용률이 다름

2) 교착 상태 회피 (Avoidance)

교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주함

교착 상태가 발생하지 않을만큼 조심하여 할당함

배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분함

• 안전 순서열: 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서 e.g. A-B-C: 교착 상태 , A-C-A: 교착 상태 X → 안전 순서열!
• 안전 상태: 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태 → 안전 순서열이 있는 상태
• 불안전 상태: 교착 상태가 발생할 수도 있는 상태 → 안전 순서열이 없는 상태
• 교착 상태 회피는 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식 항시 안전 상태를 유지하도록 자원을 할당함 e.g. 은행원 알고리즘

3) 교착 상태 검출 후 회복 (Detection & Recovery)

교착 상태의 발생을 인정하고 사후에 조치하는 방식

프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복

• 선점을 통한 회복 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 프로세스 강제 종료를 통한 회복 교착 상태에 놓인 프로세스 모두 강제 종료 (작업 내역을 잃을 위험) 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (오버헤드)