우리의 서비스는 '1인 가구 맞춤 집안일 관리 서비스' 이다. 1인 가구만 해당하지는 않겠지만, 사용자들에게 계절, 트랜드 등에 맞춰 집안일을 추천해주거나, 개인이 추가하는 집안일을 설정된 주기에 맞춰 알림을 보내주면서 관리할 수 있다.

BE 개발자는 오늘 추가된 2인까지 총 4명이라 기존 MVP 외에도 더 많은 기능을 구현 해볼수 있을 것 같아 설렌다.

구현해야하는 기능을 2명이서만 나눴기 때문에 조정이 필요해보이지만, 우선 집안일에 관련된 기능을 먼저 구현해보려 한다. 집안일과 관련된 기능은 아래와 같다.

1. 집안일 추가하기
2. 집안일 수정하기
3. 집안인 삭제하기
4. 집안일 완료/완료 해제
5. 날짜별 해야할 집안일 조회하기

우선 이렇게 5가지의 기능을 구현 중이다.

기능 구현에 앞서 집안일의 Entity, DTO 를 먼저 작성해줬다.

집안일 추가하기

@Transactional
    public ChoresDto.Response createChores(Long userId,
        ChoresDto.CreateRequest request) {

        try {
            Chores chores = Chores.builder()
                    .userId(userId)
                    .title(request.getTitle())
                    .notificationYn(request.getNotificationYn())
                    .notificationTime(
                        LocalTime.parse(request.getNotificationTime()))
                    .space(request.getSpace())
                    .repeatType(request.getRepeatType())
                    .repeatInterval(request.getRepeatInterval())
                    .startDate(request.getStartDate())
                    .endDate(request.getEndDate())
                    .isDeleted(false)
                    .build();

            Chores savedChores = choresRepository.save(chores);
            List<ChoreInstances> instances = choreInstanceGenerator.generateInstances(savedChores);
            choreInstancesRepository.saveAll(instances);

          return ChoresDto.Response.fromEntity(savedChores);

        } catch (Exception e) {
            e.printStackTrace();
            throw e;
        }
    }

인스턴스 생성 중 에러가 발생할수도 있으니 @Transactional 어노테이션을 사용했다. 토큰 값에서 user 의 id 를 추출하고 클라이언트로부터 입력받은 값을 저장한다.

@Component
public class ChoreInstanceGenerator {

    private static final int MAX_INSTANCES = 1000; // 최대 인스턴스 수 제한

    public List<ChoreInstances> generateInstances(Chores chores) {
        try {

            validateChoreData(chores);
            List<ChoreInstances> instances = new ArrayList<>();

            if (chores.getRepeatType() == Chores.RepeatType.NONE) {
                instances.add(createInstance(chores, chores.getStartDate()));
            } else {
                LocalDate currentDate = chores.getStartDate();
                LocalDate endDate = chores.getEndDate() != null ? chores.getEndDate() : chores.getStartDate().plusYears(1);

                int instanceCount = 0;
                while (!currentDate.isAfter(endDate) && instanceCount < MAX_INSTANCES) {
                    instances.add(createInstance(chores, currentDate));
                    currentDate = getNextDate(currentDate, chores.getRepeatType(), chores.getRepeatInterval());
                    instanceCount++;
                }

                if (instanceCount >= MAX_INSTANCES) {
                    throw new ChoreException(ErrorCode.TOO_MANY_INSTANCES);
                }
            }

            return instances;

        } catch (DateTimeParseException e) {
            throw new ChoreException(ErrorCode.INVALID_DATE_FORMAT, "날짜 형식이 올바르지 않습니다: " + e.getMessage());
        } catch (Exception e) {
            if (e instanceof ChoreException) {
                throw e;
            }
            throw new ChoreException(ErrorCode.INTERNAL_SERVER_ERROR, "인스턴스 생성 중 오류가 발생했습니다: " + e.getMessage());
        }
    }

지금은 우선 동시에 생성할 수 있는 인스턴스 수는 1000개로 제한해두었다. 아마 300개 정도로 줄이지 않을까 싶다. 집안일을 생성하고 해당 인스턴스를 추가하는 로직이다. 별건 없고 대부분 validation 코드다.

임시로 Jwt 관련 코드들을 작성해두었지만, 이 코드를 사용할건 아니고, User 개발하시는 분이 끝나면 그 코드에 맞춰서 수정이 필요해보인다.

Postman 으로 임시 토큰을 생성하고, /chores/create 를 호출하니 잘 호출되고 예외 사항을 발생시켜도 예상대로 잘 나온다.

4-1. 데이터베이스 생성

데이터베이스란?

• 데이터를 보관하기 위한 '상자' 라고 할 수 있다.
• 데이터베이스에서 데이터를 모을 때는 특정한 규칙을 적용해서 데이터를 정리해서 보관한다.

관계형 데이터베이스란?

• 데이터를 표 형식으로 표현하고, 여러 표에서 항목의 값 사이에 관계를 맺고 있는 데이터베이스
• 가장 일반적으로 사용되는 데이터베이스이고, 보통 RDB로 줄여서 부른다.

4-2. 테이블 생성

테이블이란?

• 데이터베이스 안에서 실제로 규칙을 가진 데이터가 저장되는 상자.
• 테이블은 데이터를 항목으로 해서 이차원 표 형식으로 정리해서 저장한다.

레코드와 컬럼

• 테이블의 가로 행을 레코드(record), 세로 열을 컬럼(column) 이라고 한다.
• 하나의 컬럼은 데이터의 각 요소가 된다.

테이블 생성

CREATE TABLE [테이블명] ([컬럼명] [자료형타입] [제약조건] ... );

• 제약 조건의 예
  • NOT NULL : NULL 입력을 허용하지 않는다.
  • UNIQUE : 중복값 입력을 허용하지 않는다.
  • CHECK : 지정한 조건을 만족하지 않는 값의 입력을 허용하지 않는다.
  • PRIMARY KEY : 테이블 안에서 레코드를 식별하는 기본 키를 설정한다. 기본 키는 NOT NULL 과 UNIQUE 가 함께 적용한다.
  • FOREIGN KEY : 관련된 테이블을 연결하는 설정. 외부 키라고도 부른다.
  • DEFAULT : 컬럼의 초깃값을 설정한다.

4-3. 데이터 입력

SQL 이란?

• 데이터베이스를 조작하기 위한 언어
• 정식 명칭은 Structured Query Language (구조화 질의어)

CRUD

• 영속성으로 데이터를 취급하는 4개의 기본적인 기능인 Create, Read, Update, Delete

• UPDATE와 DELETE의 WHERE 절은 없는 경우 모든 레코드가 대상이 된다.

4-4. 엔티티와 레포지토리 알아보기

엔티티란?

• 데이터를 담아두는 객체
• 데이터베이스 테이블의 레코드에 대응하는 객체, 엔티티의 필드는 테이블의 컬럼값에 대응한다.

/**
* Member 테이블 : 엔티티
*/
public class Member {
    /** id 컬럼 대응 **/
    private Integer id;
    /** name 컬럼 대응 **/
    private String name;

    public Integer getId() {
        return id;
    }
    public void setId(Integer id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
}

레포지토리란?

• 데이터베이스를 조작하는 클래스
• 레포지토리를 생성하는 경우에는 반드시 인터페이스를 정의하고 구현해야 한다. 이유는 레포지토리 인터페이스의 필드에 레포지토리 구현 클래스를 DI 하여 특정 구현에 의존하는 것을 피할 수 있기 때문
• 자바에서는 인터페이스를 구현한 클래스의 접미사에 'Impl'을 붙이는 경우가 많다.

1-1. 의존성 주입

• 의존성 주입 (Dependency Injection) 은 '의존하는 부분을 외부에서 주입하는 것' 을 말한다.

1-2. 관점 지향 프로그래밍

• 관점 지향 프로그래밍 (Aspect Oriented Programming) 으로 AOP 에서는 프로그램이 아래 두 가지 요소로 구성된다.

  • 중심적 관심사 (Primary Concern) : 실현해야 할 기능을 나타내는 프로그램
  • 횡단적 관심사 (Crosscutting-Concerns) : 본질적인 기능은 아니지만 품질이나 유지보수 등의 관점에서 반드시 필요한 기능을 나타내는 프로그램

• 간단히 설명하면 공통 처리 등의 '횡당적 관심사' 를 추출하고 프로그램의 여러 곳에서 호출할 수 있게 설정함으로써 개발자는 실현해야 할 기능인 '중심적 관심사' 에만 집중해서 작성하면 되는 구조

1-3. DI 컨테이너

• 의존성 주입 (Dependency Injection) 의 실현을 돕는 프레임워크
• 의존성 주입 : 의존하는 부분을 외부에서 주입하는 것
• 클래스 의존 : 클래스끼리 강하게 결합되어 있어 유연성이 떨어진다. 즉, 메서드 수정 시 수정해야하는 부분이 많아진다.
• 인터페이스 의존 : 인터페이스는 참조를 받는 유형으로 사용할 수 있어 변수의 이름을 수정하지 않아도 되고, 인터페이스가 선언된 메서드를 이용하면 클래스가 수정되어도 메서드명을 수정하지 않아도 된다.
• 이러한 이점 때문에 인터페이스 의존을 사용하여 수정할 곳을 줄인다.

1-3-1. DI 컨테이너의 다섯 가지 규칙

1. 인터페이스를 이용하여 의존성을 만든다.

• 의존하는 부분에 인터페이스를 이용한다.

2. 인스턴스를 명시적으로 생성하지 않는다.

• 인스턴스 생성에 new 키워드를 사용하지 않는다.

3. 어노테이션을 클래스에 부여한다.
4. 스프링 프레임워크에서 인스턴스를 생성한다.

• 인스턴스를 생성하려는 클래스에 인스턴스 생성 어노테이션 (@Component) 을 부여한다.

5. 인스턴스를 이용하고 싶은 곳에 어노테이션을 부여한다.

• 생성된 인스턴스를 이용하는 클래스에 참조를 받는 필드를 선언하고 @Autowired 어노테이션을 부여한다.

의존성 주입에 관한 내용을 요약하면 아래와 같다.

 - 스프링 프레임워크는 임의로 구현한 클래스를 인스턴스화하는 기능을 제공한다. -> DI 컨테이너
 - 스프링 프레임워크를 사용하는 어플리케이션은 인스턴스를 명시적으로 생성하지 않는다. (new 사용 X)
 - 정해진 어노테이션 (@Component) 을 클래스에 부여하는 것으로 스프링 프레임워크가 인스턴스를 생성한다.
 - 생성된 인스턴스를 사용하고 싶은 부분에서 필드를 준비하고 @Autowired 어노테이션을 부여하면 
  스프링 프레임워크가 인스턴스가 필요한 것으로 판단하고 인스턴스를 주입한다.
 - 인터페이스를 이용해서 의존성을 만들고 DI 를 사용하여 '사용되는 객체' 클래스를 변경하는 경우
 '사용하는 객체' 클래스의 수정 없이 변경할 수 있다.

2-1. 어노테이션

• Annotation 은 주석을 의미하는 영어 표현이며, 외부 소프트웨어에 필요한 처리 내용을 전달한다.

레이어별로 사용할 인스턴스 생성 어노테이션

• 어플리케이션을 만들 때는 레이어로 나누는 것이 좋다.
• 아래는 '도메인 주도 설계 (Domain-Driven Design)' 의 레이어이다.

• 인스턴스 생성 어노테이션은 레이어별로 구분된다.
  • @Controller : 어플리케이션 레이어의 컨트롤러에 부여
  • @Service : 도메인 레이어의 업무 처리에 부여
  • @Repository : 인프라 레이어의 데이터베이스 액세스 처리에 부여
  • @Component : 위 세 어노테이션의 용도 이외의 인스턴스 생성 대상 클래스에 부여, 하위 로직을 처리할 때 사용

2-2. AOP (Aspect Oriented Programming) : 관점 지향 프로그래밍

• 스프링 프레임워크에서 제공하는 AOP 기능을 활용하여 '중심적 관심사' 와 '횡단적 관심사' 를 분리하여 프로그램을 쉽게 만들 수 있다.

AOP 고유 용어

• Advice : 횡단적 관심사의 구현 (메서드). 로그 출력 및 트랜잭션 제어 등
• Aspect : Advice를 정리한 것 (클래스).
• JoinPoint : Advice를 중심적인 관심사에 적용하는 타이밍. 메서드 (생성자) 실행 전, 후 등 실행되는 타이밍
• Pointcut : Advice를 삽입할 수 있는 위치. ex. 메서드 이름이 get 으로 시작할 때만 처리
• Interceptor : 처리의 제어를 인터셉트하기 위한 구조 또는 프로그램. 이 메커니즘으로 Advice를 중심 관심사에 추가한 것처럼 보이게 한다.
• Target : Advice가 도입되는 대상

AOP 의 구조

A 클래스가 B 클래스의 X 메서드를 호출하는 경우 인터셉터의 동작 방식

• AOP를 사용하면 A 클래스에서 B 클래스의 X 메서드 (중심적 관심사) 를 호출하는 것처럼 보인다.
• 하지만 내부적으로는 AOP 프락시 (스프링 프레임워크가 자동 생성) 가 처리를 가로채고 X 메서드 및 Advice의 호출을 제어한다.

• Advice 의 다섯 가지 종류

AOP의 주요 사항

 - AOP에서는 프로그램을 2개의 요소인 중심적 관심사와 횡단적 관심사로 구성되어 있다고 생각한다.
 - 중심적 관심사 : 구현해야 할 기능을 나타내는 비즈니스 로직
 - 횡단적 관심사 : 본질적인 기능은 아니지만, 품질이나 유지보수 등의 관점에서 꼭 필요한 기능
 - AOP에서는 횡단적 관심사를 분리함으로써 기존 코드를 수정하지 않아도 프로그램 중에 특정 기능 (공통 처리) 을 추가할 수 있다.
 - 스프링 프레임워크는 다양한 공통 기능을 AOP에서 제공한다.

02장. 기초 지식 배우기

교재의 간단한 실습을 진행하기 위한 자바 기초 지식을 복습해보고, 웹 서비스에 대한 필수 지식들을 정리 해보려한다.

2-1. 자바 기초 지식 복습

인터페이스란?

• 클래스에 포함하는 메서드의 구체적인 내용을 작성하지 않고 상수와 메서드 타입만 정의한 것
• 인터페이스는 다른 클래스에서 구현하는 것을 전제로 만들어진다.

• 인터페이스를 선언한 메서드는 암묵적으로 public abstract 접근 제어자가 붙은 추상 메서드라고 불린다.

public interface Greet {
    /**
    * 인사하기
    *
    */
    void greeting();
    public abstract void greeting();
    // 암묵적 접근 제어자는 같은 의미를 가진다.
}

• 인터페이스 구현하기

  public class MoringGreet implements Greet {
    @Override
    public void greeting() {
        System.out.println("좋은 아침입니다.");
    }
  }

리스트란?

• 자바에서 복수의 데이터를 더 쉽게 사용할 수 있게 하는 Collection 클래스를 제공한다.
• 컬렉션의 종류

이런 컬렉션의 모음을 컬렉션 프레임워크라고 한다. 컬렉션 프레임워크는 다양한 인터페이스와 구현 클래스로 구성된다.

• 리스트의 개요
  • 여러 데이터를 순서대로 정렬하여 저장할 때 사용

• 리스트 구현

package chapter02;

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

public class ListExercise {
    public static void main(String[] args) {
        // String 타입을 저장할 List를 준비
        List<String> names = new ArrayList<>();

        // String 타입의 데이터 넣기
        names.add("홍길동");
        names.add("김선비");
        names.add("James");

        // for문으로 데이터를 하나씩 출력
        for (String name : names) {
            System.out.println(name);
        }
    }
}

• 실행 결과

2-2. 웹 어플리케이션을 만들기 위한 필수 지식 복습

클라이언트와 서버

• 클라이언트는 서비스를 요청하는 쪽이고 서버는 서비스를 제공하는 쪽이다.
• 서버가 서비스를 제공해 그 서비스를 클라이언트가 사용하는 관계.

어플리케이션과 웹 어플리케이션

• 어플리케이션 (응용 프로그램) : 응용 프로그램 소프트웨어의 약어로 프로그래밍 언어로 작성한 소프트웨어다.
• 웹 어플리케이션 (웹 응용 프로그램) : 인터넷을 통해 사용되는 응용 프로그램이다.

웹 서버

• 웹 서버 : 웹 어플리케이션을 배포하는 서버다. 웹 서버는 항상 실행되며 클라이언트로부터 액세스 (요청) 를 계속 기다린다.

HTTP 통신 (프로토콜)

• 클라이언트와 웹 서버는 HTTP 요청 (request) 과 HTTP 응답 (response) 으로 상호작용하는 것
• 클라이언트의 요청에 대해 웹 서버가 응답하게 된다.
• HTTP 통신의 흐름

1. 클라이언트가 브라우저에 URL을 입력한다.
2. 클라이언트에서 웹 서버로 HTTP 요청이 전송된다.
3. 웹 서버는 HTTP 요청을 받아 HTTP 요청에 해당하는 HTTP 응답을 클라이언트에게 반환한다.
4. 브라우저는 받은 응답을 표시하고 클라이언트가 이를 확인한다.

GET 메서드와 POST 메서드

• GET 메서드 : 브라우저에서 웹 서버로 값을 전달할 때 URL 뒤에 값을 더하여 보내는 방식.

  • URL 뒤에 오는 정보를 쿼리 스트링 또는 쿼리 문자열이라고 부른다.
  • URL 끝에 '?' 가 붙어 쿼리 스트링의 시작을 나타낸다.
  • 형식은 '이름 = 값' 이다.
  • 여러 값을 전달하려면 '&' 로 연결한다. (ex. domain.com/?name=value&tel=010)
  • 쿼리 스트링은 많은 양의 값을 보내기에 적합하지 않다.

• POST 메서드 : 브라우저로부터 웹 서버에 값을 보낼 때 요청 본문이라고 하는 URL에는 보이지 않는 장소에 값을 넣어서 보내는 방법.

  • e-커머스 사이트 등에서 개인정보를 등록할 때 입력한 내용을 URL에 표시하고 싶지 않을 경우에 POST 메서드가 사용되며, 많은 양의 값을 보내는 데 적합하다.

2-3. 개발에 사용하는 편리한 라이브러리와 도구

Lombok 이란?

• getter 나 setter 등의 코드를 작성하지 않아도 자동으로 구현해주는 라이브러리

Gradle 이란?

• Gradle 은 빌드 도구이며, 최근에는 자바 개발의 표준이 되고 있다.
• 빌드 : 요구된 실행 환경에서 동작할 수 있는 형식에 어플리케이션이나 라이브러리를 조립하는 것
  • 빌드 도구는 아래 반복적인 작업을 자동화한다.
    • 필요한 라이브러리를 리포지토리에서 다운로드한다.
    • 소스코드를 컴파일한다.
    • 테스트를 실행하여 보고서를 출력한다.
    • 클래스 파일의 아카이브를 생성한다.
    • 아카이브를 스테이징 환경 등에 배포한다.

01장. 스프링 프레임워크 알아보기

사실 개인적으로 1장의 내용은 정리하면서 보는것보다는 스프링을 사용하기 위한 세팅의 내용이라 가볍게 훑어보려고 한다.

프레임 워크란? (Framework)

• 소프트웨어나 어플리케이션 개발을 간단하게 해주는 뼈대이다.
• 장점
  • 개발에 필요한 최소한의 기능 제공 -> 자신이 모든 기능을 작성할 필요가 없다.
  • 어플리케이션 개발에 필요한 시간과 비용을 줄일 수 있다.
• 단점
  • 프레임워크 고유의 사용법을 이해할 필요가 있다.

스프링 프레임워크란? (Spring Framework)

• 자바 개발 환경에서 사용되는 프레임워크, 줄여서 스프링이라고도 한다.
• 개발을 편하게 할 수 있는 여러가지 기능별로 프로젝트가 존재한다.
• 아래 이미지는 스프링이 제공하는 기능의 일부이다.
• 스프링 부트 (Spring Boot) : 스프링 어플리케이션을 복잡한 설정 없이 빠르게 작성하는 기능을 제공한다.
• 스프링 프로젝트
  • 스프링 데이터 (Spring Data) : 데이터 접근에 관한 기능을 제공한다.
  • 스프링 MVC (Spring MVC) : 웹 어플리케이션을 간단하게 생성하는 기능을 제공한다.
  • 스프링 배치 (Spring Batch) : 배치 처리 기능을 제공한다.
  • 스프링 시큐리티 (Spring Security) : 인증/허가 기능을 제공한다.
• 스프링 코어
  • 스프링 DI (Spring DI) : 의존성 주입 (Dependency Injection) 기능을 제공한다.
  • 스프링 AOP (Spring AOP) : 관점 지향 프로그래밍 (Aspect Oriented Programming) 기능을 제공한다.

개발 환경 준비 (자바)

먼저 자바로 개발하기 위한 필요한 기능을 모아둔 패키지인 JDK (Java Development Kit) 를 설치해보자 JDK는 Oracle JDK, Open JDK, Azul Zulu, BellSoft Liberica JDK를 등 여러 종류가 있지만 이 책에서는 BellSoft Liberica JDK 를 설치한다. 하지만 나는 뒤에 나올 IntelliJ IDE 에서 다운받은 jdk 를 사용하고 있다.

위 이미지처럼 프로젝트 설정해서 JDK를 종류나 버전별로 다운받을 수 있다.

아니라면 원하는 종류의 jdk 를 구글에 검색하면 쉽게 다운로드 할 수 있다. 다운로드 후 설치가 완료되면 명령 프롬프트 창에서 java 라고 치면 아래와 같은 간단한 명령어 소개가 나온다.

추가로 java -version 이라는 명령어를 통해 버전을 확인할 수 있다.

개발 환경 준비 (IDE)

프로그래밍을 편리하게 해주는 도구로 통합 개발 환경 (IDE : Integrated Development Environment) 이 있다. 이 책에서는 JetBrains 사에서 제작한 IntelliJ IDEA 의 무료 버전인 Community 버전을 사용한다. 유료 버전인 Ultimate 버전도 30일 동안은 무료로 이용 가능하니 사용해보면 더 많은 기능을 제공하기 때문에 더 편리하다는게 느껴질것이다.

이미지를 클릭하시면 IntelliJ IDEA 다운로드 링크로 연결됩니다.

개발 환경 준비 (PostgreSQL)

데이터베이스를 간단하게 표현하면 데이터를 보관하는 장소다. 이 책에서는 데이터베이스로 PostgreSQL을 사용한다. 나는 MariaDB를 사용중이었지만 SQLite를 사용해보려한다.

이미지를 클릭하시면 SQLite 다운로드 링크로 연결됩니다.

해당 링크에서 윈도우 버전으로 다운로드 받았다. 다운받은 프로그램을 명령어로 사용하면 된다. 하지만 이는 어려울 수 있으니 GUI 환경에서 제어할 수 있는 프로그램을 새로 받아 사용하도록 하겠다.

SQLiteStudio 라는 프로그램을 사용기로 했다. SQLiteStudio 다운로드 링크

위 링크에서 다운로드 받을 수 있다. 설치 후 실행하면 아래와 같은 화면이 뜬다. 그럼 준비 완료..!

다음 시간에는 자바 기초 지식을 복습하면서 스프링을 활용할 준비를 해야겠다.

👉 큰 문제를 작은 부분 문제로 나누어 해결하는 방법이다.

• 합병 정렬 : 배열을 1개 단위까지 쪼개서 서로 정렬하면서 모아가는 방법
• 퀵 정렬 : pivot을 기준으로 좌우 형태로 재귀 호출을 하며 잘게 나누고 합치면서 정렬하는 방법
• 이진 검색 : 중앙 값을 뽑아서 좌측인지 우측인지 비교하면서 정렬하는 방법
• 등등

👉 분할 정복 과정

1. 문제를 하나 이상의 작은 부분들로 분할한다.
2. 부분들을 각각 정복한다.
3. 부분들의 해답을 통합하여 원래 문제의 답을 구한다.

💡 분할 정복의 장단점

👉 장점

• 문제를 나누어 처리하여 어려운 문제를 해결할 수 있다.
• 병렬처리에 이점이 있다.

👉 단점

• 재귀 호출 구조이기 때문에 메모리를 많이 사용한다.

💡 분할 정복 예시

👉 최대 값 찾기

• 배열 : [3, 5, 10, 50, 25, 30, 1, 15]

public static int getMax(int[] arr, int left, int right) {
    int m = (left + right) / 2;
    if(left == right) return arr[left];

    left = getMax(arr, left, m);
    right = getMax(arr, m + 1, right);

    return (left > right) ? left : right;
}

👉 동적 계획법

👉 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식이다.

👉 중간 계산 결과를 기록하기 위한 메모리가 필요하다.

👉 한 번 계산한 부분을 다시 계산하지 않기 때문에 속도가 빠르다.

💡 다른 알고리즘과의 차이점

👉 분할 정복과의 차이

• 분할 정복은 부분 문제가 중복되지 않는다.
• DP는 부분 문제가 중복되어 재활용에 사용된다.

👉 그리디 알고리즘과의 차이

• 그리디 알고리즘은 순간의 최선을 구하는 방식이다. (근사치를 구한다.)
• DP는 모든 방법을 확인 후 최적해를 구하는 방식이다.

💡 다이나믹 프로그래밍 예시

👉 피보나치 수열

• 피보나치 수열을 기본 재귀로 풀게 되면 f(n) = f(n-1) + f(n-2) ex. f(5) = f(4) + f(3) 을 구하기 위한 연산들을 하고 f(3)을 다시 구하려면 f(3) = f(2) + f(1) 연산을 다시해줘야 한다. 따라서 n의 수가 높아지면 해야하는 연산도 많아진다.
• 피보나치 수열을 DP를 적용해서 풀게 되면 f(n) = f(n-1) + f(n-2) ex. f(5) 를 구하기 위한 연산들을 모두 기록해놓기 때문에 f(3)을 다시 구할 때 재귀 풀이처럼 다시 연산을 하는 것이 아닌, 기록된 정보를 가져온다. 메모리는 필요하지만 중복된 연산을 하지 않기 때문에 속도가 빠르다.

💡 다이나믹 프로그래밍 방법

👉 타뷸레이션 (Tabulation)

• 상향식 접근 방법 (Bottom Up)
• 작은 하위 문제부터 풀면서 올라간다.
• 모두 계산하면서 차례대로 진행하는 방법

👉 메모이제이션 (Memoization)

• 하향식 접근 방법 (Top Down)
• 큰 문제에서 하위 문제를 확인해가면서 진행한다.
• 계산이 필요한 순간에 계산하면서 진행하는 방법

👉 매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법

• 빠르게 근사치를 계산할 수 있다.
• 결과적으로는 최적해가 아닐 수도 있다.

💡 그리디 알고리즘 예시

👉 Activity Selection Problem

• N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기

• 종료 시간 기준으로 정렬한다.

• 먼저 종료되는 활동 순, 겹치지 않는 순으로 선택한다.

1. 가장 먼저 종료되는 C
2. A는 시작시간이 이미 지나버렸으므로 패스
3. 그 다음 일찍 종료되는 B
4. D도 이미 시작했으므로 패스
5. 마지막으로 남은 E를 선택하면 총 3가지 활동을 할 수 있게된다.

👉 거스름돈 (동전의 최소 개수)

1. case 1
   • 잔돈 : 890원
   • 동전의 종류 : 10, 50, 100, 500

   • 큰 동전부터 계산한다.

2. case 2 (그리디 알고리즘을 적용할 수 없는 경우)

   • 잔돈 : 890원

   • 동전의 종류 : 10, 50, 100, 400, 500

   • 큰 동전부터 계산한다.

   • 그리디 알고리즘 결과

   잔돈	500	400	100	50	10
   개수	1	0	3	1	4

   • 우리가 원하는 정답 (동전의 최소 개수)

   잔돈	500	400	100	50	10
   개수	0	2	0	1	4

👉 그리디 알고리즘 적용 조건

• 그리디 알고리즘은 빠르지만 최적해를 보장하지는 못한다.
• 아래 두 가지 조건에 해당하는 경우 적용할 수 있다.
  • 탐욕적 선택 특성 (Greedy choice property) : 지금 선택이 다음 선택에 영향을 주지 않는다.
  • 최적 부분 구조 (Optimal substructure) : 전체 문제의 최적해는 부분 문제의 최적해로 이루어진다.

👉 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법이다.

👉 두 개의 포인터 배치 방법은 아래와 같다.

• 같은 방향에서 시작하는 경우 : 첫 번째 원소에 둘 다 배치한다.
• 서로 다른 방향에서 시작하는 경우 : 첫 번째 원소와 마지막 원소에 배치한다.

  👉 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있다.

💡 투 포인터 예시

👉 아래 배열에서 부분 합이 9가 되는 구간을 찾는 방법

[1, 2, 5, 3, 7, 2, 4, 3, 2]

• 기존 단순 for문 이용 방법
  • 0번 인덱스 ~ 0번 + 1 인덱스 값들을 끝까지 더하면서 Target 9가 되는 구간 찾기
  • 1번 인덱스 ~ 1번 + 1 인덱스 값들을 끝까지 더하면서 Target 9가 되는 구간 찾기
  • 위와 같은 방식으로 마지막 인덱스까지 루프를 돌면서 Target 9가 되는 구간을 찾는다.

  • 알고리즘 시간복잡도 : O(n제곱)

• 투 포인터 방법
  • 포인터 P1과 포인터 P2를 지정하고 Target 9 보다 작으면 P1 을 이동하고 더하면서 Target 9가 되는 구간을 찾는다.
  • Target 9 보다 크면 P2 를 이동하고 빼면서 구간을 찾는다.

  • 알고리즘 시간복잡도 : O(n)

👉 정렬된 상태의 데이터에서 특정 값을 빠르게 검색하는 방법

• 찾고자 하는 값과 데이터 중앙에 있는 값을 비교한다.
• 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색을 진행한다.
• 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색을 진행한다.

  👉 알고리즘 시간 복잡도 : O(logn)

💡 이진 탐색 과정

👉 조건

• 데이터가 우선 정렬된 상태여야 이진 탐색을 진행할 수 있다.

  👉 예시

• 배열 : [1, 2, 5, 10, 20, 30, 40, 50, 60]
• 찾고자 하는 데이터 : 30
  1. 찾고자 하는 값과 데이터 중앙에 있는 값 20 (mid = (0+8) / 2 = 4) 을 비교한다.
  2. 값이 더 크므로 데이터 오른쪽 부분에서 이진 탐색을 진행한다.
  3. 찾고자 하는 값과 데이터 중앙에 있는 값 40 (mid = (0+3) / 2 = 1) 을 비교한다.
  4. 값이 더 작으므로 데이터 왼쪽 부분에서 이진 탐색을 진행하면 30을 찾을 수 있다.

👉 낮은 자리 수부터 정렬하는 방식 (1의 자리, 10의 자리, 100의 자리 등)

👉 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블 (Queue) 을 위한 메모리가 필요하다.

👉 알고리즘 복잡도 : O(dn) (d : 최대 자리수)

💡 기수 정렬 과정

1. 배열의 원소들의 1의 자리수를 먼저 비교해서 Queue로 구현한 기수 테이블에 자리수별로 Queue에 넣어준다.
2. 0번부터 9번까지 dequeue 시켜줘서 꺼내준다.
3. 10의 자리수를 기준으로 똑같이 inqueue 한 후 0번부터 9번까지 dequeue 시켜줘서 정렬한다.

💡 계수 정렬 (Counting Sort)

👉 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식이다.

👉 카운팅을 위한 카운팅 테이블 (Array) 메모리가 필요하다.

👉 알고리즘 복잡도 : O(n + k) (k : 정렬 대상 데이터 중 최대값)

💡 계수 정렬 과정

1. Array 로 구현한 카운팅 테이블에 각 원소들을 돌면서 개수를 세어준다.
2. Array 0번부터 돌면서 배열에 저장해서 정렬해준다.

💡 셸 정렬 (Shell Sort)

👉 삽입 정렬의 약점을 보완한 정렬 방식이다.

👉 삽입 정렬의 약점

• 오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환해야 한다.

  👉 이전의 모든 데이터와 비교하지 않고 일정 간격을 두고 비교한다.

  👉 알고리즘 복잡도 : O(n²)

간격 설정에 따라 Worst Case는 삽입 정렬과 동일하다. 일반적인 산포 데이터 기준으로는 삽입 정렬에 비해 빠르다.

💡 셸 정렬 과정

1. 0번부터 Gap을 두고 비교하여 삽입 정렬해준다. (Gap = 배열 길이 / 2)
2. 한번 정렬할 때마다 Gap을 2로 나눠 좁은 간격으로 비교해서 삽입 정렬해준다.

💡 정렬 알고리즘 복잡도 Summary

• 보조 메모리가 1인 정렬들은 제자리 정렬 (in-place 정렬) 이 가능한 정렬이다.

• 코딩 테스트에서 in-place로 문제를 풀라고 하거나, 일부 컨스턴스 메모리를 제외한 메모리를 추가로 사용하지 말라고 하면 n, nlogn, n+k 가 필요한 정렬을 피해서 풀어야한다.
• 안정한 정렬은 정렬 후 값의 자리가 바뀌지 않는 경우이다.

👉 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식이다.

👉 알고리즘 복잡도 : O(nlogn)

💡 합병 정렬 과정

1. 배열의 가운데 인덱스를 기준으로 둘로 나눈다.
2. 나눈 배열의 가운데 인덱스를 기준으로 다시 둘로 나눈다.
3. 같은 방법으로 각 배열의 길이가 1이 될 때까지 분할한다.
4. 각각 분할된 배열의 수를 비교하여 오름 or 내림 차순으로 붙여준다.
5. 같은 방법으로 배열들을 다시 합쳐서 정렬한다.

정렬 - 1 에서 정리했던 버블, 삽입, 선택 정렬과 비교했을 때 배열들을 나누고 저장하는 메모리가 더 필요하지만, 트리 구조이기 때문에 속도는 더 빠르다.

💡 힙 정렬 (Heap Sort)

👉 힙 자료구조 형태의 정렬 방식이다.

👉 기존 배열을 최대 힙으로 구조 변경 후 정렬을 진행한다.

👉 알고리즘 복잡도 : O(nlogn)

💡 퀵 정렬 (Quick Sort)

👉 임의의 기준 값 (pivot) 을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식이다.

👉 알고리즘 복잡도 : O(n²) (일반적으로는 빠른 알고리즘 이지만, 기준 값이 최소값 또는 최대값으로 지정되는 경우)

💡 퀵 정렬 과정

1. pivot 을 가장 왼쪽으로 임의로 지정했을 때, 왼쪽에서부터 pivot 보다 큰 값, 오른쪽에서는 pivot 보다 작은 값이 최초로 나오는 케이스를 찾는다.
2. 두 수를 바꾸고 같은 방식을 반복한다.
3. 왼쪽에서는 인덱스가 커지고 오른쪽에서는 작아지기 때문에 만나는 구간에서 종료하고 pivot 값과 자리를 바꿔준다.
4. 바뀐 pivot 값을 기준으로 분할하여 같은 방식을 진행하여 정렬한다.

💡 트리 정렬 (Tree Sort)

👉 이진 탐색 트리 (Binary Search Tree) 를 만들어 정렬하는 방식이다.

👉 알고리즘 복잡도 : O(nlogn)

👉 특정 값을 기준으로 데이터를 순서대로 배치하는 방법이다.

💡 정렬의 종류

👉 구현 난이도는 쉽지만, 속도는 느린 알고리즘

• 버블 정렬
• 삽입 정렬
• 선택 정렬

  👉 구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘

• 합병 정렬
• 힙 정렬
• 퀵 정렬
• 트리 정렬

  👉 하이브리드 정렬

• 팀 정렬
• 블록 병합 정렬
• 인트로 정렬

  👉 기타 정렬 알고리즘

• 기수 정렬
• 카운팅 정렬
• 셸 정렬
• 보고 정렬

💡 버블 정렬

👉 인접한 데이터를 비교하며 자리를 바꾸는 방식이다.

👉 알고리즘 복잡도 : O(n²)

💡 버블 정렬 과정

1. 배열의 가장 작은 인덱스 부터 두 수를 비교해서 작은 수를 왼쪽으로 큰 수를 오른쪽으로 보내서 자리를 바꿔준다.
2. 같은 방식으로 마지막 인덱스까지 자리를 바꿔주면 가장 큰 수가 마지막 인덱스에 자리하게 된다.
3. 끝에서부터 자리를 잡게된 수를 제외하고 횟수가 한번씩 줄게된다.

따라서 수행 횟수는 O(n²) = n(n-1)/2 가 된다.

💡 버블 정렬의 구현

👉 의사 코드 (Pseudocode)

의사코드 (Pseudo code) : 알고리즘 flow 파악용으로 실제 돌아가는 코드는 아니다. 슈도 코드라고도 읽고, 가짜 코드라고도 한다.

bubbleSort(arr[]){
    arr[SIZE]
    for i=1 to SIZE-1 {
        for j=0 to SIZE-i {
            if(arr[j] > arr[j+1])
                swap (arr[j],arr[j+1])
        }
    }
}

💡 삽입 정렬 (Insertion Sort)

👉 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식이다.

👉 알고리즘 복잡도 : O(n²)

💡 삽입 정렬 과정

1. 1번 인덱스부터 앞의 데이터와 비교해서 더 작으면 앞으로 삽입해준다.
2. 인덱스를 뒤로 옮겨가면서 똑같이 비교하면서 진행한다.
3. 만약 비교했는데 크면 그대로 둔다.
4. 버블 정렬과는 다르게 앞의 모든 수와 비교해서 작으면 앞으로 삽입해준다.
5. 마지막 인덱스까지 비교해서 정렬해준다.

따라서 수행 횟수는 O(n²) = n(n-1)/2 가 된다. 하지만 수가 큰 경우 비교를 하지 않는 경우도 발생하기 때문에 버블 정렬보다는 평균적으로 빠르다.

💡 삽입 정렬의 구현

👉 의사 코드 (Pseudocode)

insertionSort(arr[]){
    arr[SIZE]
    for i=1 to SIZE {
        for j=i to 0 (j--) {
            if(arr[j] < arr[j-1])
                swap (arr[j],arr[j-1])
        }
    }
}

💡 선택 정렬 (Selection Sort)

👉 주어진 값에서 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식이다.

👉 알고리즘 복잡도 : O(n²)

💡 선택 정렬 과정

1. 배열에서 전체 값을 비교해가면서 최소값을 찾아서 가장 앞의 데이터와 위치를 바꿔준다.
2. 남은 데이터 중에서 최소값을 찾아서 가장 앞의 데이터와 위치를 바꿔준다.
3. 같은 방식으로 계속 진행해서 정렬한다.

따라서 수행 횟수는 O(n²) = n(n-1)/2 가 된다.

위 세가지 정렬은 제자리 정렬 (in-place sort) 이라고도 한다. 배열 내에서 자리만 바꿔가면서 정렬하는 방식이기 때문에 추가적인 데이터는 따로 필요하지 않다. 따라서 메모리를 최소한으로 사용하면서 정렬하는 방식이다.

💡 선택 정렬의 구현

👉 의사 코드 (Pseudocode)

insertionSort(arr[]){
    arr[SIZE]
    for i=0 to SIZE-1 {
        min=i
        for j=i+1 to SIZE {
            if(arr[j] < arr[min])
                min=j
        }
        swap (arr[i],arr[min])
    }
}

👉 알고리즘이란?

• 어떤 문제 해결을 위한 절차나 방법을 말한다.
• 각각의 알고리즘에는 정형화된 플로우가 있다.

👉 알고리즘의 조건

• 입력
• 출력
• 명확성
• 유한성
• 효율성

👉 좋은 알고리즘이란?

• 정확성 : 가장 중요하다. 아무리 빠르고 효율적으로 처리하더라도 정답 값과 조금이라도 차이가 있다면 좋은 알고리즘이라고 볼 수 없다.
• 시간 복잡도 : 빠르게 처리하는 것이 중요하다.
• 공간 복잡도

👉 아래의 규칙으로 구성된 이진 트리

• 왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키
• 각각의 서브 트리도 이진 탐색 트리를 유지한다.
• 중복된 키를 허용하지 않는다.

💡 이진 탐색 트리의 특징

👉 이진 탐색 트리 규칙에 의해 데이터가 정렬된다.

👉 이진 트리에 비해 탐색 속도가 빠르다. (But, 균형 유지 필요)

• 균형 상태에서의 속도 : O(logN)
• 불균형 상태에서의 속도 : O(N)

💡 이진 탐색 트리 - 탐색

👉 찾고자 하는 데이터를 루트 노드부터 비교한다.

👉 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동한다.

👉 찾는 데이터가 없으면 null 을 반환한다.

👉 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어진다.

💡 이진 탐색 트리 - 삽입

👉 루트 노드부터 대소 비교한다.

👉 중복 키 발견 시 노드를 추가하지 않고 종료한다.

👉 삽입할 키 < 현재 노드의 키 -> 왼쪽으로 이동

👉 삽입할 키 > 현재 노드의 키 -> 오른쪽으로 이동

👉 Leaf 노드에 도달 후 키 값을 비교하여 작으면 왼쪽, 크면 오른쪽에 삽입한다.

💡 이진 탐색 트리 - 삭제

👉 삭제 대상 노드가 Leaf 노드인 경우

• 삭제 대상 노드를 삭제한다.
• 부모 노드의 해당 자식 링크를 null 로 변경한다.

👉 삭제 대상 노드에 자식 노드가 하나인 경우

• 자식 노드를 삭제 대상 노드의 부모 노드에 연결한다.
• 삭제 대상 노드를 삭제한다.

👉 삭제 대상 노드에 자식 노드가 둘인 경우

• 두 가지 방법
  1. 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드를 선택하는 방법
     2. 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드를 선택하는 방법
• 1 or 2 에서 선택한 노드를 삭제 대상 노드 위치로 올린다.
• 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업을 진을한다.
• 삭제 대상 노드를 삭제한다.

💡 균형 이진 트리

👉 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리

💡 이진 탐색 트리의 편향 발생

👉 Case 1. 이진 탐색 트리에 삽입되는 순서 : 20 -> 10 -> 30 -> 5

👉 Case 2. 이진 탐색 트리에 삽입되는 순서 : 5 -> 10 -> 20 -> 30

💡 균형 이진 탐색 트리

👉 Balanced Binary Search Tree

👉 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리

👉 종류 : AVL트리, Red-Black 트리

💡 AVL 트리

👉 노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리

👉 각 노드의 BF를 -1, 0, 1 만 가지게 하여 균형을 유지한다.

👉 종류 : AVL트리, Red-Black 트리

BF (Balance Factor) = 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이

💡 AVL 트리 - 리밸런싱

👉 균형이 깨진 경우

• BF가 양수면 왼쪽 서브 트리에 이상이 있다.
• BF가 음수면 오른쪽 서브 트리에 이상이 있다.

👉 회전 연산을 통해 리밸런싱을 해준다.

• 단순 회전 : LL, RR
• 이중 회전 : LR, RL

👉 LL (Left-Left)

• 단순 회전으로 1회만 회전한다.
• 왼쪽 서브 트리에 이상이 있으므로 오른쪽 방향으로 회전하여 균형을 유지한다.

👉 RR (Right-Right)

• 단순 회전으로 1회만 회전한다.
• 오른쪽 서브 트리에 이상이 있으므로 왼쪽 방향으로 회전하여 균형을 유지한다.

👉 LR (Left-Right)

• 이중 회전으로 2회 회전한다.
• RR 회전 후 LL 회전하여 균형을 유지한다.

👉 RL (Right-Left)

• 이중 회전으로 2회 회전한다.
• LL 회전 후 RR 회전하여 균형을 유지한다.

💡 Red-Black 트리

👉 조건

• Root 노드와 Leaf 노드의 색은 Black
• Red 색 노드의 자식은 Black (Double Red 는 불가능하다.)
• 모든 Leaf 노드에서 Root 노드까지 가는 경로의 Black 노드 수는 같다.

  👉 조건이 깨지는 상황에서 Rebalancing

💡 Red-Black 트리 - 삽입

👉 노드가 삽입 될 때는 Red 로 삽입된다.

👉 노드 삽입 후 Double Red 가 발생하는 경우

👉 Case 1. 부모 노드의 형제 노드가 Red 일 때

• Recoloring을 진행한다.
• 삽입한 노드의 부모와 부모의 형제 노드를 Black 으로 변경한다.
• 부모의 부모 노드를 Red 로 변경한다.
• 부모의 부모 노드가 Root 인지 Double Red 인지에 따라 조정을 진행한다.

👉 Case 2. 부모 노드의 형제 노드가 Black 이거나 없을 때

• Restructuring을 진행한다.
• 조정 대상 : 삽입한 노드, 부모 노드, 부모의 부모 노드
• 조정 대상 노드들을 오름차순으로 정렬한다.
• 가운데 노드를 부모 노드로 선정하고 Black 으로 변경한다.
• 나머지 두 노드를 자식 노드로 두고 Red 로 변경한다.

💡 Red-Black 트리 - 삭제

👉 Case 1. 기본 : 삭제 대상 노드가 Black 이고 그 자리에 오는 노드가 Red 인 경우

• 해당 자리로 오는 Red 노드를 Black 으로 변경한다.

👉 Case 2. Double Black Case : 삭제 대상 노드가 Black 이고, 그 자리에 오는 노드도 Black 인 경우

👉 Case 2-1. 이중 흑색 1 : 이중 흑색 노드의 형제 노드가 Black 이고, 형제의 양쪽 자식 모두 Black 인 경우

• 형제 노드를 Red 로 변경한다.
• 이중 흑색 노드의 검은색 1개를 부모 노드로 전달한다.
• 부모가 Root 가 아닌 이중 흑색 노드가 되면 해당 Case 를 반복한다.

👉 Case 2-2. 이중 흑색 2 : 이중 흑색 노드의 형제 노드가 Red 인 경우

• 형제 노드를 Black 으로 변경한다.
• 부모 노드를 Red 로 변경한다.
• 부모 노드를 기준으로 왼쪽으로 회전한다.
• 그 다음 이중 흑색 Case 에 따라 반복한다.

👉 Case 2-3. 이중 흑색 3-1 : 이중 흑색 노드의 형제 노드가 Black 이고, 오른쪽 자식이 Red 인 경우

• 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경한다.
• 부모 노드를 기준으로 왼쪽으로 회전한다.

👉 Case 2-4. 이중 흑색 3-2 : 이중 흑색 노드의 형제 노드가 Black 이고, 왼쪽쪽 자식이 Red 인 경우

• 형제 노드를 Red 로 변경한다.
• 형제 노드의 왼쪽 자식 노드를 Black 으로 변경한다.
• 형제 노드를 기준으로 오른쪽으로 회전한다.
• 이중 흑색 3-1 Case를 진행한다.

💡 Red-Black 트리 VS AVL 트리

👉 알고리즘 시간 복잡도

• 모두 O(logN)

  👉 균형 수준

• AVL 트리가 Red-Black 트리보다 좀 더 엄격하게 균형을 잡는다.
• Red-Black 트리는 색으로 구분하는 경우로 인해 회전 수가 감소한다.

  👉 실제 사용 시, Tree 체계가 잡힌 후, 탐색이 많은 경우에는 AVL 트리가 유리하고, 삽입, 삭제가 빈번한 경우에는 Red-Black 트리가 더 유리하다.

💡 트리 (Tree)

👉 노드와 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음)

• 연결 리스트도 트리의 일종

👉 계층적 구조를 나타낼 때 사용하는 자료구조

• 폴더 구조 (디렉토리, 서브 디렉토리)
• ex. 조직도, 가계도 등

💡 트리의 구조

👉 노드 (Node) : 트리 구조의 자료 값을 담고 있는 단위

👉 에지 (Edge) : 노드 간의 연결선 (=link, branch)

👉 루트 노드 (Root) : 부모가 없는 노드, 최상단 노드

👉 잎새 노드 (Leaf) : 자식이 없는 노드 (=단말)

👉 내부 노드 (Internal) : 잎새 노드를 제외한 모든 노드

👉 부모 (Parent) : 연결된 두 노드 중 상위의 노드

👉 자식 (Child) : 연결된 두 노드 중 하위의 노드

👉 형제 (Sibling) : 같은 부모를 가지는 노드

👉 깊이 (Depth) : 루트에서 어떤 노드까지의 간선의 수

👉 레벨 (Level) : 트리의 특정 깊이를 가지는 노드 집합

👉 높이 (Height) : 트리에서 가장 큰 레벨 값

👉 크기 (Size) : 자신을 포함한 자식 노드의 개수

👉 차수 (Degree) : 각 노드가 지닌 가지의 수

👉 트리의 차수 : 트리의 최대 차수

💡 트리의 특징

👉 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다.

👉 노드가 N개인 트리의 Edge의 수는 N-1개이다.

👉 Acyclic : Cycle이 존재하지 않는다.

👉 모든 노드는 서로 연결되어 있다.

👉 하나의 Edge를 끊으면 2개의 Sub-Tree 로 분리된다.

💡 이진 트리 (Binary Tree)

👉 각 노드는 최대 2개의 자식을 가질 수 있다.

👉 자식 노드는 좌우를 구분한다.

• 왼쪽 자식 : 부모 노드의 왼쪽 아래
• 오른쪽 자식 : 부모 노드의 오른쪽 아래

💡 이진 트리의 종류

👉 포화 이진 트리 (Perfect Binary Tree)

• 모든 레벨에서 노드들이 꽉 채워져 있는 트리

  👉 완전 이진 트리 (Complete Binary Tree)

• 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

  👉 정 이진 트리 (Full Binary Tree)

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

  👉 편향 트리 (Skewed Binary Tree) (사향 트리)

• 한쪽으로 기울어진 트리

  👉 균형 이진 트리 (Balanced Binary Tree)

• 모든 노드의 좌우 서브 트리 높이가 1 이상 차이가 나지 않는 트리

💡 이진 트리의 특징

👉 포화 이진 트리의 높이가 h 일때, 노드의 수는 2ʰ⁺¹ - 1개

👉 포화 or 완전 이진 트리의 노드가 N 개 일 때, 높이는 logN

👉 이진 트리의 노드가 N 개 일 때, 최대 가능 높이는 N - 1

💡 이진 트리의 순회 (Traversal)

👉 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산

👉 순회 종류

• DFS (Depth First Search) : 전위 순회, 중위 순회, 후위 순회
• BFS (Breadth First Search) : 레벨 순회

💡 이진 트리의 순회 - 전위 순회

👉 Preorder Traversal

👉 방문 순서 : 현재 노드 → 왼쪽 노드 → 오른쪽 노드

💡 이진 트리의 순회 - 중위 순회

👉 Inorder Traversal

👉 방문 순서 : 왼쪽 노드 → 현재 노드 → 오른쪽 노드

💡 이진 트리의 순회 - 후위 순회

👉 Postorder Traversal

👉 방문 순서 : 왼쪽 노드 → 오른쪽 노드 → 현재 노드

💡 이진 트리의 순회 - 레벨 순회

👉 Levelorder Traversal

👉 방문 순서 : 위쪽 레벨부터 왼쪽 노드 → 오른쪽 노드

💡 이진 트리의 구현

👉 배열

• 레벨 순회 순으로 배열에 구성

👉 연결 리스트

• 값과 간선을 관리하기 위한 노드로 연결리스트 구성

💡 힙 (Heap)

👉 완전 이진 트리 형태

• 마지막 레벨을 제외하고 다 차있는 형태 (좌측부터)
• 중복 값 허용
• 반 정렬 상태

  👉 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조

• 최소 힙 : 가장 위의 노드 값이 최소값
• 최대 힙 : 가장 위의 노드 값이 최대값

💡 최소힙 (Min Heap)

👉 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태

✔ 삽입

👉 트리의 가장 끝 위치에 데이터를 삽입한다.

👉 부모 노드와 키를 비교한 후 작을 경우 부모 자리와 교체를 반복한다.

✔ 삭제

👉 최상위 노드를 반환 및 삭제한다.

👉 가장 마지막 위치의 노드를 최상위 노드로 위치 시킨다.

👉 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체를 반복한다.

💡 최대힙 (Max Heap)

👉 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태

📖 최소힙, 최대힙을 활용하여 오름차순, 내림차순 정렬 예제

import java.util.ArrayList;

class MinHeap{
    ArrayList<Integer> heap;

    public MinHeap() {
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }

    public void insert(int data) {
        heap.add(data);

        int cur = heap.size() - 1;
        while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) {
            int parentVal = heap.get(cur / 2);
            heap.set(cur / 2, data);
            heap.set(cur, parentVal);

            cur /= 2;
        }
    }

    public Integer delete() {
        if (heap.size() == 1) {
            System.out.println("Heap is empty!");
            return null;
        }

        int target = heap.get(1);

        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        int cur = 1;
        while (true) {
            int leftIdx = cur * 2;
            int rightIdx = cur * 2 + 1;
            int targetIdx = -1;

            if (rightIdx < heap.size()) {
                targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < heap.size()) {
                targetIdx = cur * 2;
            } else {
                break;
            }

            if (heap.get(cur) < heap.get(targetIdx)) {
                break;
            } else {
                int parentVal = heap.get(cur);
                heap.set(cur, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                cur = targetIdx;
            }
        }

        return target;
    }

    public void printTree() {
        for (int i = 1; i < this.heap.size(); i++) {
            System.out.print(this.heap.get(i) + " ");
        }
        System.out.println();
    }
}

class MaxHeap{
    ArrayList<Integer> heap;

    public MaxHeap() {
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }

    public void insert(int data) {
        heap.add(data);

        int cur = heap.size() - 1;
        while (cur > 1 && heap.get(cur / 2) < heap.get(cur)) {
            int parentVal = heap.get(cur / 2);
            heap.set(cur / 2, data);
            heap.set(cur, parentVal);

            cur /= 2;
        }
    }

    public Integer delete() {
        if (heap.size() == 1) {
            System.out.println("Heap is empty!");
            return null;
        }

        int target = heap.get(1);

        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        int cur = 1;
        while (true) {
            int leftIdx = cur * 2;
            int rightIdx = cur * 2 + 1;
            int targetIdx = -1;

            if (rightIdx < heap.size()) {
                targetIdx = heap.get(leftIdx) > heap.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < heap.size()) {
                targetIdx = cur * 2;
            } else {
                break;
            }

            if (heap.get(cur) > heap.get(targetIdx)) {
                break;
            } else {
                int parentVal = heap.get(cur);
                heap.set(cur, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                cur = targetIdx;
            }
        }

        return target;
    }

    public void printTree() {
        for (int i = 1; i < this.heap.size(); i++) {
            System.out.print(this.heap.get(i) + " ");
        }
        System.out.println();
    }
}

public class Practice2 {
    public static void solution(MinHeap minHeap) {
        MaxHeap maxHeap = new MaxHeap();

        System.out.print("오름차순 : ");
        while (minHeap.heap.size() != 1) {
            int data = minHeap.delete();
            System.out.print(data + " ");
            maxHeap.insert(data);
        }
        System.out.println();

        System.out.print("내림차순 : ");
        while (maxHeap.heap.size() != 1) {
            System.out.print(maxHeap.delete() + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Test code
        MinHeap minHeap = new MinHeap();
        minHeap.insert(30);
        minHeap.insert(40);
        minHeap.insert(10);
        minHeap.insert(50);
        minHeap.insert(60);
        minHeap.insert(70);
        minHeap.insert(20);
        minHeap.insert(30);

        solution(minHeap);
    }
}

💡 데크 (Deque)

👉 양쪽에서 삽입과 삭제가 모두 가능한 자료구조

• Deque : Doubly - ended Queue
• Stack과 Queue를 합친 형태

💡 데크 기본 구조

👉 데크의 기본 구조는 양방향에서 삽입과 삭제가 가능한 구조

👉 일부 기능을 제한하여 용도에 맞게 변형이 가능하다.

• add, remove 는 예외를 발생시켜 예외 처리를 하고, offer, poll의 경우는 null 이나 false 를 반환한다.

👉 입력제한 데크 (Scroll)

• 한 쪽의 입력을 제한한 데크 (Front, Rear 중 한 쪽)

  👉 출력제한 데크 (Scroll)

• 한 쪽의 출력을 제한한 데크 (Front, Rear 중 한 쪽)

📖 팰린드롬 (Palindrome) 판별하기 예제

import java.util.ArrayDeque;
import java.util.Deque;

public class Practice2 {
    public static boolean checkPalindrome(String str) {
        Deque deque = new ArrayDeque();
        boolean isPalindrome = true;

        for(String s : str.split("")){
            deque.addFirst(s);
        }

        while (!deque.isEmpty()) {  // 데크가 빌때까지 루프
            String s1 = (String)deque.pollFirst();  // remove를 사용하면 비어있을 때 예외발생하지만
            String s2 = (String)deque.pollLast();   // poll 을 사용하여 null 이 저장되는걸 활용한다.

            if(s1 != null && s2 != null && !s1.equals(s2)){     // 팰린드롬이 아닌 경우
                isPalindrome = false;
                break;
            }
        }

        return isPalindrome;
    }

    public static void main(String[] args) {
        System.out.println(checkPalindrome("a"));       // true
        System.out.println(checkPalindrome("aba"));     // true
        System.out.println(checkPalindrome("abba"));    // true
        System.out.println(checkPalindrome("abab"));    // false
        System.out.println(checkPalindrome("abcba"));   // true
        System.out.println(checkPalindrome("abccba"));  // true
        System.out.println(checkPalindrome("madam"));  // true
    }
}

❓ 어떻게 공부하는게 나에게 효율적일까?

학생 때부터 공부와는 거리가 멀었던지라 공부하면서 생기는 공부 방법이라는게 나에게는 없다. 그나마 제일 몰입하고 열심히 공부했던게 수료했던 국비 지원 프로그램을 받은 약 8개월이었다. 처음 배워보는 분야고 살아온 인생도 거리가 멀었기에 더 열심히 했고 재미도 있었다.

사실 그때에도 나만의 공부법이 따로 생기지는 않았다. 그저 따라 치는데에만 급급했었다. 그렇게 프로젝트같지 않은 프로젝트를 진행하다보니 완전 멘붕이었다.

프로젝트를 진행하면서 가장 공부를 여러가지로 한것 같지만 주먹구구식이었다. 그렇게 내린 결론들이 좀 있다.

먼저 나를 믿지 말자

'나는 애초에 게으른 사람이다.' 이걸 잊지말자. MBTI는 J 라서 계획은 잘 짜는데 미루게되는 일이 많았다.

나를 믿지 말고 지금은 제로베이스를 믿어보자. 데일리로 어느정도까지는 해야되는지 알려주니 못해도 그렇게라도 진도를 맞춰보자. 상황이 된다면 무조건 더해야된다. 넌 백수가 아니다. 시간이 없다. 빡씨게 해야된다..

그리고 지금 제로베이스 과정을 공부하는 데에도 그래도 JAVA 기초는 거의 아는 부분이고 기억에 많이 남아 조금만 봐도 기억이 잘 떠올랐다.

하지만, 코딩 테스트는 고려해보지 않았던 부분이라 자료구조나 기초 수학조차 나에게는 어렵게 느껴지고 있다.

이해가 도통 안되는 부분도 너무 많았어서 나름 방법을 찾았다.

문제조차 이해가 가지 않으면 빠르게 답을 찾아보고, 역으로 답을 통해 문제를 이해하자.

오늘 라이브 세션에서 신제용 강사님도 모르는 문제를 너무 오래 붙잡고 있지 말고 답을 찾아보고 공부하는 방법을 소개해주셨는데, 정말 와닿는 말씀이었다. 문제조차 이해가 가지 않는데 몇시간이고 붙잡고 있는다고 절대 이해가 되지 않는다고 생각했다. 이렇게 푼 문제는 잘 정리해두고 일정 기간 뒤에 다시 풀어보는 식으로 공부하려고 한다.

블로그에 잘 정리해두자

제로베이스에서도 그런 습관을 만들어주기 위해서 블로그 과제를 내줬다고 생각한다. 이전에 공부할 때는 노션에 정리해두었는데 그건 나만 보기 위한 정리였다. 사실 지금 과제도 시간에 쫓겨 급급하게 원하는대로 정리가 되지는 않지만, 블로그를 작성하는 이유를 생각해보자. 취업할 때 도움이 될 수도 있겠지만, 나는 내가 찾아보기 위함도 크다. 필요한 정보를 찾을 때 우선 검색을 하는데 나는 내가 쓴 글을 검색해서 볼 수 있으면 그게 가장 좋다고 생각한다. 내가 이해할 수 있는 정도면 누가 봐도 이해할 수 있는 글이라고 생각되어 그만큼 신경써서 잘 정리하고 싶다.

회사를 활용하자

나처럼 직장이나 다른 일들을 병행하는 수강생들도 많겠지만, 재직자로서 퇴근 후 공부하기가 시간도 부족하고 뒤쳐지는 느낌이 너무 강하게 든다. 이걸 그나마 극복할 수 있는건 회사에서의 자원을 최대한 활용해보려 한다. 과정 중에서 관련된 부분이 그렇게 많지는 않겠지만, 추후 필요할지 모르는 부분이기에 잘 준비해두려고 한다. DB, 쿼리, 인터페이스, Linux 등 회사의 업무들을 관련된 내용은 기록하기 어렵겠지만, 업무를 보면서 공부하는 내용들을 잘 정리해야겠다.

많은 내용을 적지는 못했지만 적은 몇가지라도 잘 지키면서 공부를 해내가고싶다. 앞으로 좋은 개발자가 되기위해서 열심히 공부해야겠다.

백엔드 개발자가 되기로 마음 먹고 공부를 시작하면서 나는 어떤 백엔드 개발자가 되고 싶은지에 대해 고민해보았다. 그와 동시에 나는 어떤 백엔드 개발자가 될 수 있는지도 함께 고민하게 되었다.

사실 아직도 개발자가 어떻게 일하는지 직접적으로 본 적이 없어서 쫓아가야할 목표라는게 뚜렷하게 없다. 주변에도 상담을 하거나 궁금한걸 물어볼 개발자가 없는지라 먼저 검색해보았다. 가장 많이 나오는 개발자의 경력 및 기술 향상을 위한 로드맵이나 테크트리를 매년 트랜드에 맞게 안내해주는 개발자 로드맵 사이트를 들어가보니 그 안에서도 엄청나게 많은 분류로 나뉘어져 있었다.

놀랍게도 일부만 캡쳐했다..

그래도 백엔드 개발자가 되기로 마음먹었으니 백엔드 로드맵을 살펴보았다. 로드맵을 살펴보니 지금 내가 공부하고 있는 Java 언어 뿐만 아니라 그 외에도 공부해야할 것들이 산더미 같았다.

이렇게 미치지는 않을까 걱정된다....

사실 미쳐서라도 훌륭한 일을 해낼수 있다면 난 감사하다. 그런 입장이기에 미친듯이 공부해야겠다. 우선 지금 공부중인 제로베이스를 기반으로 공부하고, 비전공자이기에 CS 공부도 남들보다 더 해야겠다. 정처기도.. 한번 떨어졌지만 다시 공부해서 내년 1차때 꼭 따야겠다. 그래도 DB는 지금 하고 있는 솔루션 유지보수 업무가 도움이 조금은 될지도 모르겠다. 회사에서 최대한 서버, DB에 대한 내용들을 뽑아먹을 계획이다.

지금 내가 될 수 있는 개발자는 지식이 없기에 그저 소통을 잘 하는 개발자가 되고 싶다. 혼자 일하는게 아닌 회사나 팀 구성에 따라 디자이너, 프론트엔드 개발자, 기획자 등과 함께 업무를 하게 될텐데, 여기서 소통을 원활하게 할 수 있는 개발자가 되고싶다.

소통을 원활하게 하려면 그들이 말하는걸 잘 이해할 수 있어야하기에 내 업무만 잘한다고 되는게 아니라는걸 짧다면 짧은 회사생활에서 느껴왔다.

내가 내 맡은 바 뒤쳐지지 않게 할 수 있다면 주변도 둘러보고 나와 직접적이지 않더라고 간접적으로라도 관련이 있다면 무심코 지나치지않고 그 부분에 대해서 한 번, 두 번이라도 찾아보려고 노력할거다.

또 먼 훗날 이야기겠지만, 후배들이 생긴다면 그들의 이야기도 잘 들어주고 잘 말해 줄 수 있는 사람, 선배, 개발자가 되고싶다.

짧게 내가 어떤 공부를 해야하는지 내가 어떤 사람, 개발자가 되고싶은지 끄적여봤다. 사실 너무 두서없어도 나도 다시 안읽을것 같다..ㅎㅎ 그래도 이렇게라도 한번 써보니까 좀 더 머릿속이 정리되는것 같아서 좋다. 길지 않은 시간 작성할 수 있는 글이지만 이런 시간조차 내지 않으려한 나를 반성하며 기회를 준 제로베이스에 감사하다!