치자피즈

최단 경로를 찾는 데 자주 사용되는 알고리즘은 여러 가지가 있다.

1. One-To-One 한 지점에서 다른 특정 지점까지의 최단경로 구하기

2. One-To-All 한 지점에서 다른 모든 지점까지의 최단경로 구하기

3. All-To-All 모든 지점에서 모든 지점까지의 최단경로 구하기

문제의 조건마다 사용되는 알고리즘이 다르기때문에 적절히 선택해서 사용해야 한다.

그러려면 어떤 알고리즘이 있는지 알아야 할 것!

1. 다익스트라(Dijkstra) 알고리즘

목적

단일 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 것

원하는 목적지가 나오면 종료할 수도 있음

그래프 유형

가중치가 있는 방향성 또는 무방향성 그래프 - 음수 가중치 허용 X

시간복잡도

 O((V+E)⋅log⁡V)

구현방식

1. 시작 노드의 거리를 0으로 설정하고, 다른 노드는 무한대로 초기화

2. 아직 처리되지 않은 노드 중 거리가 가장 짧은 노드를 선택

3. 선택된 노드를 기준으로 인접 노드의 거리 갱신

4. 모든 노드를 처리할 때까지 반복

특징

음수 가중치가 없을 경우 가장 빠르고 효율적

우선순위 큐(힙)를 사용하여 효율적으로 구현 가능

자세한정리

2. 벨만포드(Bellman-Ford) 알고리즘

목적

단일 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 것

그래프 유형

가중치가 있는 방향성 그래프 -  음수 가중치 허용 O

시간복잡도

O(V⋅E)

구현방식 

1. 시작 노드에서 모든 노드의 거리를 무한대로 초기화하고, 시작 노드의 거리를 0으로 설정

2. 모든 간선을 V - 1 번 반복하여 탐색 

3. V - 1 번의 반복 이후에도 거리 갱신이 발생한다면, 음수 사이클이 존재한다고 판단.

https://great-park.tistory.com/134

특징

음수 가중치 처리 가능

음수 사이클이 존재할 경우 알 수 있음

자세한 정리

3. 플로이드-워셜(Floyd-Warshall) 알고리즘

목적

모든 정점 간의 최단 경로를 구하는 것

그래프 유형

가중치가 있는 방향성 그래프 - 음수 가중치 허용 O

시간복잡도

O(V^3)

구현방식

1. V x V 크기의 거리 행렬 d[i][j]를 초기화

   ex) d[i][j]는 노드 i에서 j로 직접 연결된 간선의 가중치 (없으면 무한대, 자기 자신은 0)

2. 중간 노드를 하나씩 추가하면서 최단경로를 갱신

   ex) d[i][j] = min(d[i][j], d[i][k]+d[k][j])

3. 위 과정을 모든 노드 쌍에 대해 반복

특징

모든 노드 간의 최단 경로를 동시에 계산 가능

음수 가중치 간선은 허용되지만, 음수 사이클이 있을 경우 잘못된 결과가 나올수도 있음

동적 계획법 기반

자세한 정리

그럼 얘네를 어떤 문제에 써야할까??

1. 단일 시작점 문제 -> 다익스트라 or 벨만포드

음수 가중치가 없다? => 다익스트라

음수 가중치가 있다? => 벨만포드

2. 모든 쌍 최단 경로 문제: 플로이드-워셜

근데 플로이드-워셜의 시간 복잡도는 V^3... 정점이 많을수록 매우 느려짐 

그래서 정점 수가 많으면 존슨 알고리즘도 있다

근데 음수 사이클이 있으면??

음수 사이클이 있는지 판별하는 문제인지 확인

판별만 하는 문제면 벨만포드로 확인해서 해결

그래도 최단거리 찾으라고 하면 음수 사이클이 포함된 경로 사용하지 않게 하는 처리하기

🌳 AVL 트리(Adelson-Velsky and Landis Tree)란?

AVL 트리는 이진 탐색 트리(Binary Search Tree, BST)의 일종으로,
트리의 균형을 유지하여 탐색, 삽입, 삭제 연산을 O(log n) 시간 복잡도로 보장하는 자기 균형 이진 탐색 트리다.

특징

1. 균형 인수(Balance Factor, BF)
   • 어떤 노드의 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
   • 가능한 값: -1, 0, 1
   • BF = 2 또는 -2가 되면 불균형 → 회전(Rotation) 필요
2. 자동 균형 유지
   • 삽입/삭제 시 불균형 발생 → 회전 연산으로 균형 유지
3. 탐색, 삽입, 삭제 모두 O(log n)

여기서 주목할 점은 균형을 유지하기위해 하는 회전 연산이다.

근데 왜 균형을 유지해야할까? 얘도 어차피 이진트리 아닌가? 라고 생각이 들수도 있다.

하지만 이진트리에 값을 넣다보면 아래의 예처럼 한쪽으로 치우지는 경우가 생긴다

이러면 분기로 나뉘어 정보의 탐색이 빨라진다는 이진트리의 장점이 없어지게 된다.

그래서 나온게 트리의 높이를 삽입할때마다 조절해 균형을 맞추는 자기 균형 이진 트리이다.

얼마나 효율적으로  균형을 맞추는지가 자기 균형 이진 트리에서 재밌게 볼 수 있는 점일 것 같다.

하여튼  avl 트리는 이러한 문제를 방지하기 위해 한쪽이 다른쪽에 비해 높이가 2 이상 차이나면 트리의 구조를 회전을 통해 수정해준다.

avl 트리는 4가지 회전을 통해 불균형을 해결한다.

1. LL회전 (단순 오른쪽 회전, Right Rotation)

• 왼쪽-왼쪽(Left-Left) 불균형 발생 시 사용
• 왼쪽 자식이 다시 왼쪽 자식을 갖는 경우

 30을 오른쪽으로 회전 → 20이 루트가 됨

2. RR 회전 (단순 왼쪽 회전, Left Rotation)

• 오른쪽-오른쪽(Right-Right) 불균형 발생 시 사용
• 오른쪽 자식이 다시 오른쪽 자식을 갖는 경우

10을 왼쪽으로 회전 → 20이 루트가 됨

3. LR 회전 (좌-우 회전, Left-Right Rotation)

• 왼쪽-오른쪽(Left-Right) 불균형 발생 시 사용
• 왼쪽 자식의 오른쪽 서브트리가 불균형을 일으킨 경우

왼쪽 자식(10)을 왼쪽 회전(RR)

부모 노드(30)를 오른쪽 회전(LL)

4. RL 회전 (우-좌 회전, Right-Left Rotation)

• 오른쪽-왼쪽(Right-Left) 불균형 발생 시 사용
• 오른쪽 자식의 왼쪽 서브트리가 불균형을 일으킨 경우

오른쪽 자식(30)을 오른쪽 회전(LL)

부모 노드(10)를 왼쪽 회전(RR)

구현 코드 GUI

실행환경

java 11 이상의 intellij 

새프로젝트생성 -> 왼쪽 제너레이터 밑에 javaFX로 생성 후  아래 코드를 실행

구현시 주의점

기본적으로 입력은 이진트리와 비슷하지만 각 노드에 균형인수가 추가되었다.

그리고 삽입과 삭제 시 회전 조건이 달라지는 점!

삽입은 항상 새로운 노드가 추가되기 때문에 한쪽으로만 무거워짐 → 불균형이 단방향으로 발생

삭제는 노드 제거로 인해 트리가 양방향으로 불균형해질 수 있음.
삭제로 인해 왼쪽, 오른쪽 서브트리 모두 불균형 발생 가능.

삭제가 좀 복잡하다 삭제시에 균형인수를 잘 확인할 필요가 있따.

package com.example.demo;

import javafx.application.Application;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.control.Button;
import javafx.scene.control.TextField;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
import javafx.scene.paint.Color;
import javafx.stage.Stage;

public class HelloApplication extends Application {

    private Avl root;  // 트리의 루트 노드
    private Canvas canvas;

    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void start(Stage primaryStage) {
        // 캔버스 생성
        canvas = new Canvas(800, 600);

        // 입력 필드 및 버튼 생성
        TextField inputField = new TextField();
        inputField.setPromptText("숫자 입력");
        Button insertButton = new Button("삽입");
        Button deleteButton = new Button("삭제");

        // 버튼 이벤트
        insertButton.setOnAction(e -> {
            try {
                int value = Integer.parseInt(inputField.getText());
                root = insert(root, value);
                drawTree();  // 트리 그리기
                inputField.clear();
            } catch (NumberFormatException ex) {
                inputField.setText("숫자만 입력");
            }
        });

        deleteButton.setOnAction(e -> {
            try {
                int value = Integer.parseInt(inputField.getText());
                root = delete(root, value);
                drawTree();  // 트리 그리기
                inputField.clear();
            } catch (NumberFormatException ex) {
                inputField.setText("숫자만 입력");
            }
        });

        // 레이아웃 구성
        HBox controls = new HBox(10, inputField, insertButton, deleteButton);
        controls.setAlignment(Pos.CENTER);

        BorderPane rootPane = new BorderPane();
        rootPane.setTop(controls);
        rootPane.setCenter(canvas);

        Scene scene = new Scene(rootPane, 800, 600);
        primaryStage.setTitle("이진 탐색 트리 시각화");
        primaryStage.setScene(scene);
        primaryStage.show();
    }

    // 트리 그리기
    private void drawTree() {
        GraphicsContext gc = canvas.getGraphicsContext2D();
        gc.clearRect(0, 0, canvas.getWidth(), canvas.getHeight());
        drawNode(gc, root, canvas.getWidth() / 2, 50, canvas.getWidth() / 4);
    }

    // 노드 및 연결선 그리기
    private void drawNode(GraphicsContext gc, Avl node, double x, double y, double offset) {
        if (node == null) return;

        gc.setFill(Color.LIGHTBLUE);
        gc.fillOval(x - 15, y - 15, 30, 30);
        gc.setFill(Color.BLACK);
        gc.strokeOval(x - 15, y - 15, 30, 30);
        gc.fillText(String.valueOf(node.value), x - 5, y + 5);

        if (node.left != null) {
            gc.strokeLine(x, y, x - offset, y + 50);
            drawNode(gc, node.left, x - offset, y + 50, offset / 2);
        }

        if (node.right != null) {
            gc.strokeLine(x, y, x + offset, y + 50);
            drawNode(gc, node.right, x + offset, y + 50, offset / 2);
        }
    }

    // avl tree에 삽입
    public Avl insert(Avl node, int value) {

        if (node == null) {
            return new Avl(value);
        }

        if (value < node.value) {
            node.left = insert(node.left, value);
        } else if (value > node.value) {
            node.right = insert(node.right, value);
        } else {
            // 중복 값 허용 X -> 그대로 반환
            return node;
        }

        //  서브트리 높이 업데이트
        node.left_size = getHeight(node.left);
        node.right_size = getHeight(node.right);

        // 균형 인수 계산
        int balance = node.left_size - node.right_size;

        // 회전(Rotation)으로 균형 조정

        // LL 회전
        if (balance > 1 && value < node.left.value) {
            return rightRotate(node);
        }

        // RR 회전
        if (balance < -1 && value > node.right.value) {
            return leftRotate(node);
        }

        // LR 회전
        if (balance > 1 && value > node.left.value) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RL 회전
        if (balance < -1 && value < node.right.value) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // 균형 상태 -> 그대로 반환
        return node;
    }

    // avl tree에서 삭제
    public Avl delete(Avl node, int value) {

        if (node == null) {
            return null;
        }

        if (value < node.value) {
            node.left = delete(node.left, value);
        } else if (value > node.value) {
            node.right = delete(node.right, value);
        } else {
            // 삭제할 노드를 찾음

            // 자식이 없거나 한 개일 때
            if (node.left == null || node.right == null) {
                Avl temp = (node.left != null) ? node.left : node.right;

                // 자식이 없는 경우
                if (temp == null) {
                    node = null;
                } else { // 자식이 하나인 경우
                    node = temp;
                }
            } else {
                // 자식이 두 개인 경우 -> 오른쪽 서브트리에서 최소값 찾기
                Avl successor = getMinValueNode(node.right);

                // 후계자의 값을 복사
                node.value = successor.value;

                // 후계자 노드 삭제
                node.right = delete(node.right, successor.value);
            }
        }

        // 노드가 null이면 그대로 반환
        if (node == null) {
            return null;
        }

        //  서브트리 높이 업데이트
        node.left_size = getHeight(node.left);
        node.right_size = getHeight(node.right);

        // 균형 인수(Balance Factor) 계산
        int balance = node.left_size - node.right_size;

        // 불균형 해결 (회전)

        // LL 회전
        if (balance > 1 && getBalance(node.left) >= 0) {
            return rightRotate(node);
        }

        // LR 회전
        if (balance > 1 && getBalance(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RR 회전
        if (balance < -1 && getBalance(node.right) <= 0) {
            return leftRotate(node);
        }

        // RL 회전
        if (balance < -1 && getBalance(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }
    private Avl getMinValueNode(Avl node) {
        Avl current = node;

        // 가장 왼쪽 노드 탐색
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }
    private int getBalance(Avl node) {
        if (node == null) return 0;
        return getHeight(node.left) - getHeight(node.right);
    }
    // 최소값 찾기
    public int getHeight(Avl node) {
        if (node == null) return 0;
        return 1 + Math.max(node.left_size, node.right_size);
    }

    // 오른쪽회전 - LL
    private Avl rightRotate(Avl y) {
        Avl x = y.left;
        Avl T2 = x.right;

        // 회전
        x.right = y;
        y.left = T2;

        // 높이 업데이트
        y.left_size = getHeight(y.left);
        y.right_size = getHeight(y.right);
        x.left_size = getHeight(x.left);
        x.right_size = getHeight(x.right);

        return x;
    }
    // 왼쪽회전 - RR
    private Avl leftRotate(Avl x) {
        Avl y = x.right;
        Avl T2 = y.left;

        // 회전
        y.left = x;
        x.right = T2;

        // 높이 업데이트
        x.left_size = getHeight(x.left);
        x.right_size = getHeight(x.right);
        y.left_size = getHeight(y.left);
        y.right_size = getHeight(y.right);

        return y;
    }
    // Avl 노드 클래스
    public class Avl {
        int value;
        int left_size;
        int right_size;
        Avl left;
        Avl right;

        public Avl(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
            this.left_size = 0;
            this.right_size = 0;
        }
    }

}

트리의 기본용어

• 노드(Node): 데이터를 저장하는 기본 단위
• 루트(Root): 트리의 최상위 노드
• 자식(Child): 특정 노드의 하위 노드
• 부모(Parent): 자식 노드의 상위 노드
• 리프(Leaf): 자식이 없는 노드
• 서브트리(Subtree): 특정 노드와 그 하위 트리

이진트리의 특징

• 자식 노드의 수: 최대 2개 (0~2)
• 재귀적 구조: 트리의 하위 구조도 트리 형태
• 균형도(Balance): 노드의 배치가 성능에 영향을 미침

이진 트리의 종류

1. 포화 이진 트리(Full Binary Tree)
   • 모든 노드가 0개 또는 2개의 자식을 가짐
   • 리프 노드는 동일한 깊이에 위치
2. 완전 이진 트리(Complete Binary Tree)
   • 마지막 레벨을 제외하고 모든 레벨이 꽉 찬 트리
   • 마지막 레벨은 왼쪽부터 채워짐
3. 편향 이진 트리(Skewed Binary Tree)
   • 한쪽 방향(왼쪽 또는 오른쪽)으로만 노드가 추가된 트리
4. 이진 탐색 트리(Binary Search Tree, BST)
   • 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
   • 빠른 검색, 삽입, 삭제 가능 (O(log n))
5. 균형 이진 트리(Balanced Binary Tree)
   • 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하
   • 예시: AVL 트리, 레드-블랙 트리

아래는 이진탐색트리 구현 후 GUI 추가한 코드

실행환경

java 11 이상의 intellij 

새프로젝트생성 -> 왼쪽 제너레이터 밑에 javaFX로 생성 후  아래 코드를 실행

package com.example.demo;

import javafx.application.Application;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.control.Button;
import javafx.scene.control.TextField;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
import javafx.scene.paint.Color;
import javafx.stage.Stage;

public class HelloApplication extends Application {

    private Binary root;  // 트리의 루트 노드
    private Canvas canvas;

    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void start(Stage primaryStage) {
        // 캔버스 생성
        canvas = new Canvas(800, 600);

        // 입력 필드 및 버튼 생성
        TextField inputField = new TextField();
        inputField.setPromptText("숫자 입력");
        Button insertButton = new Button("삽입");
        Button deleteButton = new Button("삭제");

        // 버튼 이벤트
        insertButton.setOnAction(e -> {
            try {
                int value = Integer.parseInt(inputField.getText());
                root = insert(root, value);
                drawTree();  // 트리 그리기
                inputField.clear();
            } catch (NumberFormatException ex) {
                inputField.setText("숫자만 입력");
            }
        });

        deleteButton.setOnAction(e -> {
            try {
                int value = Integer.parseInt(inputField.getText());
                root = delete(root, value);
                drawTree();  // 트리 그리기
                inputField.clear();
            } catch (NumberFormatException ex) {
                inputField.setText("숫자만 입력");
            }
        });

        // 레이아웃 구성
        HBox controls = new HBox(10, inputField, insertButton, deleteButton);
        controls.setAlignment(Pos.CENTER);

        BorderPane rootPane = new BorderPane();
        rootPane.setTop(controls);
        rootPane.setCenter(canvas);

        Scene scene = new Scene(rootPane, 800, 600);
        primaryStage.setTitle("이진 탐색 트리 시각화");
        primaryStage.setScene(scene);
        primaryStage.show();
    }

    // 트리 그리기
    private void drawTree() {
        GraphicsContext gc = canvas.getGraphicsContext2D();
        gc.clearRect(0, 0, canvas.getWidth(), canvas.getHeight());
        drawNode(gc, root, canvas.getWidth() / 2, 50, canvas.getWidth() / 4);
    }

    // 노드 및 연결선 그리기
    private void drawNode(GraphicsContext gc, Binary node, double x, double y, double offset) {
        if (node == null) return;

        gc.setFill(Color.LIGHTBLUE);
        gc.fillOval(x - 15, y - 15, 30, 30);
        gc.setFill(Color.BLACK);
        gc.strokeOval(x - 15, y - 15, 30, 30);
        gc.fillText(String.valueOf(node.value), x - 5, y + 5);

        if (node.left != null) {
            gc.strokeLine(x, y, x - offset, y + 50);
            drawNode(gc, node.left, x - offset, y + 50, offset / 2);
        }

        if (node.right != null) {
            gc.strokeLine(x, y, x + offset, y + 50);
            drawNode(gc, node.right, x + offset, y + 50, offset / 2);
        }
    }

    // 삽입 메서드
    private Binary insert(Binary node, int value) {
        if (node == null) return new Binary(value);
        if (value < node.value) {
            node.left = insert(node.left, value);
        } else if (value > node.value) {
            node.right = insert(node.right, value);
        }
        return node;
    }

    // 삭제 메서드
    private Binary delete(Binary node, int value) {
        if (node == null) return null;

        if (value < node.value) {
            node.left = delete(node.left, value);
        } else if (value > node.value) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;

            Binary minNode = findMin(node.right);
            node.value = minNode.value;
            node.right = delete(node.right, minNode.value);
        }
        return node;
    }

    // 최소값 찾기
    private Binary findMin(Binary node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // Binary 노드 클래스
    class Binary {
        int value;
        Binary left, right;

        Binary(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }
}

실행화면

 B+Tree란?

데이터베이스 index에 자주 사용되는 자료구조

B-Tree 계열의 Balanced Tree 종류 중 하나
 

MySQL의 InnoDB 스토리지 엔진은 주로 B+ Tree를 사용한다. B+ Tree B-Tree에서 파생된 개념이다.

B+Tree는 데이터베이스 인덱스와 파일 시스템 사용에 더 적합할 수 있도록 만들어졌다.

B-Tree와 차별화되는 특징은 아래와 같다.

B+Tree의 리프 노드는 서로 연결 리스트로 서로 연결되어, 형제 노드끼리도 옮겨가며 조회할 수 있다.
연결된 리프 노드의 리스트를 따라가면서 범위 쿼리를 할 수 있어서, 범위 검색 성능이 좋다.
internal 노드에는 키만 저장되며, 이 키를 사용해서 자식 노드의 메모리 상 위치를 판단한다..

internal 노드에는 데이터의 포인터도 없으며, 오로지 키만 저장된다.
데이터를 찾기 위한 포인터도 리프 노드에만 있다.
internal 노드의 크기를 줄여 메모리 사용이 효율적이다.
실제 데이터는 리프 노드에만 저장되어 있다.

먼저 데이터를 넣어보면서 B-트리의 동작원리에 대해 알아보자

하나의 노드에 최대 2개의 값만 들어갈 수 있고 오름차순으로 정렬돼야하기때문에 위 그림처럼 삽입된다.

50은 42보단 크고 55보단 작아서 그 사이에 위치해야하는데 하나의 노드엔 최대 2개의 값만 들어갈 수 있으므로

트리의 균형을 위해 재배치해준다. 따라서 50이 상위노드로 올라가고 42와 55가 좌우로 연결된 형태로 변한다.

아까 50을 삽입했을 때처럼 55 80 90 에서 재배치를 해야하기 때문에 중간값인 80을 상위로 보낸다. 50이 담겨있던 노드는 하나를 더 담을 수 있기때문에 50 80 노드가 되고 재배치가 종료된다.

60을 넣으면 55 60 70 이렇게 정렬이 되야하는데 초과가 발생하므로 중간값인 60이 상위로 올라간다.

그런데 상위 노드에서도 50 60 80으로 초과가 발생하므로 다시 중간값인 60이 상위로 올라가며 재배치가 끝난다.

B-Tree는 이런 규칙을 따르며 트리의 균형을 유지한다.

그럼 B+Tree는 어떨까?

B-Tree의 예시처럼 42 55 50을 순서대로 삽입한 모습이다.

같은 규칙으로 한 노드에 2개 이상의 값이 들어가자 중간값인 50이 상위로 올라가는 모습이다.

하지만 리프노드가 뭔가 다르단걸 볼 수 있다.

B-Tree의 예시처럼 동일한 값을 전부 삽입한 모습이다. 

2개이상의 값이 노드에 있으면 중간값을 올리는 규칙을 따랐지만 뭔가 다른 모습이다.

바로 B+Tree는 실제 값은 전부 리프노드에만 저장되는 특징때문이다.

잘보면 삽입된 값은 전부 리프노드에서 확인할 수 있고 링크드리스트로 연결이 되어있다.

이것이 B+tree와 그냥 B-tree의 차이점이라고 할 수 있다!

B-tree는 리프 노드와 내부 노드가 각각 데이터와 포인터까지 가지고 있기 때문에 B+Tree보다 더 많은 메모리 공간을 차지한다. B+tree는 데이터는 리프 노드에만 저장되고, internal 노드는 키만 갖고 있으면 되므로, 메모리 효율이 좋다.

또한 B-tree는 순차탐색을 위한 알고리즘이 따로 필요한 반면, B+tree는 연결된 리프노드를 통해 순차탐색이 용이하다.

마지막으로 B+Tree가 DB 인덱스에 사용되었을 때 더 좋은 점에 대해서 이야기하면 아래와 같다.

 

리프 노드를 제외하고 데이터를 담아두지 않기 때문에 internal 노드의 경우, 한정된 메모리 안에 더 많은 key들을 수용할 수 있다. 

즉, 하나의 노드에 더 많은 key들을 저장하기 때문에 동일한 데이터 개수라면, 트리의 높이는 더 낮아진다. 

cache hit를 높일 수 있을 뿐만 아니라, 범위 검색이나 범위 쿼리에도 큰 강점을 갖고 있으며, 상대적으로 굉장히 느린 secondary storage에 대한 접근 횟수가 현저히 줄어든다. 

 

테이블 풀 스캔 시, B-Tree의 경우에는 데이터가 internal 노드와 리프 노드에 퍼져있기 때문에 모든 노드를 탐색해야 한다.

B+tree는 리프 노드에만 데이터가 존재하고, 존재하는 모든 데이터는 리프 노드에 있기 때문에 한 번의 선형탐색만 하면 되므로 매우 빠르다. 

LinkedList란??

변수와 다음 노드를 가리키는 정보를 가진 노드들의 집합

Java에서는 LinkedList와 ArrayList를 기본제공한다.

기본제공 메서드 

List<String> list = new ArrayList<>();  // String타입 리스트 기본 생성자 

get(int index) 

index위치의 값을 반환

contains(Object e)

해당 Object가 list에 있는지 boolean타입으로 반환

size()

list의 사이즈를 int로 반환

add(String e)

list에 String 추가

add(int index, String element)

list의 index위치에 String 추가

remove(int index)

해당 index 위치의 값을 삭제

clear()

list 초기화

직접 구현해보기 

public class Node {
    private Object data;
    private Node next;

    public Node() {
        data = null;
        next = null;
    }


    public Node(Object data) {
        this.data = data;
        next = null;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Object getData() {
        return data;
    }
    public Node getNext() {
        return next;
    }

    // 리스트 맨 뒤에 추가
    public void add(int data) {
        if(this.data == null) {
            this.data = data;
        } else {
            Node newNode = this;
            while (newNode.getNext() != null) {
                newNode = newNode.getNext();
            }
            newNode.setNext(new Node(data));
        }
    }
    // idx 위치의 값을 return
    public Object get(int idx) {
        if(size() >= idx) {
            Node current = this;
            for(int i = 0; i < idx; i++) {
                current = current.getNext();
            }
            if(current == null) {
                return null;
            } else {
                return current.getData();
            }
        } else {
            return null;
        }
    }
    // 해당위치 삭제
    public boolean delete(int idx) {

        if(size() >= idx) {
            if(idx == 0) {
                this.data = this.next.getData();
                this.next = this.next.getNext();

                return true;
            }
            Node previous = this;
            Node current = this.next;
            for(int i = 0; i < idx-1; i++) {
                previous = current;
                current = current.getNext();
            }
            if(current != null) {
                previous.setNext(current.getNext());
            } else {
                previous.setNext(null);
            }
            return true;
        } else {
            return false;
        }
    }


    // 리스트 크기
    public int size() {
        int result = 0;
        if(this.data == null) {
            return result;
        } else {
            result++;
            if (this.next != null) {
                Node current = this.next;
                while (current != null) {
                    result++;
                    current = current.getNext();
                }
            }
            return result;
        }
    }
    // 리스트 출력
    public void print() {
        Node current = this;
        while(current != null) {
            System.out.println(current.getData());
            current = current.getNext();
        }
    }
}

메인함수

import java.util.Scanner;

public class Main {

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

        Node head = new Node();
        String status;
        while(true) {
            System.out.println("삽입 - insert\n삭제 - delete\n리스트출력 - print\nN번째 인덱스 출력 - index\n종료 - exit");
            status = scanner.nextLine();
            switch(status) {
                case "insert" -> {
                    head.add(getNumber());
                }
                case "delete" -> {
                    if(head.delete(getNumber())) {
                        System.out.println("삭제되었습니다.");
                    } else {
                        System.out.println("삭제할수없습니다");
                    }
                }
                case "print" -> {
                    head.print();
                }
                case "index" -> {
                    int index =  getNumber();
                    Object result = head.get(index);
                    if(result != null) {
                        System.out.println("List의 "+index+"번 값은 "+result+"입니다.");
                    } else {
                        System.out.println("존재하지않는 번호입니다.");
                    }
                }
                default -> {
                    return;
                }
            }

        }
    }
    public static int getNumber() {
        System.out.println("숫자를 입력해주세요");
        return Integer.parseInt(scanner.nextLine());
    }
}

스택 정리해놓은 글 

바로가기

근데 이제 기본제공하는 구조체 안쓰고 해보기

public class MyStack {

    private int[] stack;
    private int top;

    /**
     * 기본 생성자
     * stack 크기 = 10
     */
    public MyStack() {
        stack = new int[10];
        top=-1;
    }
    /**
     * 기본 생성자 2
     * stack 크기 받아서 생성
     */
    public MyStack(int size) {
        stack = new int[size];
        top=-1;
    }

    /** stack에 값 넣기 = push
     *  정수를 stack에 넣음
     *
     *  top에 1을 더하고
     *  stack의 길이 이상으로 push 하려하면 배열 늘려주고 push
     *
     * @param x
     */
    public void push(int x) {
        top = top+1;
        if(size() < stack.length) {
            stack[top] = x;
        } else {
            increaseStack();
            stack[top] = x;
        }
    }

    /** stack에서 값 빼기  = pop
     *  제일 마지막에 push된 정수를 반환
     * top 위치의 정수를 빼고 top을 -1 해주고 해당값 반환
     * @return
     */
    public int pop() {

        if(size() >= 0) {
            int temp = stack[top];
            stack[top--]=0;
            return temp;
        }
        else return -1;
    }
    /** stack이 비었는지 확인
     *  top이 0보다 작으면 비어있는것 return true
     *  top이 0보다 크거나 같으면 비어있지 않은것 return false
     * @return
     */
    public boolean isEmpty() {
        return top < 0;
    }

    /** stack의 크기 확인
     *  크기를 int로 반환
      * @return
     */
    public int size() {
        return top;
    }

    /**
     * 스택의 내용을 출력해주는 함수
     */
    public void print() {
        System.out.println("┌─────┐");
        for(int i=top; i>=0; i--) {
            System.out.println("│  "+stack[i]+"  │");
            if (i == 0) {
                System.out.println("└─────┘");
            } else {
                System.out.println("├─────┤");
            }
        }
    }

    /**
     * stack 꽉차면 한칸 늘리는 함수
     */
    public void increaseStack() {
        int[] temp = new int[stack.length+1];
        System.arraycopy(stack, 0, temp, 0, stack.length);
        stack = temp;
    }

}

스택 활용

중위표기식 -> 후위표기식 전환

후위표기식 계산

문자열 뒤집기

메인함수

public class Main {
    public static void main(String[] args) {
        // 계산식 넣기
        String str = "((9-(2*1))-8)+4";

        // String을 stack으로
        MyStack myStack = UseStack.stringToStack(str);

        // 뒤집기
        myStack = UseStack.resverseStack(myStack);
        // 뒤집은거 출력
        myStack.print();
        // postfix 변환
        myStack = UseStack.convert(myStack);
        // 변환된 스택 출력
        myStack.print();

        // 변환된거 뒤집기
        myStack = UseStack.resverseStack(myStack);

        // string으로 옮기기
        StringBuilder sb = new StringBuilder();
        while(!myStack.isEmpty()) {
            char temp = (char) myStack.pop();
            System.out.print(temp+ " ");
            sb.append(temp);
        }

        // string으로 옮긴 계산식 계산하기
        System.out.println();
        System.out.println(UseStack.calc(sb.toString()));
    }
}

MyStack.javaint가 아닌 char stack으로 변경

public class MyStack {

    private char[] stack;
    private int top;

    /**
     * 기본 생성자
     * stack 크기 = 10
     */
    public MyStack() {
        stack = new char[10];
        top=-1;
    }
    /**
     * 기본 생성자 2
     * stack 크기 받아서 생성
     */
    public MyStack(int size) {
        stack = new char[size];
        top=-1;
    }

    /** stack에 값 넣기 = push
     *  정수를 stack에 넣음
     *
     *  top에 1을 더하고
     *  stack의 길이 이상으로 push 하려하면 배열 늘려주고 push
     *
     * @param x
     */
    public void push(char x) {
        top = top+1;
        if(size() < stack.length) {
            stack[top] = x;
        } else {
            increaseStack();
            stack[top] = x;
        }
    }

    /** stack에서 값 빼기  = pop
     *  제일 마지막에 push된 문자를 반환
     * top 위치의 정수를 빼고 top을 -1 해주고 해당값 반환
     * 뺄수없으면 null 반환
     * @return
     */
    public Object pop() {

        if(size() >= 0) {
            char temp = stack[top];
            top = top - 1;
            return temp;
        }
        else return null;
    }

    /**
     *  stack top 확인 = peek
     *  비어있지않다면 top의 값 보여줌 실제 pop X
     */
    public Object peek() {
        if(size() >= 0) {
            return stack[top];
        }
        else {
            return null;
        }
    }


    /** stack이 비었는지 확인
     *  top이 0보다 작으면 비어있는것 return true
     *  top이 0보다 크거나 같으면 비어있지 않은것 return false
     * @return
     */
    public boolean isEmpty() {
        return top < 0;
    }

    /** stack의 크기 확인
     *  크기를 int로 반환
      * @return
     */
    public int size() {
        return top;
    }

    /**
     * 스택의 내용을 출력해주는 함수
     */
    public void print() {
        System.out.println("┌─────┐");
        for(int i=top; i>=0; i--) {
            System.out.println("│  "+stack[i]+"  │");
            if (i == 0) {
                System.out.println("└─────┘");
            } else {
                System.out.println("├─────┤");
            }
        }
    }

    /**
     * stack 꽉차면 한칸 늘리는 함수
     */
    public void increaseStack() {
        char[] temp = new char[stack.length+1];
        System.arraycopy(stack, 0, temp, 0, stack.length);
        stack = temp;
    }

}

UseStack.java

import java.util.ArrayList;
import java.util.List;

public class UseStack {

    /**
     * String을 stack으로
     * String을 charArray로 바꾸고 stack에 넣기
     * @param str
     * @return
     */
    static public MyStack stringToStack(String str) {
        MyStack stack = new MyStack();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            stack.push(chars[i]);
        }
        return stack;
    }

    /**
     * 스택 뒤집기
     * 새로운 스택 하나 생성해서
     * 기존 스택 pop한걸 새로운 스택에 push
     * @param stack
     * @return
     */
    static public MyStack resverseStack(MyStack stack) {
        MyStack newStack = new MyStack(stack.size());
        for (int i = stack.size(); i >= 0; i--) {
            newStack.push((char) stack.pop());
        }
        return newStack;
    }

    /**
     * 중위표기식을 후위표기식으로 변환
     *
     * @param stack
     * @return
     */
    static public MyStack convert(MyStack stack) {
        // 결과 스택
        MyStack newStack = new MyStack(stack.size());
        // 연산자 스택
        MyStack opStack = new MyStack(stack.size());

        // 후위표기식으로 변환
        for(int i = stack.size(); i >= 0; i--) {
            char c = (char) stack.pop();
                switch (c) {
                    // 피연산자는 바로 결과배열에 추가
                    // 연산자는 경우에 따라 달라짐
                    case '(' -> {
                        opStack.push(c);
                    }
                    case ')' -> {
                        // ( 가 나올때까지 연산자스택에서 pop해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.pop();
                            if(temp == '(') {
                                break;
                            }
                            newStack.push(temp);
                        }
                    }
                    case '+', '-' -> {
                        // 자기보다 낮은거 만날때까지 연산자스택에서 pop 해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.peek();
                            if(temp == '(' ) {
                                break;
                            } else {
                                newStack.push((char) opStack.pop());
                            }
                        }
                        opStack.push(c);
                    }
                    case '*', '/' -> {
                        // 자기보다 낮은거 만날때까지 연산자스택에서 pop 해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.peek();
                            if(temp == '+' || temp == '-' || temp == '(') {
                                break;
                            } else {
                                newStack.push((char) opStack.pop());
                            }
                        }
                        opStack.push(c);
                    }

                    // c가 알파벳이면 바로 결과스택에 추가
                    default -> {
                        newStack.push(c);
                    }
                }

        }
        // 남은 연산자가 있으면 다 pop해서 결과스택에 넣어주고 결과스택을 return
        while(!opStack.isEmpty()) {
            newStack.push((char)opStack.pop());
        }
        return newStack;
    }

    /**
     * 후위표기식을 계산
     * 피연산자는 stack에 저장
     * 연산자가 나오면 stack에서 피연산자 2개 빼서 연산하고 다시 stack에 저장
     * 마지막 stack에 남은 숫자가 계산결과이므로 return
     * @param str
     * @return
     */
    static public int calc(String str) {
        List<Character> op = new ArrayList<Character>();
        op.add('+');
        op.add('-');
        op.add('*');
        op.add('/');
        char[] chars = str.toCharArray();
        MyStack stack = new MyStack();
        for (char aChar : chars) {
            if (op.contains(aChar)) {
                int b = (char) stack.pop() - '0';
                int a = (char) stack.pop() - '0';

                switch (aChar) {
                    case '+' -> {
                        stack.push((char) ((a + b) + '0'));
                    }
                    case '-' -> {
                        stack.push((char) ((a - b) + '0'));
                    }
                    case '*' -> {
                        stack.push((char) ((a * b) + '0'));
                    }
                    case '/' -> {
                        stack.push((char) ((a / b) + '0'));
                    }
                }
            } else {
                stack.push(aChar);
            }
        }
        return (char)stack.pop() - '0';
    }
}

📢 Servlet Filter 란??

Servlet Filter는 클라이언트의 요청(Request)과 응답(Response)를 가로채서 중간에 특정 작업을 수행할 수 있는 Servlet Component이다.

클라이언트의 요청이 Servlet이나 JSP 에 도달하기 전에, 또는 응답이 클라이언트에 전달되기 전에 동작한다.

🎁 Servlet Filter의 주요 역할

1. 요청(Request) 전처리

사용자 인증 및 권한 체크

요청 파라미터 인코딩 처리

로그 기록 및 모니터링

2. 응답(Response) 후처리

응답데이터압축

보안헤더추가

캐싱정책적용

3. 공통작업처리

 CORS 설정

XSS/SQL Injection 방어

💨 Filter 동작 순서

 클라이언트 요청 -> 필터(Filter) -> 서블릿(Servlet) -> 필터(Filter) -> 클라이언트 응답

요청과 응답 사이에 필터를 거치게 할 수 있음!

🔰 Filter 구성 요소

1. init() 

필터가 초기화될 때 호출 (서버 시작 시 1회)

2. doFilter()

요청/응답을 가로채서 처리 (핵심 메서드)

doFilter() 메서드는 파라미터에 filterchain을 가지고 있는데, filterchain.doFilter(request, response); 메서드를 호출하게 되면,

다음 필터가 있으면 필터를 호출하고, 필터가 없으면 dispatcherServlet을 호출한다.

만약 이 로직을 호출하지 않으면 다음 단계로 진행되지 않기 때문에, 특별한 경우를 제외하고 반드시 호출해야한다.

3. destroy()

필터가 소멸될 때 호출 (서버 종료시)

✨ Filter 구현 예제

import javax.servlet.*;
import javax.servlet.annotation.WebFilter;
import java.io.IOException;

@WebFilter("/*")  // 모든 요청에 적용
@WebFilter(filterName = "LoginFilter", urlPatterns = {"/user/mypage","/shop/register"}) // 이런 양식으로 원하는 요청만 적용시킬수도 있음
public class LogFilter implements Filter {

    @Override
    public void init(FilterConfig filterConfig) {
        System.out.println("LogFilter 초기화됨");
    }

    @Override
    public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain)
            throws IOException, ServletException {

        System.out.println("요청이 들어왔습니다: " + request.getRemoteAddr());

        // 다음 필터나 서블릿으로 요청 전달
        chain.doFilter(request, response);

        System.out.println("응답이 완료되었습니다.");
    }

    @Override
    public void destroy() {
        System.out.println("LogFilter가 종료됨");
    }
}

✅ Filter의 장점

1. 공통 기능 분리 → 중복 코드 최소화
2. 유연한 요청/응답 처리 → 전처리·후처리 가능
3. 보안 강화 → 인증·인가, XSS/SQL Injection 방어

❗ Filter 사용 시 주의사항

1. chain.doFilter() 호출 → 호출하지 않으면 요청이 중단됨
2. 필터 순서 주의 → 의도한 대로 작동하도록 등록 순서 관리
3. 리소스 누수 방지 → destroy()에서 자원 정리

🏷️ 요약

• Servlet Filter는 요청/응답 전후로 공통 처리를 수행
• 인증, 인코딩, 보안, 로깅 등 다양한 전처리·후처리 작업 가능
• 여러 필터가 있을 경우 순서대로 실행 (FilterChain)

1. DBCP?

데이터베이스 연결(Connection)을 효율적으로 관리하기 위해 사용되는 기술.

데이터베이스 연결을 매번 생성하고 종료하는 작업은 비용이 많이 든다!

그래서 미리 일정 수의 연결을 생성해두고 필요할 때 재사용하도록 도와주는 것이 DBCP

2. 필요한 이유

데이터베이스 커넥션을 획득할 때는 다음과 같은 복잡한 과정을 거친다.

1. 애플리케이션 로직은 DB 드라이버를 통해 커넥션을 조회한다.
2. DB 드라이버는 DB와 TCP/IP 커넥션을 연결한다. 물론 이 과정에서 3 way handshake 같은 TCP/IP
연결을 위한 네트워크 동작이 발생한다.
3. DB 드라이버는 TCP/IP 커넥션이 연결되면 ID, PW와 기타 부가정보를 DB에 전달한다.
4. DB는 ID, PW를 통해 내부 인증을 완료하고, 내부에 DB 세션을 생성한다.
5. DB는 커넥션 생성이 완료되었다는 응답을 보낸다.
6. DB 드라이버는 커넥션 객체를 생성해서 클라이언트에 반환한다.

이게 너무 복잡하고 시간도 많이 소요되니까 커넥션 풀을 사용하는 것!

장점

비용절감

커넥션을 매번 열고 닫는 것은 시간과 자원을 많이 소모한다.

커넥션 풀을 사용하면 커넥션을 재사용해 성능을 높일 수 있다.

성능향상

DB 커넥션 생성/종료 과정을 줄여 응답속도가 빨라짐.

트래픽이 급증해도 커넥션 풀로 안정적인 서비스 제공 가능.

안정성

커넥션을 일정 수만 유지해 DB 과부하 방지함

유휴 커넥션은 자동으로 정리하거나 갱신함

DBCP 동작 원리

1. 애플리케이션 시작 시 미리 커넥션 풀을 생성

2. 요청 발생 시 커넥션 풀에서 사용 가능한 커넥션을 할당

3. 작업 완료 후 커넥션을 닫지 않고 반환

4. 커넥션 풀이 부족하면 새 커넥션 생성 또는 대기

5. 일정 시간이 지난 유휴 커넥션은 자동으로 제거

추천되는 것 

HikariCP

경량화와 고성능 커넥션 풀

빠른 응답 속도와 효율적인 자원관리를 해줌 

Spring boot 기본으로 채택됨!

DBCP  주요 설정 항목

1. 기본 커넥션 설정

2. 커넥션 풀 크기 설정

3. 커넥션 테스트 및 검증

4. 성능 최적화 관련 설정

import com.zaxxer.hikari.HikariConfig;
import com.zaxxer.hikari.HikariDataSource;

import java.sql.Connection;

public class HikariCPExample {

    private static HikariDataSource dataSource;

    static {
        HikariConfig config = new HikariConfig();
        config.setJdbcUrl("jdbc:mysql://localhost:3306/mydb");
        config.setUsername("root");
        config.setPassword("password");
        config.setDriverClassName("com.mysql.cj.jdbc.Driver");

        // 커넥션 풀 설정
        config.setMaximumPoolSize(20);      // 최대 커넥션 수
        config.setMinimumIdle(5);           // 최소 유휴 커넥션
        config.setConnectionTimeout(10000); // 커넥션 요청 대기 시간 (10초)
        config.setIdleTimeout(300000);      // 유휴 커넥션 유지 시간 (5분)
        config.setMaxLifetime(1800000);     // 커넥션 최대 수명 (30분)

        // 유효성 검사 쿼리
        config.setConnectionTestQuery("SELECT 1");

        // 누수 감지 (5초 이상 반환 안 되면 경고)
        config.setLeakDetectionThreshold(5000);

        // 커넥션 풀 이름
        config.setPoolName("MyHikariCP");

        // 데이터 소스 초기화
        dataSource = new HikariDataSource(config);
    }

    public static Connection getConnection() throws Exception {
        return dataSource.getConnection();
    }

    public static void close() {
        if (dataSource != null) {
            dataSource.close();
        }
    }
}