명품호세의 개발 공부 및 기록 블로그

문제의 그림만 보고 생각하면 어떻게 풀어야 할지 감이 잘 안온다. 표를 만들어서 한번 보자

표를 자세히 보면 방이 1개일때를 제외하고는 층이 바뀔때 마다 방이 6의 배수로 늘어나는 것을 볼 수 있다.

또한 1층을 제외한 층의 최소 방번호 역시 최소 방번호 + 해당 층의 방 갯수를 더하면 다음 층의 최소 방번호가 나오는 것을 알 수 있다.

이것을 힌트로 코드를 작성해보자

int range = 2;
int count = 1;

while (range <= N) {
    range += 6 * count;
    count ++;
}

System.out.println(count);

1층일 때는 어차피 1이므로 제외하고 range를 2층의 최소 방번호 부터 시작해보자. (여기서 N은 입력 방 번호값이다)

사용자가 N을 입력하면 range를 2층부터 방의 수를 계속 더해주어 N보다 커지면 중지시키는 알고리즘이다.

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

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

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

        if (N == 1) {
            System.out.println(N);
            return;
        } else {
            int range = 2;
            int count = 1;

            while (range <= N) {
                range += 6 * count;
                count ++;
            }

            System.out.println(count);
        }
    }
}

참고 : [백준] 2292번 : 벌집 - JAVA [자바] (tistory.com)

주어진 문자열을 모두 순회하면서 변경할 크로아티아 알파벳이 나올경우 비교하여 순회하면 된다.

예를 들면 c가 나올경우 c다음에 =가 나올지 -가 나올지 비교하며 진행하면 된다.

코드로 알아보자

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();

for (int i = 0; i < length; i++) {
        char ch = s.charAt(i);

        char nextCh;

        if (ch == 'c' && i < length - 1) {
            nextCh = s.charAt(i + 1);

            if (nextCh == '=' || nextCh == '-') {
                    i += 1;
            }
        }
 }

1. 위 코드에서 문장 s의 길이로 전체 순회를 돈다.
2. 문자열의 해당 인덱스에 단어를 가져온다.
3. 크로아티아 알파벳에 해당할 경우 그 다음 단어까지 비교한다.
4. 만약 문장 끝에 c가 있을 경우 nextCh를 가져올때 IndexOutofBounds 에러가 발생하니 문장의 끝이 아닌지 확인한다.
5. 변경된 크로아티아 알파벳에 해당할 경우 2단어를 1단어로 취급해야 하니 인덱스 i를 +1 해준다.

아래는 전체 코드 이다.

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

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

        int count = 0;
        int length = s.length();

        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);

            char nextCh;

            if (ch == 'c' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == '=' || nextCh == '-') {
                    i += 1;
                }
            } else if (ch == 'd' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == 'z' && i < length - 2) {
                    nextCh = s.charAt(i + 2);
                    if (nextCh == '=') {
                        i += 2;
                    }
                } else if (nextCh == '-') {
                    i += 1;
                }
            } else if (ch == 'l' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == 'j') {
                    i += 1;
                }
            } else if (ch == 'n' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == 'j') {
                    i += 1;
                }
            } else if (ch == 's' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == '=') {
                    i += 1;
                }
            } else if (ch == 'z' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == '=') {
                    i += 1;
                }
            }

            count++;
        }

        System.out.println(count);
    }
}

동시성 (Concurrency)

• 소프트웨어 적으로 동시에 실행되는 것처럼 보이게 하는것이다. 
• 싱글 코어에서 멀티 스레드를 동작시키기 위한 방식
  • 멀티 코어에서도 동시성은 사용 가능하다.
• 멀티 태스킹을 위해 여러 개의 스레드가 번갈아가면서 실행되는 방식
• 동시성을 이용한 싱글 코어의 멀티 태스킹은 각 스레드들이 병렬적으로 실행되는 것처럼 보이지만 사실은 번갈아 가면서 조금씩 실행되고 있다.

병렬성 (Parallelism)

• 물리적으로 같은 시간동안 작업이 동시에 실행되고 있는것
• 멀티코어에서 멀티 스레드를 동작시키는 방식
• 병렬성은 데이터 병렬성과 작업 병렬성으로 구분된다.
  • 데이터 병렬성 : 전체 데이터를 나누어 서브데이터를 만든 뒤, 서브 데이터들을 병렬 처리하여 작업을 빠르게 수행하는것
  • 작업 병렬성 : 서로 다른 작업을 병렬처리하는것

출처 : 동시성(Concurrency) vs 병렬성(Parallelism) Atin (tistory.com)

RDB

RDB는 Relation DataBase의 약자이다. RDB를 만든 핵심 개념이 관계형 대수학이다. 자료를 관계형 대수학 개념으로 묶고 이를 바탕으로 테이블을 만든다. 뿐만 아니라 SQL문법역시 관계형 대수학을 기반으로 한다. 그리하여 "관계형"데이터베이스 라는 이름을 얻었다.

데이터는 테이블에 레코드로 저장되는데, 각 테이블마다 명확하게 정의된 구조(스키마)가 있다. 데이터를 저장할때 스키마를 준수하지 않은 레코드는 저장할 수 없다.

NOSQL

Nosql은 RDB의 확장성이슈를 해결하기 위해 나온 데이터베이스 모델이다. 

스키마가 없기때문에 RDB보다 자유롭게 데이터를 관리할 수 있다.

NoSQL 에서는 Document에 데이터가 저장된다. 여기서 Document는 RDB의 레코드이며 테이블은 Collection이라는 형태로 데이터를 관리한다.

위와같은 데이터가 있다면 RDB는 필요한 정보만 따로 빼서 각각의 테이블에 저장해야 하지만 NoSQL의 경우 위 데이터를 통째로 저장할 수 있는 차이점이 있다.

RDB의 경우 성능상 이슈가 있을경우 Scale-Up을 통해 업그레이드를 할수밖에 없지만 NoSql의 경우 데이터 모델 자체가 독립적으로 설계되어있어 데이터를 여러 서버에 분산 시키는 Scale-Out을 통해 개선이 가능하다. 물론 RDB도 샤딩을 통해 충분히 Scale-Out할 수 있지만 어플리케이션 레벨에서 모든 샤딩을 제어해야 한다 (어떤 데이터를 요청하면 어느 클러스터에서 처리해라) 그러나 NoSql은 자체적으로 지원하기 때문에 복잡한 제어가 필요하지 않다.

서블릿이란?

기존에는 HTML을 사용하여 웹페이지를 개발했다. 그러나 HTML만 사용할 경우 사용자 변경이나, 시간에따라 데이터를 바꿀 수 없다. 즉 데이터가 고정되어있어 정적인 웹페이지밖에 만들 수 없다.

사용자가 글을 등록하거나 삭제할 경우 동적으로 데이터를 보여주고 싶다면 동적인 웹페이지를 작성해야 하는데 JAVA 진영에서 동적인 웹페이지를 개발하기위한 기술중 하나가 서블릿이다.

톰캣이란?

서블릿을 실행하는 역할을 한다. 사용자의 요청을받아 사용자 요청에 해당하는 Path를 추출하고 Path에 해당하는 서블릿을 찾아 그 서블릿에 요청을 하고 서블릿이 작업 처리가 끝나고 응답을 하면 클라이언트에게 데이터를 전달하는 역할을 한다. 이런 톰캣서버를 총칭해서 Web Application Server라고 하고 줄여서 WAS라고 한다.

서블릿 컨테이너란?

서블릿 객체를 만들어 보관하고 서블릿을 관리하고 서비스하는 프로그램이다. 대표적인 서블릿 컨테이너로 톰캣이 있다.

람다식은 객체지향 언어보다는 함수지향 언어에 가깝다. 객체지향 언어인 자바가 람다식을 수용한 이유는 코드가 매우 간결해지고 컬렉션의 요소를 필터링하거나 매핑해서 원하는 결과를 쉽게 집계할 수 있기 때문이라고 한다.

람다식은 "(매개변수) -> { 실행코드 }" 형태로 작성되는데, 마치 함수 정의 형태를 띠고 있지만 런타임 시에 인터페이스의 익명 구현 객체로 생성된다. 

람다식의 기본 문법

람다식을 작성하는 방법은 다음과 같다.

(타입, 매개변수) -> { 실행문 } 

예를 들어 int 매개 변수 a의 값을 콘솔에 출력하기 위해 다음과 같이 람다식을 작성할 수 있다.

(int a) -> { System.out.println(a); }

매개 변수의 타입은 대입되는 값에 따라 자동으로 인식될 수 있기 때문에 생략해도 무방하다.

하나의 매개변수만 있다면 괄호를 생략 할 수 있고, 하나의 실행문만 있다면 중괄호도 생략이 가능하다.

a -> System.out.println(a)

만약 매개변수가 없다면 빈 괄호를 사용하여 작성한다.

만약 어떤 작업을 수행후 리턴해야 하는 값이 있으면 return을 적어주고 만약 return만 있다면 return 생략 하여 작성할 수 있다.

(x, y) -> x + y

람다식은 인터페이스 변수에 대입된다. 인터페이스는 직접 객체화 할 수 없기때문에 구현 클래스가 필요한데, 람다식은 익명 구현 클래스를 생성하고 객체화한다. 람다식은 대입될 인터페이스의 종류에 따라 작성 방법이 달라지기 때문에 람다식이 대입될 인터페이스를 람다식의 타켓 타입이라고 한다.

람다식의 실행 블록에는 클래스의 멤버(필드와 메서드) 및 로컬 변수를 사용할 수 있다. 클래스의 멤버는 제약 사항 없이 사용 가능하지만, 로컬 변수는 제약 사항이 따른다. 

자바 8부터는 빈번하게 사용되는 함수적 인터페이스는 표준 API 패키지로 제공한다. 크게 Consumer, Supplier, Function, Operator, Predicate로 구분된다.

메소드 참조 

메소드를 참조해서 매개 변수의 정보 및 리턴 타입을 알아내어, 람다식에 불필요한 매개 변수를 제거하는 것이 목적이다.

예를들어 두개의 값을 받아 큰 수를 리턴하는 Math 클래스의 max() 정적 메소드를 호출하는 람다식은 다음과 같다.

(left, right) -> Math.max(left, right);

이 경우에는 다음과 같이 메소드 참조를 이용하면 매우 깔끔하게 처리할 수 있다.

Math::max

정적(static)메서드를 참조할 경우에는 클래스 이름 뒤에 :: 기호를 붙이고 정적 메소드 이름을 적으면된다.

클래스 :: 메소드

인스턴스 메서드일 경우에는 먼저 객체를 생성한 다음 참조 변수 뒤에 :: 기호를 붙이고 인스턴스 메서드 이름을 적으면된다.

참조변수 :: 메서드

docker-compose.yml 파일을 만들고 아래와 같이 만들어준다.

version: "3" # 파일 규격 버전
services: # 이 항목 밑에 실행하려는 컨테이너 들을 정의
  db: # 서비스 명
    image: mysql:5.7.34 # 사용할 이미지
    container_name: mysql_container # 컨테이너 이름 설정
    ports:
      - "3306:3306" # 접근 포트 설정 (컨테이너 외부:컨테이너 내부)
    environment: # -e 옵션
      MYSQL_ROOT_PASSWORD: "password"  # MYSQL 패스워드 설정 옵션
    command: # 명령어 실행
      - --character-set-server=utf8mb4
      - --collation-server=utf8mb4_unicode_ci
    volumes:
      - /Users/bell/mysql_data:/var/lib/mysql # -v 옵션 (다렉토리 마운트 설정)

작성 후 터미널에서 docker-compose up을 입력하면 mysql 컨테이너가 만들어진다.

웹서버

웹 서버의 개념

• 웹 서버는 소프트웨어와 하드웨어로 구분된다.
• 하드웨어 : Web 서버가 설치되어있는 컴퓨터
• 소프트웨어 : 웹 브라우저 클라이언트로부터 HTTP 요청을 받아 정적인 컨텐츠 (html, css 등)를 제공하는 컴퓨터 프로그램

웹서버의 기능

• HTTP 프로토콜을 기반으로 하여 클라이언트의 요청을 서비스 하는 기능을 담당한다.
• 기능 1
  • 정적인 컨텐츠 제공
  • WAS를 거치지 않고 바로 자원을 제공한다.
• 기능 2
  • 동적인 컨텐츠 제공을 위한 요청 전달
  • 클라이언트의 요청(Request)을 WAS에 보내고, WAS가 처리한 결과를 클라이언트에게 전달(응답, Response)한다.
  • 클라이언트는 일반적으로 웹 브라우저를 의미한다.
• 웹 서버의 예 : Nginx, Apache Server 등

WAS ( Web Application Server)

WAS의 개념

• DB 조회나 다양한 로직 처리를 요구하는 동적인 컨텐츠를 제공하기 위해 만들어진 Application Server
• HTTP를 통해 컴퓨터나 장치에 애플리케이션을 수행해주는 미들웨어(소프트웨어 엔진)이다.
• '웹 컨테이너' 혹은 '서블릿 컨테이너' 라고도 불린다.
  • 컨테이너란 JSP, Servlet을 실행시킬 수 있는 소프트웨어를 말한다. WAS는 JSP, Servlet 구동 환경을 제공한다.

WAS의 역할

• WAS = Web Server + Web Container
• 웹서버의 기능들을 구조적으로 분리하여 처리하고자하는 목적으로 제시되었다.
  • 분산 트랜잭션, 보안, 메시징, 쓰레드 처리 등의 기능을 처리하는 분산 환경에서 사용된다.
  • 주로 DB 서버와 같이 수행된다.
• 현재는 WAS가 가지고 있는 웹 서버도 정적인 컨텐츠를 처리 하는데 있어서 성능상 큰 차이가 없다.

WAS의 주요 기능

• 프로그램 실행 환경과 DB 접속 기능 제공
• 여러 개의 트랜잭션(논리적인 작업 단위) 관리 기능
• 업무를 처리한느 비즈니스 로직 수행

WAS의 예 : Tomcat 등

웹 서버와 WAS를 구분하는 이유

웹페이지는 정적 컨텐츠와 동적컨텐츠가 모두 존재한다. 이를 WAS에서 모두 처리하기에는 정적데이터 처리로 인해 부하가 커지게되어 동적 컨텐츠의 처리가 지연되어 수행속도가 저하된다. 웹서버를 사용하여 정적인 컨텐츠만 처리하도록 기능을 분배하여 서버의 부담을 줄일 수 있다.

Index의 목적 : SELECT 쿼리의 WHERE절이나 JOIN 예약어를 사용했을때만 인덱스를 사용되며 SELECT 쿼리의 검색 속도를 빠르게 하는데 목적을 두고 있다.

테이블의 칼럼을 색인화하여 데이터베이스 안의 레코드를 처음부터 풀스캔하지 않고, B+ Tree로 구성된 구조에서 Index 파일 검색으로 속도를 향상시키는 기술이다.

테이블 생성시, 3가지 파일이 생성된다.

• FRM : 테이블 구조 저장 파일
• MYD : 실제 데이터 파일
• MYI : Index 정보 파일 (Index 사용 시 생성)
  • 해당 컬럼을 인덱스로 설정해 놓으면 SELECT를 할때 MYI파일의 내용을 검색한다.

인덱스의 장점

• 키 값을 기초로 하여 테이블에서 검색과 정렬 속도를 향상시킨다.
• 질의나 보고서에서 그룹화 작업의 속도를 향상시킨다.

Transaction : 데이터베이스의 데이터를 조작하는 작업의 단위이다.

transaction은 ACID원칙을 보장해야 한다. 

• Atomicity (원자성) : 트랜잭션의 작업이 부분적으로 실행되거나 중단되지 않는 것을 보장한다. All or Nothing의 개념
• Consistency (일관성) : 트랜잭션이 성공적으로 완료되면 일관적인 DB상태를 유지해야 한다.
• Isolation (독립성) : 트랜잭션 수행시 다른 트랜잭션의 작업이 끼어들지 못하도록 보장하는것을 말한다.
• Durability (영구성) : 성공적으로 수행된 트랜잭션은 영원히 반영되는것을 말한다.

Commit : 하나의 트랜잭션이 성공적으로 끝났고, DB가 일관성있는 상태일 때 이를 알려주기 위해 사용하는 연산

Rollback : 하나의 트랜잭션 처리가 비정상적으로 종료되어 트랜잭션 원자성이 깨진 경우, 트랜잭션의 시작상태로 롤 백 할 수 있음.

하지만 ACID 원칙은 종종 지켜지지 않는다. 원칙을 완벽하게 지키려 하면 동시성이 매우 떨어지기 때문이다. 

그렇기 때문에 DB 엔진은 ACID 원칙을 희생하여 동시성을 얻을 수 있는 방법을 제공한다. 바로 transaction의 Isolation level이다. Isolation 원칙을 덜 지키는 level을 사용할수록 문제가 발생할 가능성은 커지지만 동시성은 얻을 수 있다. 

동시성을 제공함으로써 생기는 격리성 문제

1. Dirty Read

- 데이터 캐시에는 변경이 되었지만, 디스크에는 변경되지 않은 데이터를 Dirty Page라하고, 이를 읽는 작업을 Dirty Read

2. Non-Repeatable Read

- 트랜잭션 내 다른 시점에 읽은 하나의 데이터가 값이 다른 것

3. Phantom Read

- 트랜잭션 수행 중 없던 행이 추가되어 새로운 데이터를 읽게 되거나 존재하던 데이터가 사라지는 것, 트랜잭션 내 동일한 조건으로 읽은 데이터의 개수가 달라지는 것

트랜잭션 격리 Level

1. Read Uncommitted

• 트랜잭션이 완료(Commit)되지 않은 데이터를 다른 트랜잭션이 읽는 것을 허용
• 해당 데이터를 SELECT할 경우 Shared-Lock이 걸리지 않는다.
• 발생할 수 있는 격리성 문제 : Dirty Read, Non-repeatable Read, Phantom Read

2. Read Committed

• 트랜잭션이 완료된 데이터만 읽는 것을 허용
• 해당 데이터를 SELECT할 경우 Shared-Lock 이 적용된다.
• SELECT가 끝날때까지만 Shared-Lock이 적용된다. 
• 발생할 수 있는 격리성 문제 : Non-repeatable Read, Phantom Read

3. Repeatable Read

• 트랜잭션이 완료되기 전까지 Shared-Lock을 적용하여 다른 트랜잭션에서 해당 데이터를 읽을 수 없다.
• 따라서 트랜잭션이 완료 되기 전까지 일관된 데이터가 보장된다. (Non-Repeatable Read 예방)
• Shared-Lock이 해제 되기 전에도 다른 트랜잭션에서 새로운 데이터를 삽입하는 것은 가능하기때문에 Phantom Read는 발생할 수 있다.
• 발생할 수 있는 격리성 문제 : Phantom Read

4. Serializable

• Shared-Lock이 범위(Range) 단위로 적용되고, 트랜잭션이 완료된 이후에 해제가 된다.
• 범위 단위의 Lock 덕분에 Phantom Read까지 예방할 수 있다.
• 발생할 수 있는 격리성 문제 : 없음

출처: https://s1107.tistory.com/45 [개발자]

트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

용어 :

• Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node : 트리 맨 위에 있는 노드
• Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
• Child Node : 어떤 노드의 상위 레벨에 연결된 노드
• Leaf Node : Child Node가 하나도 없는 노드 
• Sibling : 동일한 Parent Node를 가진 노드
• Depth : 트리에서 Node가 가질 수 있는 최대 Level

이진 트리와 이진 탐색 트리

• 이진 트리 : 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음.

이진 탐색 트리 삭제

• 매우 복잡하다. 경우를 나누어서 이해하는 것이 좋다.

1. Leaf Node 삭제
   • Leaf Node : Child Node가 없는 Node
   • 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.
2. Child Node가 하나인 Node 삭제
   • 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.
3. 삭제할 Node의 자식이 2개인 경우 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다 (아래 방법중 하나를 선택해서 적용한다.)
   • 삭제할 Node의 오른쪽 자식 중, 가장 작은 삭제할 Node의 Parent Node가 가리키도록 한다.
   • 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

Ex)

1. 삭제할 Node의 오른쪽 자식 선택
2. 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
3. 해당 Node를 삭제할 Node의 Parent Node의 완쪽 Branch가 가리키게 한다.
4.  해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 한다.
5. 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 한다.
6. 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 한다.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class NodeManagement:
    def __init__(self, root):
        self.root = root

    def get_value(self):
        return self.root.value

    def insert(self, value):
        self.current_node = self.root
        while True:
            if value < self.current_node.value:
                if self.current_node.left is not None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right is not None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break

    def search(self, value):
        self.current_node = self.root

        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right

        return False

    def delete(self, value):
        # 삭제할 노드 탐색
        searched = False
        self.current_node = self.root
        self.parent = self.root
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right

        # 삭제할 노드가 없음
        if searched is False:
            return False

        # 삭제할 노드를 찾음
        # 1. 삭제할 노드가 리프노드 경우
        if self.current_node.left is None and self.current_node.right is None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None

        # 2. 삭제할 노드가 Child Node를 가지고 있을 경우
        # 2-1 Child Node가 삭제할 노드의 왼쪽에 있을 경우
        elif self.current_node.left is not None and self.current_node.right is None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left

        # 2-2 Child Node가 삭제할 노드의 오른쪽에 있을 경우
        elif self.current_node.left is None and self.current_node.right is not None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right

        # 3. 삭제할 노드가 Child Node를 양쪽 모두 가지고 있을 경우
        elif self.current_node.left is not None and self.current_node.right is not None:
            # 3-1 삭제할 Node가 Parent Node 왼쪽에 있는 경우
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                self.change_node_parent.left = None
                if self.change_node.right:
                    self.change_node_parent.right = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.change_node.left

            # 3-2 삭제할 Node가 Parent Node 오른쪽에 있는 경우
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left

        return True



if __name__ == "__main__":
    bst_nums = set()

    while len(bst_nums) != 100:
        bst_nums.add(random.randint(0, 999))

    print(bst_nums)

    head = node_management.Node(500)
    binary_tree = node_management.NodeManagement(head)

    for number in bst_nums:
        binary_tree.insert(number)

    # 검색 기능 확인
    for number in bst_nums:
        if binary_tree.search(number) is False:
            print("search failed : ", number)

    delete_nums = set()
    bst_nums = list(bst_nums)
    while len(delete_nums) != 10:
        delete_nums.add(bst_nums[random.randint(0, 99)])

    # 삭제 기능 확인
    for del_num in delete_nums:
        if binary_tree.delete(del_num) is False:
            print('delete failed', del_num)

이진 탐색 트리의 시간 복잡도와 단점

시간 복잡도 (탐색)

• depth ( 트리의 높이) 를 h라고 표기한다면 O(h)
• 검색을 하기위해 비교 할때마다 절반씩 사라지므로 O(log n)으로 표시할 수 있다.

단점

• 균형이 잡혀이는 트리의 경우 평균 시간 복잡도는 O(log n)이지만 트리가 한쪽으로 편향되어 있으면 O(n)으로 나빠질 수 있다.

Hash Table : 키(key)에 데이터(value)를 저장하는 구조

• Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.
• 파이썬 딕셔너리 타입이 해쉬 테이블의 예시이다.
• 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용한다 (공간과 탐색 시간을 맞바꾸는 기법이다.

기본 예시

# 간단한 해쉬 함수를 만들기 (나무기를 통해 나머지 값을 사용하기)
def custom_hash_func(key):
    return key % 5


def storage_data(data, value):
    key = ord(data[0])
    hash_address = custom_hash_func(key)
    hash_table[hash_address] = value


def get_value(data):
    key = ord(data[0])
    hash_address = custom_hash_func(key)
    return hash_table[hash_address]


if __name__ == '__main__':
    hash_table = list([0 for i in range(10)])

    storage_data('Andy', '01012341234')
    storage_data('Dave', '01033332222')
    storage_data('Trump', '01055556666')

    print(hash_table)
    print(get_value('Andy'))

해시 테이블의 가장 큰 문제는 해시 충돌이다. 이것을 해결하는 방법은 아래와 같다.

• Chaining 기법
  • 개방 해싱 또는 Open Hashing 기법 중 하나이다. 
  • 충돌이 일어나면, 링크드 리스트를 사용하여 데이터를 추가로 뒤에 연결시켜 저장한다.

  • def get_key(data):
        return hash(data)
    
    
    def hash_function(key):
        return key % 8
    
    
    def save_data(data, value):
        index_key = get_key(data)
    
        hash_address = hash_function(index_key)
    
        if hash_table[hash_address] != 0:
            for index in range(len(hash_table[hash_address])):
                if hash_table[hash_address][index][0] == index_key:
                    hash_table[hash_address][index][1] = value
                    return
                hash_table[hash_address].append([index_key, value])
        else:
            hash_table[hash_address] = list([index_key, value])
        hash_table[hash_address] = value
    
    
    def read_data(data):
        index_key = get_key(data)
        hash_address = hash_function(index_key)
    
        if hash_table[hash_address] != 0:
            for index in range(len(hash_table[hash_address])):
                if hash_table[hash_address][index][0] == index_key:
                    return hash_table[hash_address][index][1]
            return None
        else:
            return None
    
    
    if __name__ == "__main__":
        ## 해시 충돌 해결 해보기
        hash_table = list([0 for i in range(8)])
    

• Linear Probing 기법
  • 폐쇄 해슁 또는 Close Hashing 기법중 하나이다.
  • 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법

  • def get_key(data):
        return hash(data)
    
    
    def hash_function(key):
        return key % 8
    
    
    def save_data(data, value):
        index_key = get_key(data)
        hash_address = hash_function(index_key)
        if hash_table[hash_address] != 0:
            for index in range(hash_address, len(hash_table)):
                if hash_table[index] == 0:
                    hash_table[index] = [index_key, value]
                    return
                elif hash_table[index][0] == index_key:
                    hash_table[index][1] = value
                    return
        else:
            hash_table[hash_address] = [index_key, value]
    
    
    def read_data(data):
        index_key = get_key(data)
        hash_address = hash_function(index_key)
    
        if hash_table[hash_address] != 0:
            for index in range(hash_address, len(hash_table)):
                if hash_table[index] == 0:
                    return None
    
                elif hash_table[index][0] == index_key:
                    return hash_table[index][1]
        else:
            return None
    
    
    if __name__ == "__main__":
        ## 해시 충돌 해결 해보기
        hash_table = list([0 for i in range(8)])
    

@Bean : 개발자가 컨트롤이 불가능한 외부 라이브러리들을 Bean으로 등록하고 싶을때 사용한다.

Ex) QueryDSL을 사용할때 JPAQueryFactory를 사용해야 하는데 QueryDSL을 사용하는 곳마다 주입받는 코드를 작성하기 귀찮다. 그럴때 사용할 수 있다.

@Component : 개발자가 직접 만들어 사용하는 Class들의 경우 @Component를 사용한다. 

Ex) API Request를 받기위해 컨트롤러를 만들었을때 그 컨트롤러를 Component로 등록해 사용한다.

재귀 용법을 활용한 정렬 알고리즘이다.

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

알고리즘의 이해

데이터가 4개일때

예 ) data = [1, 9, 3, 2]

1. 먼저 [1, 9], [3, 2] 로 나눈다.
2. 다시 [1,9]를 [1], [9]로 나눈다.
3. 나눈 [1], [9]를 정렬하여 [1, 9]로 합친다.
4. 다음 [3, 2]를 [3], [2]로 나눈다.
5. 나눈 [3], [2]를 정렬하여 [2, 3]으로 합친다.
6. [1,9]와 [2,3]을 정렬하여 합친다.
   1. 1 < 2 이니 [1]
   2. 9 > 2 이니 [1, 2]
   3. 9 > 3 이니 [1, 2, 3]
   4. 9밖에 없으니 [1, 2, 3, 9]

완성 코드

import random


def split(list_data):
    if len(list_data) < 1:
        return list_data

    mid_index = len(list_data) // 2

    left_list = split(list_data[:mid_index])
    right_list = split(list_data[mid_index:])

    return merge(left_list, right_list)


def merge(left_list, right_list):
    left_start_index, right_start_index = 0, 0
    temp_list = list()

    while len(left_list) > left_start_index and len(right_list) > right_start_index:

        if left_list[left_start_index] < right_list[right_start_index]:
            temp_list.append(left_list[left_start_index])
            left_start_index += 1

        else:
            temp_list.append(right_list[right_start_index])
            right_start_index += 1

    while len(left_list) > left_start_index:
        temp_list.append(left_list[left_start_index])
        left_start_index += 1

    while len(right_list) > right_start_index:
        temp_list.append(right_list[right_start_index])
        right_start_index += 1

    return temp_list


def merge_sort(list_data):
    return split(list_data)


if __name__ == '__main__':
    data = random.sample(range(1000), 15)

    print(data)

    print(merge_sort(data))

실제 각 프로세스마다 충분한 메모리를 할당하기에는 메모리 크기에 한계가 있다.

• 일반 적으로 현재 개인 데스크탑의 메모리는 8GB ~ 32GB 정도이다.
• 현재 컴퓨터의 폰노이만 구조 기반이므로, 코드는 메모리에 반드시 올라와 있어야 한다.

가상 메모리는 메모리가 실제 메모리보다 많아 보이게 하는 기술

• 가상 메모리 기본 아이디어
  • 프로세스는 가상 주소를 사용하고, 실제 해당 주소에서 데이터를 읽고/쓸때만 물리 주소로 바꿔주면 된다.
  • virtual address (가상 주소) : 프로세스가 참조하는 주소
  • physical address (물리 주소) : 실제 메모리 주소
• MMU (Memory Management Unit)
  • CPU에 코드 실행시, 가상 주소 메모리 접근이 필요할 때, 해당 주소를 물리 주소값으로 변환해주는 하드웨어 장치

가상 메모리와 MMU

CPU는 가상 메모리를 다루고, 실제 해당 주소 접근시 MMU 하드웨어 장치를 통해 물리 메모리에 접근

• 하드웨어 장치를 이용해서 주소 변환이 빠르기 때문에 별도의 장치를 둔다.

페이징 시스템(paging system)

페이징 개념

• 크기가 동일한 페이지로 가상 주소 공간과 이에 매칭하는 물리 주소 공간을 관리
• 하드웨어 지원이 필요하다
• 페이지 번호를 기반으로 가상 주소/물리 주소 매핑정보를 기록/사용

페이징 시스템 구조

• page 또는 page frame : 고정된 크기의 block
• paging system
  • 가상 주소 v = (p, d)
    • p : 가상 메모리 페이지
    • d : p 안에서 참조하는 위치

• 페이지 크기가 4KB 예시
  • 가상 주소의 0비트에서 11비트가 변위(d)를 나타낸다.
  • 12비트 이상이 페이지 번호가 될 수 있음

페이징 시스템과 MMU

• CPU는 가상 주소 접근시 MMU 하드웨어 장치를 통해 물리 메모리에 접근한다.
• 프로세스 생성시 페이지 테이블 정보를 생성한다
  • PCB등에서 해당 페이지 테이블 접근이 가능하고, 관련 정보는 물리 메모리에 적재한다.
  • 프로세스 구동시, 해당 페이지 테이블 base주소가 별도 레지스터에 저장된다.
  • CPU가 가장 주소 접근시 MMU가 페이지 테이블의 base 주소에 접근하여 물리 주소를 가져온다.
  • 이전에 요청한 가상주소를 TLB에 저장시켜 실제 물리 메모리에서 가져오기 않는다. (캐시 기능)

요구 페이징

프로세스 모든 데이터를 메모리로 적재하지 않고, 실행중 필요한 시점에서만 메모리로 적재함

• 선행 페이징의 반대 개념이다. 선행 페이징은 미리 프로세스 관련 모든 데이터를 메모리에 올려놓고 실행하는 개념
• 더 이상 필요하지 않은 페이지 프레임은 다시 저장매체에 저장(페이지 교체 알고리즘 필요)

페이지 폴트(page fault)

• 어떤 페이지가 실제 물리 메모리에 없을 때 일어나는 인터럽트
• 운영체제가 page fault가 일어나면, 해당 페이지를 물리 메모리에 올림

페이지 폴트가 자주 일어나면?

• 실행되기 전에, 해당 페이지를 물리 메모리에 올려야 한다 → 시간이 오래걸림

페이지 폴트가 안 일어나게 하려면?

• 향후 실행/ 참조될 코드/ 데이터를 미리 물리 메모리에 올린다 → 예측을 하는 일이므로 전혀 알 수 없다.

프로세스와 스레드

프로세스 : 운영체제로부터 자원을 할당받은 작업의 단위.

스레드 : 프로세스가 할당받은 자원을 이용하는 실행 흐름의 단위.

프로그램 → 프로세스 → 스레드

프로그램 -> 프로세스

프로그램 : 파일이 저장 장치에 저장되어 있지만 메모리에는 올라가 있지 않은 정적인 상태. 즉 실행하지 전의 상태이다.

프로세스 : 프로그램을 실행하여 컴퓨터 메모리가 올라가있는 프로그램.

프로그램은 코드 덩어리 파일, 프로그램을 실행하면 프로세스가 된다.

프로세스 간에는 각 프로세스의 데이터 접근이 불가

프로세스 -> 스레드

스레드 : 프로세스의 실행 단위이다. 한 프로세스 내에서 동작되는 여러 실행 프로그램으로 프로세스 내의 주소 공간이나 자원을 공유 할 수 있다. 프로세스 내의 다수의 스레드가 존재할 수 있다.

프로세스 내의 스레드가 하나라도 오류가 생겨 종료될경우 프로세스가 종료된다.

프로세스 안에 있으므로, 프로세스의 데이터를 모두 접근 가능하며 스레드들 끼리는 Heap, Data, Code 영역을 모두 공유한다.

퀵 정렬이란?

• 기준점 (pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽 으로 모으는 함수를 작성함
• 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다.
• 함수는 왼쪽 + 기준점 + 오른쪽을 리턴한다.

import random


def quick_sort(list_data):
    if len(list_data) <= 1:
        return list_data

    pivot = list_data[len(list_data) // 2]

    left = [item for item in list_data if pivot > item]

    right = [item for item in list_data if pivot < item]

    return quick_sort(left) + [pivot] + quick_sort(right)


if __name__ == '__main__':
    data = random.sample(range(1000), 30)

    print("정렬 전 : ", data)
    print()
    print("정렬 후 : ", quick_sort(data))