RAG는 검색 단계와 생성 단계로 이루어져 있다. 즉 검색단계와 생성단계를 각각 테스트 하고, 검색 -> 생선 순이 효율적이다!

검색 단계

사용자의 질문과 관련된 문서를 DB에서 찾아오는 과정

목적 : 문서의 정확도 파라미터 : 임베딩 모델, 벡터 DB, 청킹 전략, 검색 전략이 있다.

• 생성 단계 : 찾은 문서를 참고해 LLM이 답변을 만든다.
  • 파라미터 : 프롬포트, LLM 모델이 있다.

랭스미스를 이용해서 테스트를 자동화하자!

검색 단계 : 임베딩 모델과 K 개수

청킹 전략

생성 단계 : 파라미터와 LLM 모델

최종 A/B 테스트 :

전체 결과

## 다음글은

RAG에서 사용할 벡터 DB를 만드는 단계

1. 원본 문서 준비 : RAG에 사용할 PDF·Markdown·텍스트 등 지식의 원본 자료를 수집하는 단계
2. 텍스트 정제 & chunking : 문서를 불필요한 요소를 제거한 뒤 의미 있는 작은 텍스트 조각으로 나누는 단계
3. embedding 생성 : 각 텍스트 chunk를 의미를 담은 숫자 벡터로 변환하는 단계
4. 벡터 DB 생성 : embedding을 저장하고 유사도 검색을 수행할 벡터 전용 데이터베이스를 만드는 단계
5. 벡터 + 메타데이터 저장 : embedding을 저장하고 유사도 검색을 수행할 벡터 전용 데이터베이스를 만드는 단계

다행히 우리 서비스는 기존에 사기 유형 파악과 가이드라인을 제공하기 위한 문서들을 가지고 있다. 다만, Q&A 자료나 용어 설명등 필요하다고 생각하는 몇가지의 문서를 추가로 준비했다.

따라서 다음 단계는 문서를 쪼개는 과정인 청킹이다. 청킹을 하기 전, 청킹을 해야하는 이유와 좋은 청킹의 방식을 알아보자.

오늘도 여러 기술 블로그를 읽었는데, 이렇게 좋은 자료를 만들어주시는 선배개발자 분들께 다시 한번 감사의 표시를...

Chunking 은 무엇이고 왜 필요할까

Chunking 이란 긴 문서를 작은 조각인 Chunk로 나누는 작업이다.
1번 과정에서 준비한 긴 문서를 그대로 임베딩 하지 않고, 500자나 1000 단위로 쪼갠 후 넣어야 한다.

왜 이런 과정이 필요할까?

Chunking이 필요한 이유

1️⃣ 질문에 대해 정확한 정보를 받기 위해서

• 내용증명 설명 문서에는 용어의 뜻, 목적, 과정, 주의사항, 대상 의 정보가 있습니다.
• 질문자 A는 내용증명의 목적을 질문했고, 내용 증명 설명을 받았습니다.

받은 내용 증명 문서에는 필요한 정보인 "목적" 이외에도 너무 많은 정보가 존재한다.

물론 문서를 너무 작게 자른다면, 문서의 맥락이 사라져 정보가 부족해질 수 있다.

2️⃣ LLM의 입력 한계가 존재한다.

• 위의 상황에서 내용증명문서를 그대로 넣었다고 가정해보자.

LLM은 문자 길이에 제한이 존재해서, 질문에 실패할 수도 있고 토큰 방식으로 비용이 청구되기 때문에 엄청난 돈을 내게될 수 있다. 💦 또한 문서에서 가장 중요한 정보를 찾기 어렵거나 중요도가 희석되거나, 일부 정보는 사라지게 되는 문제가 발생할 수 있다. 정확도와 비용측면에서 모두 안좋다.

즉, 모든 정보를 주는 것이 아니라 질문에 필요한 정확한 정보를 주는 것이 중요하고, 그러기 위해서는 적절한 단위로 문서를 자르는 과정이 필요하다

관련 용어 정리

• Precision (정밀도) : "내가 찾았다고 한 것 중 진짜 맞는 비율"
  • 정답으로 예측한 것 중 실제 정답 / 정답이라고 예측한 전체

• Recall (재현율) : "실제 정답 중 내가 찾아낸 비율"
  • 내가 찾아낸 정답 / 실제 정답 전체

좋은 Chunking 전략

Chunking 에도 여러 전략이 있지만, 3가지 정도를 소개 하려고 한다.

✔️ 고정 길이로 자르기

청킹은 보통 500자나 1000자가 권장된다. 긴 길이의 문서를 일정한 단위로 자르되, 문맥 정보를 유지하기 위해 청크끼리 오버랩을 줄 수 있다.

문서의 양이 방대하다면, 고정길이로 자르는 것이 유용할 수 있다. 또한 고정 단위로 자르는 방식이 무조건 성능 저하를 일으키는 것은 아니다. 여러 실험에서는 고정 길이 방식이 Recall 88.1~89.5 %을 유지하며 안정적인 성능을 보이기도 했다고 한다.

✔️ 의미 단위로 자르기

텍스트에는 복잡한 의미가 담겨있다. 내부에 표나 리스트가 있기도 하고 의미적인 구조가 존재하기도 한다. 이런 맥락과 텍스트 문서의 특징을 살려 하나의 문서 조각이 하나의 주제를 다를 수 있도록 짜르는 것이다.

✔️ AI 한테 시키기

또한 아예 문서의 핵심 주제를 AI가 의미적 유사성을 분석해 만든 단위로 문서를 쪼개는 방법도 있다. 문장을 쪼갠 후 임베딩을 하는 것이 아니라, 임베딩한 후 문장간의 유사도 분석을 통해 문서를 쪼개는 것이다.

➕ 맥락을 지키는 오버랩

오버랩(OverRap)은 이전 chunk의 끝부분을 다음 chunk 시작에 포함시키는 기술이다. 예를 들어서 설명하자면 첫 청크의 한두문장을 두번째 청크의 처음으로 추가하는 것이다. 이런 방식은 문서의 문맥을 살리게 되어 Recall을 높일 수 있다.

OverRap의 비율은 도메인에 따라 달라질 수 있으며 보통 10~20%를 권장한다.

• 법률/ 의료 : 30~50%
• 기술 문서/API : 20~30%
• 일반 문서/뉴스 : 10~20%
• Q&A : 5~10%

➕ 문서마다 다를 수 있으니 기본적으로 10%에서 시작해 조정해나가는 방법이 좋다고 한다.

*무조건 OverRap 비율을 높이는 것이 정확도 향상으로 이어지지는 않는다.! *

1. 오버랩률이 높아지면 그만큼 더 많은 저장소 공간을 필요로 하고, 인덱싱의 비용증가로 이어진다.

2. 또한 재현율을 높이려 한 선택이지만 정밀도(Precision)를 낮출 수 있다. 오버랩이 높으면 같은 내용이 여러 청크에 포함되며 상관없는 문서도 함께 검색 결과에 들어가게 된다. 이는 정밀도가 낮아지게 만든다. ( 정밀도 = 정답으로 예측한 것 중 실제 정답 / 정답이라고 예측한 전체)

청킹에는 어떤 문서를 넣어야하는가?

과연 청킹은 어떻게 하는걸까? 다행스럽게도 👩‍💻 개발자 도비가 손으로 일일히 하는 것은 아니다.

코드로 문서를 읽어오고, 선택한 전략에 맞춰서 적절한 문서 조각으로 나눈다. 이렇게 만들어진 문서 조각(청크)를 사람이 한번 더 검수하는 과정으로 이루어진다.

추천되는 문서 형태 : .md

이 문서를 읽고 자르는 주체는 컴퓨터이다. 컴퓨터 입장에서 해석하기 좋고, 불필요한 정보가 없는 문서 형태가 좋다.

word나 html은 컴퓨터가 이해하기에는 불필요한 정보가 많고, 일반 텍스트는 의미를 파악하기에는 정보가 부족하다. 마크다운은 표나 제목을 표시할 수 있어 의미 단위로 자르기에 간편하다.

우리 서비스는 어떤 전략으로 Chunking 을 할까?

전세 사기 피해 대처 가이드라인의 도메인 특성

• 법률 용어가 많다.
• 절차가 존재한다.
• 상황별 대처방법이 따로 존재한다. (절차가 여러 갈래가 된다.)
• 법률 조항은 중간에 짤리면 안된다.

문서의 내용이 어렵다고 판단했고, 용어 사전과 Q&A 자료를 함께 준비했다!

문서 구조 선택 : 마크다운

사실 프로젝트를 기획하면서 노션에 정리를 해와서 수고롭지 않게 정리할 수 있었다. 마크다운 문법을 활용해서 제목 (#),중제목(##), 소제목(###)으로 정리했다. 출처가 중요하다 판단해, 문서의 하단에는 출처링크들을 함께 정리했다.

지금 구조가 확정은 아니고, 성능을 테스트 하면서 마크다운의 구조를 바꾸거나, 의미별로 잘 잘라지(?)게 다듬을 것이다.

청킹 전략 : 의미 단위 vs 고정 길이

맥락을 보존할 수 있도록 의미 단위 (##)로 자르고, 자른 청크의 길이가 500이 넘어갈 때는 500자 단위로 자르기로 했다.

당연히 이 방식도 이것도 확정은 아니고, 성능 테스트를 보면서 확정을 하도록 하겠다!

Chunking 전략을 (대략적으로) 정하자

문제 상황 : 아예 다른 답변을 준다.

상황 : 임차권 등기 명령을 신청했으나, 전세 사기 피해자와 관련된 대답을 줌

** 문제점 파악** : 문서의 핵심 주제와 작은 주제인 #, ## 옆에 있던 텍스트들이 빠지면서 검색 성능이 떨어지고 있었음

📑 계약 만료일이 지났음에도 집주인이 ~~ 

해결 : 우선 코드를 변경해서 헤더옆의 텍스트가 들어갈 수 있게 수정했다.

** 결과**

📑 임차권등기명령 신청 임차권등기명령을 신청해야 하는 상황 ### 1. 임대차 기간 종료 후 보증금 미반환\n계약 만료

여러 자료를 찾아보면서 LLM 성능은 단계별로 조정하기 어렵다는 것을 알았다. 점진적으로 조절을 해야하긴하지만, 일단 대략적으로 정한 청킹 전략을 소개하겠다

의미 기반 청킹 & 길이 기준청킹 전력

1. #, ## 기반으로 나누기 제목과, 대분류 텍스트는 제거하지 않고 content에 저장

2. 길이 기반으로 나누기 1번의 결과가 기준(1000)자를 넘을 경우에는 텍스트 내부에서 큰 의미 단위로 자름: ( \n\n (문단) → \n (줄바꿈) → . (문장) → (단어) :

3. 청크를 관라히기 위한 chunk_id 이후 테스트용 데이터 셋을 만들거나 관리에 사용할 chunk_id

   chunk_id = 파일명_헤더인덱스_서브인덱스(번호)

코드 전문

# chunking.py
# chunking.py
from langchain_text_splitters import (
    MarkdownHeaderTextSplitter,
    RecursiveCharacterTextSplitter
)

import os
import json
from pathlib import Path

global i


class MarkdownChunker:
    def __init__(self, chunk_size=800, chunk_overlap=80):
        """
        Args:
            chunk_size: 한 청크의 최대 크기 (글자 수)
            chunk_overlap: 청크 간 오버랩 크기 (10% = 80자)
        """
        self.chunk_size = chunk_size
        self.chunk_overlap = chunk_overlap

        # 헤더 기반 분리기
        self.headers_to_split_on = [
            ("#", "제목"),
            ("##", "대분류"),
        ]

        self.markdown_splitter = MarkdownHeaderTextSplitter(
            headers_to_split_on=self.headers_to_split_on
        )

        # 크기 조정용 분리기
        self.text_splitter = RecursiveCharacterTextSplitter(
            chunk_size=self.chunk_size,
            chunk_overlap=self.chunk_overlap,
            separators=["\n\n", "\n", ".", "!", "?", " ", ""],
            length_function=len,
        )

    # 제목과 부제목은 제외
    def chunk_file_1(self, file_path):
        """단일 마크다운 파일을 청킹"""
        print(f"처리 중: {file_path}")

        file_name = os.path.basename(file_path)

        with open(file_path, 'r', encoding='utf-8') as f:
            content = f.read()

        # 1단계: 헤더 단위로 먼저 분리
        try:
            md_chunks = self.markdown_splitter.split_text(content)
        except Exception as e:
            print(f"헤더 분리 실패, 텍스트 분리로 전환: {e}")
            md_chunks = [{"page_content": content, "metadata": {}}]

        # 2단계: 크기 조정
        final_chunks = []
        for i, chunk in enumerate(md_chunks):
            chunk_content = chunk.page_content if hasattr(chunk, 'page_content') else chunk
            chunk_metadata = chunk.metadata if hasattr(chunk, 'metadata') else {}

            base_id = f"{file_name}_{i}"

            # 청크가 너무 크면 재분할
            if len(chunk_content) > self.chunk_size:
                sub_chunks = self.text_splitter.split_text(chunk_content)
                for j, sub in enumerate(sub_chunks):
                    final_chunks.append({
                        'content': sub,
                        'metadata': {
                            'source': file_name,
                            'chunk_id': f"{base_id}_{j}",
                            **chunk_metadata
                        }
                    })
            else:
                final_chunks.append({
                    'content': chunk_content,
                    'metadata': {
                        'source': file_name,
                        'chunk_id': base_id,
                        **chunk_metadata
                    }
                })

        return final_chunks

    def chunk_file(self, file_path):
        """단일 마크다운 파일을 청킹하며 고유한 ID 부여"""
        print(f"처리 중: {file_path}")

        # 파일명을 ID의 일부로 사용하기 위해 추출
        file_name = os.path.basename(file_path)

        with open(file_path, 'r', encoding='utf-8') as f:
            content = f.read()

        try:
            md_chunks = self.markdown_splitter.split_text(content)
        except Exception as e:
            print(f"헤더 분리 실패: {e}")
            md_chunks = [{"page_content": content, "metadata": {}}]

        final_chunks = []
        for i, chunk in enumerate(md_chunks):
            chunk_content = chunk.page_content if hasattr(chunk, 'page_content') else chunk
            chunk_metadata = chunk.metadata if hasattr(chunk, 'metadata') else {}

            header_prefix = ""
            title = chunk_metadata.get('제목', '')
            category = chunk_metadata.get('대분류', '')

            if title or category:
                header_prefix = f"{title} {category} ".strip() + " "

            processed_content = header_prefix + chunk_content

            # 고유 ID 생성을 위한 베이스 ID (파일명 + 헤더순서)
            base_id = f"{file_name}_{i}"
            # base_id = f"{i}"

            if len(processed_content) > self.chunk_size:
                sub_chunks = self.text_splitter.split_text(processed_content)
                for j, sub in enumerate(sub_chunks):
                    final_chunks.append({
                        'content': sub,
                        'metadata': {
                            'source': file_name,
                            'chunk_id': f"{base_id}_{j}",  # 예: document.md_0_1
                            **chunk_metadata
                        }
                    })
            else:
                final_chunks.append({
                    'content': processed_content,
                    'metadata': {
                        'source': file_name,
                        'chunk_id': base_id,  # 예: document.md_0
                        **chunk_metadata
                    }
                })

        return final_chunks




    def chunk_directory(self, directory_path="문서"):
        """디렉토리 내 모든 .md 파일 청킹"""
        all_chunks = []

        # 모든 .md 파일 찾기
        base_path = Path(__file__).parent / directory_path
        print(base_path)

        if not base_path.exists():
            print(f"오류: {base_path} 경로를 찾을 수 없습니다.")
            return []

        md_files = list(base_path.glob("*.md"))

        print(f"\n총 {len(md_files)}개의 마크다운 파일을 찾았습니다.")

        for file_path in md_files:
            chunks = self.chunk_file(file_path)
            all_chunks.extend(chunks)
            print(f"  → {len(chunks)}개 청크 생성")

        print(f"\n총 {len(all_chunks)}개의 청크가 생성되었습니다.")
        return all_chunks

    def save_chunks(self, chunks, output_file="json/chunks.json"):
        """청크를 JSON 파일로 저장"""
        with open(output_file, 'w', encoding='utf-8') as f:
            json.dump(chunks, f, ensure_ascii=False, indent=2)
        print(f"\n청크가 {output_file}에 저장되었습니다.")

    def print_chunk_stats(self, chunks):
        """청크 통계 출력"""
        if not chunks:
            return

        chunk_lengths = [len(chunk['content']) for chunk in chunks]
        print("\n=== 청킹 통계 ===")
        print(f"총 청크 수: {len(chunks)}")
        print(f"평균 길이: {sum(chunk_lengths) / len(chunk_lengths):.0f}자")
        print(f"최소 길이: {min(chunk_lengths)}자")
        print(f"최대 길이: {max(chunk_lengths)}자")

        # 파일별 통계
        from collections import Counter
        sources = Counter([chunk['metadata']['source'] for chunk in chunks])
        print("\n파일별 청크 수:")
        for source, count in sources.items():
            print(f"  - {source}: {count}개")


def main():
    # 청커 초기화
    chunker = MarkdownChunker(
        chunk_size=1000,  # 최대 800자
        chunk_overlap=80  # 10% 오버랩
    )

    # 현재 디렉토리의 모든 .md 파일 청킹
    chunks = chunker.chunk_directory()

    # 통계 출력
    chunker.print_chunk_stats(chunks)

    # JSON 파일로 저장
    chunker.save_chunks(chunks, "json/chunks.json")

    # 첫 3개 청크 미리보기
    print("\n=== 첫 3개 청크 미리보기 ===")
    for i, chunk in enumerate(chunks[:3]):
        print(f"\n[청크 {i + 1}]")
        print(f"파일: {chunk['metadata']['source']}")
        print(f"메타데이터: {chunk['metadata']}")
        print(f"내용 (처음 200자):\n{chunk['content'][:200]}...")


if __name__ == "__main__":
    main()

다음 글

진짜로 성능 테스트를 다루자 !

유용한 글

RAG 시스템을 위한 문서 전처리 가이드: AI가 이해하기 쉬운 형태로 만들기 LLM 서비스 개발의 핵심 기술: RAG, VectorDB, LangChain 개념 정리 [Tech Series] kt cloud AI 검색 증강 생성(RAG) #3 : 청킹(Chunking) 전략과 최적화 청킹과 인덱싱(Chunking & Indexing)-셀렉트스타

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

예제 입력

3
1 2 3 --> 인오더(중위순회) : 왼-중-오
1 3 2 --> 포스트 오더(후위순회): 왼-오-중

예제 출력

2 1 3 -> 프리오더(전위순회) :중-왼-오

내 풀이

인오더랑 프리오더 뭔지 몰랐음 ㅋ

• Inorder (중위 순회) : left Node -> root Node -> right Node
• preorder (전위 순회) : root Node -> left Node -> right Node
• postorder (후위 순회) : left Node -> right Node -> root Node

아이디어

일단 n개 노드를 가지는 이진 트리의 구조를 생각해보자

          0              
    1           2      
  3   4      5         
인오더 : 3 1 4 0 5 2  
포스트오더 : 3 4 1 5 2 0 

-> 먼저 자릿수를 계산해봐야함 [-,-,-,-,-,-] 5개일때, 처음 들어갈 위치 : ? ? ? ? ? ? ?

자릿수를 계산하는 위치 : 트리의 전체 루트를 알아야하기 때문이다.

→ 트리의 전체 루트는 포스트 오더의 마지막 부분

😦😦😦😦😦

왜 스스로 생각하지 못했는가.

• 자릿수를 계산해야한다는 발상은 좋았지만 해당 아이디어가 해결해야하는 핵심 목적을 생각하지 못했고, 인오더의 케이스에만 집중해서, 포스트 오더가 가지는 맨마지막에 전체 루트가 나온다는 특징은 발견하지 못했음

인오더 : 3 1 4 0 5 2  :  왼-중-오
포스트오더 : 3 4 1 5 2 0 : 왼-오-중

트리의 전체 루트 : 0 트리의 왼쪽 : 인오더의 0 기준 왼쪽, 트리의 오른쪽 : 인오더의 0 기준 오른쪽

그러면 포스트 오더의 맨 끝을 보고, 인오더에서 왼쪽에 존재하는 노드 개수를 센 다음에, 다시 해당 노드 개수만큼 포스트오더에서 자른 후, 왼쪽 노드의 루트를 확인하는 식으로 하면 안되나?

          0              
    1           2      
  3    4      5   6
7  8 
          0 1 2 3 4 5 6 7 8
인오더 :    7 3 8 1 4 0 **5 2 6** : 왼-중-오
포스트오더 : 7 8 3 4 1 **5 6 2** 0 : 왼-오-중

find(루트인덱스(1) ,인오더시작인덱스(0) , 인오더끝인덱스(4) , 포스트시작인덱스(0), 포스트끝인덱스(4)) :
    루트 = 포스트[포스트끝인덱스] = 1 
    프리[루트인덱스] = 루트 

    인오더왼쪽부분시작 =  인오더시작인덱스 
    인오더왼쪽부분끝 =  인오더인덱스[루트] - 1 

    포스트오더왼쪽부분시작 =  포스트시작인덱스 
    포스트오더왼쪽부분끝 =  포스트시작인덱스 + (인오더왼쪽부분끝 - 인오더왼쪽부분시작) 

    if (왼쪽<=오른쪽) -> find()

    인오른쪽부분시작 = 인오더인덱스[루트] + 1 
    인오른쪽부분끝 = 인오더 끝 인덱스 

    포스트오른쪽부분시작 = 포스트오더왼쪽부분끝 + 1 
    포스트오른쪽부분끝 =  포스트끝인덱스 - 1 

    if (왼쪽<=오른쪽) -> find()

find(루트인덱스(1) ,인오더시작인덱스(6) , 인오더끝인덱스(8) , 포스트시작인덱스(5), 포스트끝인덱스(7)) :
    루트 = 포스트[포스트끝인덱스]=2 
    프리[루트인덱스] = 루트 

    인오더왼쪽부분시작 =  인오더시작인덱스 = 6 
    인오더왼쪽부분끝 =  인오더인덱스[루트] - 1 = 7 - 6

    포스트오더왼쪽부분시작 =  포스트시작인덱스 = 5     
    포스트오더왼쪽부분끝 =  포스트시작인덱스 + (인오더왼쪽부분끝 - 인오더왼쪽부분시작) = 5

    if (왼쪽<=오른쪽) -> find()

    인오른쪽부분시작 = 인오더인덱스[루트] + 1 = 8    
    인오른쪽부분끝 = 인오더 끝 인덱스 = 8

    포스트오른쪽부분시작 = 포스트오더왼쪽부분끝 + 1 = 6 
    포스트오른쪽부분끝 =  포스트끝인덱스 - 1 = 6

    if (왼쪽<=오른쪽) -> find()

실패 : 완전 이진 트리가 아니었다. ;;

이진트리라고 해서 차곡 차곡 쌓인 트리라고 생각했는데 아니였다.

그래서 바로 문자열에 넣었디. (재귀 순서가 프리 오더랑 동일함

성공 코드

public class BOJ2263트리의순회 {
    static StringBuilder sb = new StringBuilder();
    static int[] in_order_idx;
    static int[] post_order;

    static class Order {
        int start;
        int end;

        Order(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    static void find(int root_idx, Order in, Order post) {
        int root = post_order[post.end];
        sb.append(root).append(" ");

        Order left_in = new Order(
            in.start,
            in_order_idx[root] - 1
        );

        Order left_post = new Order(
            post.start,
            post.start + (left_in.end - left_in.start)
        );

        if (left_in.end >= left_in.start) {
            find(root_idx * 2 + 1, left_in, left_post);
        }

        Order right_in = new Order(
            in_order_idx[root] + 1,
            in.end
        );

        Order right_post = new Order(
            left_post.end + 1,
            post.end - 1
        );

        if (right_in.end >= right_in.start) {
            find(root_idx * 2 + 2, right_in, right_post);
        }
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        in_order_idx = new int[n + 1];
        post_order = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            int v = Integer.parseInt(st.nextToken());
            in_order_idx[v] = i;
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int v = Integer.parseInt(st.nextToken());
            post_order[i] = v;
        }

        Order in = new Order(0, n - 1);

        Order post = new Order(0, n - 1);

        if (in.end >= in.start) {
            find(0, in, post);
        }

        System.out.print(sb);
    }
}

기억하고 싶은 것

📌 못푸는 문제는 없다 : 규칙이 무조건 존재한다.

🤔 왜 하필, 인오더-포스트 오더를 줬을까?

🤔 왜 하필 프리오더를 출력할까?

→ 이조합으로 해야 문제를 풀 수 있군, 즉 각 순회방식의 특징을 이해해야한다.

📌 단서인 것 같기는 한데, 여기서 더 발전하기 어려울때는

내가 이 단서에서 얻고자하는 것, 내가 지금 필요로 하는 것이 무엇인지 더 살펴보자 !

괜히 직관이 발동한게 아니다 !!

오늘 했어야하는 좋은 사고 흐름

→ 오늘은 기준을 찾으려고 했다.

🤔 인오더와 포스트 오더 중 기준을 명확하게 보여주는 것이 있나?

🤔 포스트 오더의 끝부분은 항상 전체 트리의 루트다!

🤔 인오더에서 전체 트리 루트의 노드를 알면 무엇을 알 수 있을까?

🤔 인오더는 루트 노드 기준으로 왼쪽/오른쪽이 나뉜다.

→ 완전 이진이 아니네?

🤔 하지만 무조건 풀린다. (안풀리는 문제는 없다)

→ 만약 내 아이디어로 절대 풀 수 없다면 다른 아이디어가 존재한다는 것!

🤔 이 재귀 탐색 순서와 프리 오더의 상관관계는?

전세 사기 대처 플랫폼에 LLM 기반의 상담봇을 도입하려고 한다. 여러 기술이 있는데 그 중 RAG를 결합해 LLM을 사용하려고 한다.

여러 기술 중 왜 LLM + RAG를 선택했는지, 또 다른 기술에는 무엇이 있는지를 설명하고 정말 간단한 예제코드로 작은 RAG 기술을 결합한 LLM 시스템을 동작 시켜보고 이해해보자!

추천하는 사람들

👩🏻‍🎓 : 바로 LLM과 RAG를 사용해보고 싶은 개발자 👩🏻‍🎓 : LLM과 RAG을 이해하고 싶은 학생 개발자

전세 사기 대처 플랫폼에 상담봇이 필요하다!

전세 사기 대처 플랫폼, 부메랑

부메랑은 전세사기 피해자들을 위한 전세사기 대처 웹 플랫폼입니다.

전세사기 피해자들이 환급 과정에서 겪는 복잡한 절차와 정보 부족의 어려움을 해결하기 위해 개발했습니다. 피해자들은 환급을 위해 전세사기 유형을 파악하고, 법적 용어를 이해하는 등 추가적인 피로를 겪습니다. 따라서 피해자들이 환급 과정에만 집중할 수 있도록, 유형 파악부터 환급까지 필요한 기능을 제공하고자 노력했습니다. 또한, 채팅과 상담, 서류 자동 완성 등 피해자들에게 실질적인 도움이 되는 기능들을 지속적으로 고민하며 발전시켰습니다.

새로운 상담 기능의 필요성

현재 상담 기능은 전문 변호사의 유료 상담만을 지원하고 있다. 그러다보니 다음과 같은 두가지 문제가 발생했다.

1. 금전적 어려움을 겪고 있는 유저에게 추가적인 비용 부담, 운영자는 변호사를 모셔오기(?)위한 추가적인 비용이 발생하고 있다.
2. 또 변호사가 없다면, 상담 기능 자체가 미운영되는 문제가 발생! 💦

전세사기 피해자들을 돕기 위한 프로젝트의 목적을 달성하지 못했다.

따라서 무료이면서 정확한 정보를 바로 제공할 수 있는 새로운 상담봇이 필요하다.

새로운 상담봇의 요구 사항 정리

1. 정확한 정보 ⭐️⭐️
2. 플랫폼 내에서 검색을 끝낼 수 있도록 완전한 정보 (=외부 검색이 필요없는)
3. 무료일 것 (불가능하다면 비용 최소화)

상담봇을 어떻게 구현할지 고민하자

그 전에!! 기본 지식을 점검하자

헷갈리는 용어들을 가볍게 정리하고 들어가봅시다~👍

생성형 AI

생성형 AI은 대화, 이야기, 이미지, 동영상, 음악 등 새로운 콘텐츠와 아이디어를 만들 수 있는 AI의 일종 인간 언어, 프로그래밍 언어, 예술, 화학, 생물학 또는 어떤 복잡한 주제라도 학습할 수 있습니다. 학습한 내용을 재 사용하여 새로운 문제를 해결할 수 있다.

머신 러닝

머신러닝은 모델을 학습하고, 예측/분류의 작업을 수행하는 기술. 딥러닝은 머신러닝 중에 인공 신경망을 활용하는 기술로, 더욱 복잡한 데이터 구조(비선형 데이터, 자연어, 이미지)를 학습할 수 있다.

LLM (대규모 언어 모델)

LLM = Large Language Model

LLM(대규모 언어 모델)은 방대한 양의 데이터로 사전 학습된 초대형 딥 러닝 모델이다.
즉, 딥 러닝중에서도 특히 아주아주 큰 텍스트 데이터를 학습한 아주아주 큰 모델을 말한다.

흔히 쓰는 GPT, Claude 모두 LLM 이다. 이러한 LLM은 특정 도메인에 한정되지 않고 다양한 분야의 데이터를 학습한 후 사용자의 질문에 답변한다.

기존 기계학습은 언어 데이터를 숫자 표 형식으로 표현했다. 그러다보니 단어의 유의성과 같은 관계를 인식할 수 없었다. LLM은 워드 임베딩이라는 다차원 벡터를 사용한다. 이 다차원 벡터는 단어들끼리의 관계(유의성, 반의성)를 표현하고 이를 통해언어 데이터를 더 잘 학습하고, 잘 다룰 수 있게 된 것이다.

따봉 도치야 고마워 ~ 

LLM를 사용하는 상담 봇에도 다양한 구현 방법이 있다!

LLM 모델을 직접 만들기

위에서 말했듯이 엄청난 학습데이터와 엄청난 규모의 모델을 설계해야한다.

• 수백GB~수TB 규모의 학습데이터가 필요
• 모델을 운영하기 위한 수천 개의 GPU, 수억원 이상의 비용이 필요
• 또한 이런 LLM 구조를 설계하고 학습, 운영하기 위한 지식이 필요

즉, OpenAI, Anthropic, Google 같은 대기업이 할 수 있는 규모로 나같은 일반 개발자에게는 비현실적인 방식이다.

LLM을 그대로 사용하기

그렇다면 OpenAI나 클로드를 그대로 사용하는 것은 어떨까? LLM은 유용하지만 여러 약점을 가지고 있다.

• 할루시네이션 (Hallucination) : 거짓인 정보를 진실인 것처럼 제공, 사용자 입장에서는 할루네이션인지 아닌지 판단하기 어려움
• 출처 정보 부재 : 답변의 근거나 출처를 제공하지 않음, 따라서 답변의 신뢰성이 높지 않고 재확인이 어려움

다시 돌아가서 전세 사기 대처 플랫폼에 필요한 새로운 상담봇의 요구 사항을 살펴보자

1. 정확한 정보 ⭐️⭐️

전세 사기라는 도메인은 정확성이 아주 중요하다. 만약 두 가지 문제점으로 인해 사용자가 거짓정보를 얻게되거나, 서비스가 제공한 정보를 교차 검증해야한다면 프로젝트 목표인 전세 사기 피해자들이 겪는 복잡한 절차, 정보 부족의 문제점을 해결할 수 없게된다.

따라서 정확한 정보만을 제공할 수 있는 다른 방법이 필요하다.

LLM에 파인 튜닝을 적용하기

파인 튜닝이란 LLM에 원하는 데이터를 추가로 학습 시켜 모델을 미세 조정하는 기술이다. 범용 모델을 특정 분야에 특화된 전문 모델로 변화 시키는 것이다.

학습을 위한 데이터가 필요하며, 시간이 지나며 최신 정보를 반영하기 위해 주기적으로 데이터를 재 학습시켜야한다. 또한 데이터 학습에는 전문 지식이 필요하다! ⭐️⭐️

LLM에 질문하기 전 RAG을 활용하기

RAG(Retrieval-Augmented Generation)는 질문을 벡터로 변환해서 벡터 데이터베이스에서 의미적으로 유사한 문서를 검색한 후, LLM이 답변 생성에 해당 문서를 참고하도록 하는 기술이다.

즉, GPT에게 "신규 입사가 언제야?" 를 물어보기전에 질문하기전 사내 일정 데이터 저장소(벡터 데이터베이스) 에서 "신입 채용 일정", "경력 채용 일정"의 문서를 찾은 후 , GPT가 해당 문서를 참고해서 출력을 만들 수 있도록 하는 것이다.

이런 방식은 LLM를 재학습시키는 과정이 생략되어 비용이 적고, 신뢰할 수 있는 데이터의 관리가 수월해진다. 재학습보다 데이터의 최신성을 유지하기 편하다.

• 문서 몇십~몇백 개면 시작 가능
• 재학습 불필요, 문서만 추가하면 즉시 반영

(출처 : https://aws.amazon.com/ko/what-is/retrieval-augmented-generation/)

이런 RAG 기술 활용이 전세 사기 대처 플랫폼에 적절한 이유는 무엇일까?

1. 할루시네이션 방지에 효과적이다. RAG는 모든 답변을 근거 있게 생성하기 때문에 할루시네이션 방지에 더 효과적이다. 또한 정보 데이터를 제어할 수 있기 때문에 잘못된 정보를 수정하기 수월하다.
2. 정보 출처 관리에 유리하다. 검색된 문서를 함께 보여줘서 출처를 사용자에게 보여줄 수 있다.

프롬포트와 RAG를 사용하는 것은 무엇이 다를까?

• 프롬포트는 LLM에게 질문할 때 지시사항이나 맥락을 함께 전달하는 것이다. 사용자의 질문에 따라 동적으로 주어지는 것이 아니라, 관리자가 기존에 텍스트로 저장하는 것이다. 답변의 맥락을 저장할 수는 있지만, 내부적으로 참고하는 데이터를 설정할 수는 없기 때문에 할루시네이션을 해결할 수 없다.

• RAG는 사용자의 질문에 따라 가장 관련성이 높은 문서(신뢰할 수 있는)를 검색해서 LLM에 함께 저장하는 것이다. 참고하는 문서를 직접 관리하기 때문에 출처를 명확하게 관리하고, 할루시네이션을 줄일 수 있다. LLM이 학습하지 않은 정보(비공개, 최신데이터)에 접근할 수 있도록한다.

또 다른 기술 FAQ 규칙 기반 챗봇

AI기술을 적용하지 않은 시나리오형 FAQ 챗봇으로만 한정지어 설명하겠습니다.

다들 써보셨던 자동응답형을 떠올리시면 좋을 것 같다!. FAQ, 즉 유저가 자주 물어보는 질문들에 대한 답변을 미리 만들어놓고 채팅 식으로 답변을 주는 방식이다. 만약 물어보는 질문이 패턴화가 되어있고, 단순하다면 비용을 고려한 FAQ 규칙 기반 챗봇도 적절할 것이다.

그러나 전세 사기라는 도메인은 개인마다 다른 조건과 상황에 따른 다양한 질문이 가능하고 "키워드A와 키워드B의 차이점" 등 과 같은 다양한 조합이 가능하다.

따라서 FQA 규칙 기반 챗봇은 좋은 선택이 아니다. LLM을 사용한다면 유저의 질문에 대한 자연스러운 답변을 생성해 대응할 수 있다.

실습으로 LLM과 RAG 이해하기

개념 설명이 너무 길어졌다. 💦  간단한 예제로 직접 RAG를 활용하는 LLM 시스템의 구조를 학습하자 !! 

역시 백문이 불여일타. 직접 하면 일단 이해된다.!

최대한 간단한 코드를 가져왔으니 직접 실습해보자

1단계 : 필요한 라이브러리 다운로드 받기

아래 명령어를 터미널에 입력하자. 필요한 파이썬 라이브러리를 다운로드 받는 명령어다.

pip install openai
pip install chromadb
pip install langchain
pip install langchain-openai
pip install langchain-community

• openai : OpenAI의 공식 Python 라이브러리, GPT와 임베딩 API 호출에 사용
• chromadb : 벡터 데이터베이스, 임베딩 벡터 저장 및 유사도 검색에 사용
• langchain : LLM 애플리케이션 개발 프레임워크, RAG와 챗봇 구축의 핵심 도구
• langchain-openai : LangChain에서 OpenAI를 사용하기 위한 통합 패키지
• langchain-community: LangChain의 확장 모듈, 다양한 벡터 DB와 문서 로더 제공

2단계 : Open API 키 발급받기

LLM은 OpeAPI를 이용하도록 하자. 당연히 무료로 사용할 수 있도록 API를 열어놓지 않았다. (까비!)

키를 발급받고, 비용을 내야한다.

👉 Open API 키 발급 받으러 가기

크레딧 충전하기

• ⚙️ 프로필 옆 톱니 버튼 > Organization > Billing 에서 충전하자.

예전에는 5달러 정도 기본으로 줬던 것 같은데 변경되었는지 5달러를 충전하라고 한다. 중간에 Yes~~ 는 자동 충전설정이 비활성화를 하자⭐️

참고로 5.5달러는 8천원이다 짱비쌈!

secret key 발급받기

• 동일하게 ⚙️ 프로필 옆 톱니 버튼 > Organization > API Keys에서 키를 발급받자.

이름은 원하는 데로, 프로젝트는 일단 디폴트로 두면 된다. creat를 하면 복사할 수 있게 문자열로 된 키가 나오는데 이후에는 다시 알려주지 않으므로 소중하게 저장하다. (물론 이후에 또 재발급하면 된다.) 블로그나 깃허브에 올리면 비용 청구될 수도 있다.

3단계 : 일단 해보기

여기까지 했다면, 코드에 필요한 라이브러이와 키는 모두 준비됐다. 사실 하나 더 필요하다. 벡터 데이터 베이스! 그건 코드 내부에 있다.

from openai import OpenAI
import chromadb

# OpenAI 클라이언트 설정
client = OpenAI(api_key="아까 발급맏은 키!!")

# Chroma 벡터 DB 설정
chroma_client = chromadb.Client()
collection = chroma_client.get_or_create_collection(name="jeonse_docs")

# 임베딩 생성 함수
def get_embedding(text):
    response = client.embeddings.create(
        input=text,
        model="text-embedding-3-small"
    )
    return response.data[0].embedding

# 1. 전세 관련 문서들 (지식 베이스)
documents = [
    "전세 계약 시 확정일자를 반드시 받아야 합니다. 확정일자는 전세금 반환 우선순위를 정하는 중요한 기준입니다.",
    "임대인의 재산 상태를 등기부등본으로 확인하세요. 근저당, 가압류 등이 있는지 체크해야 합니다.",
    "전세 사기 피해를 입었다면 즉시 경찰에 신고하고, 대한법률구조공단에서 무료 법률 상담을 받을 수 있습니다.",
    "전세보증보험에 가입하면 임대인이 보증금을 돌려주지 못할 때 보험사가 대신 지급합니다.",
    "전입신고는 계약 당일에 하는 것이 좋습니다. 전입신고를 해야 대항력이 생깁니다."
]

# 2. 문서를 벡터 DB에 저장
print("문서를 벡터 DB에 저장 중...")
for i, doc in enumerate(documents):
    embedding = get_embedding(doc)
    collection.add(
        documents=[doc],
        embeddings=[embedding],
        ids=[f"doc_{i}"]
    )
print("저장 완료!\n")

# 3. 사용자 질문
user_question = "전세 계약할 때 뭘 확인해야 하나요?"
print(f"질문: {user_question}\n")

# 4. 질문과 유사한 문서 검색
print("관련 문서 검색 중...")
question_embedding = get_embedding(user_question)
search_results = collection.query(
    query_embeddings=[question_embedding],
    n_results=3
)

# 5. 검색된 문서 출력
print("검색된 관련 문서:")
for i, doc in enumerate(search_results['documents'][0]):
    print(f"{i+1}. {doc}\n")

# 6. 검색된 문서 + 질문을 LLM에게 전달해서 답변 생성
context = "\n".join(search_results['documents'][0])
prompt = \
    f"""
    다음 정보를 바탕으로 질문에 답변해주세요.

        정보:
        {context}

        질문: {user_question}

        답변:
    """

print("LLM이 답변 생성 중...\n")
response = client.chat.completions.create(
    model="gpt-3.5-turbo",
    messages=[
        {"role": "user", "content": prompt}
    ]
)

print("=== 최종 답변 ===")
print(response.choices[0].message.content)

코드를 실행해보면

전세 계약을 할 때 확정일자를 꼭 확인해야 합니다. 확정일자는 전세금 반환 우선순위를 정하는 중요한 기준이기 때문입니다. 
또한, 전세보증보험에 가입하는 것이 좋습니다. 
이를 통해 임대인이 보증금을 돌려주지 못할 때 보험사가 대신 지급해줍니다. 
마지막으로, 전입신고는 계약 당일에 하는 것이 좋습니다. 이를 통해 대항력을 가질 수 있습니다.

라는 답변을 얻을 수 있다. !

다음 글에서는 진짜 만들자 !

위 글을 충분히 읽고, 코드의 주석을 읽는다면 대략적인 동작을 이해할 수 있을 것이라 생각한다! 오늘 글은 LLM와 RAG이 생소한 분들(나)를 위한 글이었다.

체험은 이걸로 충분! 이제는 실전! 다음 글부터는 데이터를 벡터 데이터로 만들고, 벡터 데이터 베이스로.. 등등등 진짜로 사용할 수 있도록 RAG와 LLM을 만져보겠다.!!

참고글 🙇‍♀️

좋은 자료를 제공해주시는 모든 분들과 여러 기업에 항상 감사합니다 ... 🙏

홍영호 AI 연구원님의 생성형 AI, 머신러닝, 딥러닝, LLM 글 aws 의 생성형 AI google의 머신러닝 글 aws의 대규모 언어모델(LLM) RAG vs. 파인튜닝 :: 기업용 맞춤 LLM을 위한 선택 가이드 사람인의 RAG 기술

궁금해서 _ "크림 파스타와 토마토 파스타의 차이가 뭐야?"_라는 질문으로 바꿔봤다.

죄송합니다, 질문과 관련된 정보가 아닙니다. 다시 한 번 질문을 해주시면 정확한 답변을 드리겠습니다. 감사합니다.

라는 답변을 얻었다. 내겐 너무 차가운 그녀

어제 시간 복잡도를 계산하지 않아서 시간을 날린 경험을 토대로 오늘은 먼저 가능한지부터 판별했다. 역시나 단순 그래프 탐색으로는 불가능하기 때문에 더 찾아봤고, “서로소 알고리즘” 이라는 것을 알게됐다.

서로소 알고리즘이란

서로소 : 공통 원소가 없는 두 집합

👉 두개의 집합이 공통 원소가 없는 서로소 집합인지를 판별하기 위한 알고리즘이다.

상황

여러개의 집합을 합치는 과정에서, 특정 원소나 집합이 두개가 같은 집합에 속해있는지를 확인해야한다. 즉 서로소 집합이 아닌 것을 확인해야한다. 그래프를 만든 후, 모든 경로를 확인하는 것도 가능하겠지만, 시간 복잡도가 높다. 그럴때 쓰는 것이 서로소 알고리즘

원리

각 집합의 대표 노드를 정한 후 이름표를 붙이듯, 각 원소마다 대표 노드를 저장한다. 어떤 원소 두 개의 대표 노드가 같다면 동일한 집합에 속해 있다. 반대로 다르다면 서로 다른 집합에 속한 서로소 집합인 것이다.

이러기 위해서는 대표노드를 저장하는 규칙이 항상 동일 (대개 더 작은 숫자로)해야한다.

풀이

union 연산

• 서로 연결된 두 노드 A, B의 최종 대표 노드를 확인한다. find 연산 활용 (A’, B’)
  ⭐️ 재귀적으로 찾은 대표 노드를 사용해야함에 유의
• 둘 중 더 작은 대표 노드를 대표 노드로 정한다. (A’라고 가정)
• B’의 대표노드를 A’로 한다.
  ⭐️ B의 대표 노드를 바꾸는 것이 아니라 B’의 대표 노드를 바꾸는 것임에 유의

find 연산 ;

최종 대표 노드( 대표노드와 자신 노드값이 동일함)를 찾을때까지 순회한다. 그러나 최악의 경우 선형 트리가 생성될 수 있다.

개선된 find 연산 :

트리의 구조를 평평하게, 즉 방문한 모든 노드들에 곧바로 최종 대표 노드를 가리키도록 설정한다 (depth를 1로 줄이는 것)

• frind(노드): 어떤 노드의 대표노드를 찾으려고 할때,
  • 해당 노드의 대표 노드가 최종 대표 노드인 경우 :
    • 최종 대표 노드 반환

- 아닌 경우 :
    - _frind(해당 노드의 대표 노드)_ … 1 

   - 현재 노드의 대표 노드를 1번의 반환값 (**최종 대표 노드 반환**) 으로 업데이트    
    → 트리의 뎁스가 줄어든다.

1717 집합의 표현

문제

초기에 $n+1$개의 집합 ${0}, {1}, {2}, … , {n}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

예제 입력

7 8 : n, m -> 집합의 개수, 연산 수 
    집합 : 0 1 2 3 4 5 6 7 

0 1 3 : 합치기, 0, 1-3,2,4,5,6,7
1 1 7 : 같이 있는지? no
0 7 6 : 합치기 : 0, 1-3,2,4,5,6-7
1 7 1 : 같이 있는지? no
0 3 7 : 합치기 : 0,1-3-7-6, 2, 4, 5
0 4 2 : 합치기 : 0,1-3-7-6, 4-2, 5
0 1 1 : 합치기 : 0,1-3-7-6, 4-2, 5
1 1 1 : 같이 있는지? yes

예제 출력

NO
NO
YES

그래프 탐색으로 안되는 이유 : 시간 복잡도

그래프 탐색에 걸리는 시간 복잡도 : O(V + E)

• V = 정점(vertex)의 개수
• E = 간선(edge)의 개수

→ 만약 M 모두 확인하는 연산이라면? O(M(N) ⇒ 10^11 : 시간 초과

→ 만약 반반이라면? O(M/2(N+M/2)) ⇒ 50,000 * ( 1050,000) = 10^10 : 시간 초과)

자바 시간 복잡도

서로소 집합 알고리즘

정답 코드

package day11_GraphDeepening;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1717집합의표현_3 {
    static int find(int node, int[] nodes) {
        if (node == nodes[node]) {
            return node;
        }
        nodes[node] = find(nodes[node], nodes);
        return nodes[node];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[m][3];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
        }

        int[] nodes = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            nodes[i] = i;
        }

        for (int i = 0; i < m; i++) {
            int a = arr[i][1];
            int b = arr[i][2];
            if (arr[i][0] == 0) {
                int A = find(a,nodes);
                int B = find(b,nodes);
                int rep = Math.min(A, B);
                int sub = Math.max(A, B);

                nodes[sub] = rep;

            } else {
                if (find(a, nodes) == find(b, nodes)) {
                    sb.append("YES\n");
                } else {
                    sb.append("NO\n");
                }
            }
        }
        System.out.print(sb);
    }
}

실패코드

• union에서 find 로 찾은 최종 대표 노드가 아닌, 단순 대표 노드를 사용해서 틀렸다.

for (int i = 0; i < m; i++) {
            int a = arr[i][1];
            int b = arr[i][2];
            if (arr[i][0] == 0) {
                int rep = Math.min(nodes[a], nodes[b]); // 단순 대표 노드를 사용
                int sub = Math.max(nodes[a], nodes[b]);

                nodes[sub] = rep;

            } else {
                if (find(a, nodes) == find(b, nodes)) {
                    sb.append("YES\n");
                } else {
                    sb.append("NO\n");
                }
            }
        }

반례

4 4
0 3 4
0 1 3
0 2 4
1 1 4

정답

NO

내 출력

YES

마무리

바로 안풀고, 시간 복잡도를 한번 체크한거 칭찬해~

이전에 DP 알고리즘을 정리한 적이 있는데, 까먹은 건지 DP인걸 캐치하지 못했다. 반성 겸, 정리 겸 DP를 다시 한번 정리하려고 한다.

1005번 ACM Craft가 DP였던 이유

가장 먼저, 이 글을 정리하게 된 계기를 정리해보자.

문제 설명

• 선행 조건에 따라 건물 짓는 순서가 결정 (DAG)
• 어떤 건물을 짓는데 걸리는 시간을 계산해야한다. ( → 이 부분이 DP)

이 문제를 풀면서 나는 여기까지 도달했다.

내 아이디어

1 -> 3      -> 4 
  -> 2 -> 5 -> 4
의문점1) 3,2 단계에서는 2의 시간만 필요한데, 이걸 이 시점에 알 수 있을까? 

1 -> 3 -> 4 -> 5
2 -> 6 -> 7 
의문점2) 7의 관점에서는 1,3,4,5의 시간은 필요없는데 이걸 어떻게 알 수 있을까? 

그리디일까? ❌ 

• 3의 시간이 더 짧기 때문에 2가 아니라 3을 선택하면 답이 틀린다.

어떤 순간의 최적인 답이 최종 정답으로 이어지지 않는다.

👉 따라서 특정 건물을 짓는데 걸리는 시간을 계산하기 위해서는 각 과정에 걸리는 값을 어딘가에 저장 후(메모제이션) 나중에 활용해야한다.  

DP란

부분 문제 결과를 저장하고 재활용한다.

👉 겹치는 하위 문제 + 최적 부분 구조 + 메모이제이션(또는 테이블링)

• 해당 문제의 구조가 하위 문제를 활용해서 (비교 해서) 결정된다.
• 과거 선택을 전부 기억하고 있어야 답을 구할 수 있다.

DP 문제 특징

• 서로 다른 경로가 “합쳐져서 경쟁함”
• 과거 선택을 전부 기억하지 않으면 답 못 구함
• 최적해가 여러 하위 문제들의 비교 결과로 나옴
• “누적값 최대/최소/경우의 수”가 등장함

키워드 : 최소 시간, 최대 이득, 경로 수, 누적, 겹치는 부분 문제

결국 1005번 문제는

• 여러 선행 경로 중 가장 오래 걸리는 경로를 선택해야한다.
• 지금 당장 결정할 수 없고, 계속 갱신하다가 마지막에 결정해야한다.
• 누적 시간이 등장한다.

1005 ACM Craft

dp 점화식

a -> b : dp[b] = max(dp[a]+time[b],dp[b])

풀이

• 진입차수가 0인 노드를 저장한 큐에서 꺼내기
  • 결과에 넣기 (노드 : a)
  • 관련 경로 차수 - - ; dp[관련 경로] = max(dp[a]+time[관련 경로], dp[관련 경로])
  • 차수 0이 된 노드 큐에 넣기
• 큐가 빌 때까지 계산

정답 코드

package day11_GraphDeepening;

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

public class BOJ1005ACMCraft {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            int[] degree = new int[n + 1];
            int[] time = new int[n + 1];
            int[] dp = new int[n + 1];
            Queue<Integer> q = new ArrayDeque<>();

            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < n + 1; j++) {
                time[j] = Integer.parseInt(st.nextToken());
            }

            List<Integer>[] graph = new ArrayList[n + 1];
            for(int j = 1; j < n + 1; j++) {
                graph[j] = new ArrayList<>();
            }

            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                graph[a].add(b);
                degree[b]++;
            }

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

            for (int j = 1; j < n + 1; j++) {
                if (degree[j] == 0) {
                    q.offer(j); //i로 함
                    dp[j] = time[j];
                }
            }

            while (!q.isEmpty()) {
                int node = q.poll();

                for (int k : graph[node]) {
                    degree[k]--;
                    dp[k] = Math.max(dp[k], time[k] + dp[node]);
                    if (degree[k] == 0) {
                        q.offer(k); //node로 해놓음
                    }
                }
            }

            sb.append(dp[w]).append("\n");
        }
        System.out.println(sb);

    }

}

• 방향 그래프의 정점들을 간선의 방향을 지켜서 나열하는 것이다.
• 선행 작업을 먼저 수행한 후에 후행 작업을 수행하도록 작업 순서를 정렬하는 알고리즘이다.

따라서, 사이클이 없는 방향 그래프(DAG)에서만 가능하고, 사이클이 있으면 위상정렬이 불가능하다.

(정답 여러개 가능)

위상 정렬로 풀 수 있는 문제 ⭐️

일반 정렬 : 숫자나 문자열처럼 값의 크기를 비교해 정렬 위상 정렬 : 노드 간의 선후 관계를 정렬 “순서 규칙”을 만족하도록 나열한다,

• 위상 정렬에는 선후 관계에 대한 규칙이 있다. (“1번은 2번보다 앞선다.”, “3번은 4번보다 앞선다”...)

따라서, 순서의 규칙이 있는 문제에 적용할 수 있으며, 풀이 과정 중 사이클의 존재를 확인할 수 있다.

문제 구별법

1. 선후관계나 순서정하기
   • "A 작업을 끝내야 B 작업을 시작할 수 있다”
   • 선수 과목, 선행 조건…
   • "A는 B보다 먼저 와야 한다”
   • 가능한 순서 중 하나를 출력
2. 사이클 판별
   • "순서를 정할 수 없는 경우를 판별”

대표적인 유형

• 작업 스케줄링 (선행 작업 있음)
• 커리큘럼 문제 (선수과목)
• 빌드 순서 (의존성 관리)
• 게임 캐릭터 순위 정하기

풀이 방법

키워드 정리

• 진입 차수 : 특정 노드로 들어오는 화살표(간선)의 개수
• 큐 : 진입 차수가 0인 노드들을 처리하기 위한 임시 저장소
• 결과 : 위상 정렬의 결과를 저장하기 위한 리스트

풀이 방법

1. 진입 차수가 0인 노드를 큐에 삽입
   1. 큐에서 노드를 꺼내 결과에 추가
   2. 해당 노드와 연결된 간선을 제거 (연결된 노드의 진입차수 -1)
   3. 진입차수가 0이 된 노드를 큐에 삽입
2. 큐가 빌 때까지 a~c 반복
3. 결과의 크기가 전체 노드 개수와 같지 않으면 사이클 존재

실제 문제 풀어보기 : 2252 줄세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

3 2
1 3
2 3

예제 출력 1

1 2 3

내 풀이

정답 코드 (다듬은 버전)

• 문자열 출력에 StringBuilder 사용
• Queue 구현체를 ArrayDeque 선택

실제로 시간이 반절가까이 감소해, 성능 확인

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ2252줄세우기V_2 {
    public static void main(String[] args ) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // StringBuilder: 반복적인 문자열 연결 시 System.out.print()보다 훨씬 빠름
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //그래프 그리기
        List<Integer>[] graph = new ArrayList[n + 1];
        int[] degree = new int[n+1];

        //1부터 n 까지만 초기화, 불필요한 9번 인덱스 초기화 제거
        for(int i = 1; i < n+1; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            degree[b]++;
        }

        //Queue 연산은 LinkedList 보다 ArrayDeque 이 적합
        // add, remove 보다는 offer, poll 권장 ✅
        Queue<Integer> q = new ArrayDeque<>();
        ArrayList<Integer> result = new ArrayList<>();

        //진입차수가 0인 ⭐️!! 조건식을 M으로 해서 문제
        for (int i = 1; i < n+1; i ++){
            if (degree[i] == 0) {
               q.offer(i);
            }
        }

        while(!q.isEmpty()){
            //큐에서 노드를 꺼내 결과에 추가
            // 📌 반복문 외부 선언 vs 내부 선언
            // ✅ 성능은 동일하고, 가독성과 안정성 면에서 내부 선언이 더 우수
            int node = q.poll();
            sb.append(node).append(' ');

            //해당 노드와 연결된 간선을 제거 (연결된 노드의 진입차수 -1)
            for (int k : graph[node] ){
                degree[k]--;
                if (degree[k] == 0){
                    q.add(k);
                }
            }
        }

        System.out.println(sb);

    }
}

실패 코드

• 오타로 인한 실패 ! 😩

        for (int i = 0; i < m; i++) { // 차수 계산하는 부분을 n이 아닌 m번 반복해 인덱스 에러 
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
  
            graph[a].add(b);
            degree[b]++;
        }
  

## 처음 풀이 링크드 리스트로 풀기 

1. 비교 정보 리스트 정렬 → 1 2 / 2 4 / 3 2 → 1 2, 2 4, 3 2,
2. 링크드 배열에 값 넣기
    1. 1번의 결과의 첫번째를 배열 첫번째 링크드 배열의 값으로 선언
    2. 1번의 결과의 두번째값을 링크드 배열의 값으로 선언, 이 객체를 첫번째 배열의 next값으로 설정
    3. 그 다음…???
    4. 2번의 결과의 첫번째 값을 세번째 객체로 설정, 두번째 객체의 넥스트 값으로 이 객체 설정

—> **문제 !!**
- 2번의 결과의 첫번째 값과, 1번의 결과의 두번째 값이 같은 걸 어떻게 구별할 것인가???*

```jsx
    [1, 2] ⇒ [2, 3] 인 상태에서 
    1. [4, 2]를 넣어야해! 그러면, 2를 원래 가리키던 1를 찾아야하는데
    매번 이 리스트를 전체 순회해서 찾기? (n회 반복)
    2. [2,5]를 넣는다면? 2가 가리키는 3에 3->5를 해야하는데, 2를 value로 하는 애들 찾아야하니까.. 또 n번 순회

    한번 넣을때마다, 
    첫번째 요소가 이미 값으로 있는지 체크 (n회), 첫번째 요소를 가리키고 있는 애가 있는지 (n회) 
    --> n*n

이중 for문 → 연산 횟수는 n^2 32,000 ^ 2 ≈ 1,024,000,000 → 약 10억 번 반복

*n이 32,000이고, 시간 제한이 2초 → 무조건 이중 포문은 안된다는 결론이 나온다 *

오답노트

⭐️ 결국, 시간 복잡도를 고려하지 않고 대강 풀어서 시간을 버렸다. 어떤 알고리즘을 적용하기 전에는 이거다! 확신을 갖고 풀어야겠다 (시간 복잡도나, 문제의 특징을 바탕으로!)

시험 기간과 이것저것.. 집중하지 못했슨..
다시 시작해보겠슨

deque (collections.deque)

# 양쪽에서 O(1)로 삽입/삭제 가능 — 스택, 큐 모두 구현 가능
from collections import deque

dq = deque([1, 2, 3])
dq.append(4)        # 오른쪽 추가 → [1, 2, 3, 4]
dq.appendleft(0)    # 왼쪽 추가 → [0, 1, 2, 3, 4]
dq.pop()            # 오른쪽 제거 (4 반환)
dq.popleft()        # 왼쪽 제거 (0 반환)
dq[0]               # 맨 앞 요소 접근
dq[-1]              # 맨 뒤 요소 접근

heapq: 자동 정렬된 우선순위 큐 — O(logN) 삽입/삭제

import heapq

hq = []
heapq.heappush(hq, 3)
heapq.heappush(hq, 1)
heapq.heappush(hq, 2)
heapq.heappop(hq)   # 1 반환 (가장 작은 값)
min_val = hq[0]     # 최소값 확인만 하기 (제거 X)

# 최대 힙처럼 쓰려면 음수로 저장
heapq.heappush(hq, -x)  # push
x = -heapq.heappop(hq)  # pop

우선순위 큐 + DP 문제 풀기

우선순위 큐

import heapq

pq = []  # 우선순위 큐(최소 힙) 초기화

# 리스트 형태의 요소들을 하나씩 넣기
heapq.heappush(pq, [3, 'C'])
heapq.heappush(pq, [1, 'A'])
heapq.heappush(pq, [2, 'B'])

print(pq)
# 내부 구조 예: [[1, 'A'], [3, 'C'], [2, 'B']]  (힙 구조)

# heappop()을 하면 첫 번째 원소(0번째 인덱스 기준)가 작은 리스트가 나옴
print(heapq.heappop(pq))  # [1, 'A']
print(heapq.heappop(pq))  # [2, 'B']
print(heapq.heappop(pq))  # [3, 'C']

직접 문제 풀어보기

1781 컵라면

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 범위에 따른 DP를 할때는 이전 조건이 이후 조건의 넓은 범위를 유지하도록 해, 우선순위 큐 내부의 적합성을 유지하자

1202 보석 도둑

• 풀이 링크 : 🔗 개인 노션 링크

• 한줄 정리 : 어떤 구조일때 이전 조건이 이후 조건에도 만족할 수 있는지를 따져보자

  보석 무게 ≤ 1 을 만족할 수 있는건 이후 보석무게 ≤2를 만족한다. ✅

자소서 핑계로 한껏 헤이해진 나 ! 
하지만 또 시작하면 된다...
쏟아지는 취업공고에 쫓기는 기분이 들지만 괜찮다!! 

후회없이 이 시기를 잘 보내자! 그렇다면 나의 제 3의 전성기 시작임요~~~~ 

DP 심화

LIS/LCS, 문자열 DP 점화식 세우는 훈련을 해보자 

직접 문제 풀어보기

11053 가장 긴 증가하는 부분 수열

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 무조건 O(n^2)을 피하는게 아니라 n의 크기를 함께 고려하면서 시간복잡도에 따른 시간을 고려하자.(n^2)이면 무조건안될거라고 생각해서 다른 방법을 찾느라 늦었음.... n이 1000이도라.. !! 1000이면 1초 내로 가능 !

11055 가장 큰 증가하는 부분 수열

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 가장 긴 증가하는 부분 수열의 알고리즘을 활용하면 된다. 즉 !!! _가장 긴 증가하는 부분수열의 알고리즘_을 잘 기억하자..!!

9251 LCS

• 풀이링크 🔗 개인 노션 링크
• 한줄 정리 : 오 ! 이게 되네? 역시 겁먹지말고 그냥 해보면 됨 !!!! 아자자!! 앞으로도 이렇게 !!

2156 포도주 시식

• 풀이링크 🔗 개인 노션 링크
• 한줄 정리 : 코테는 기세다 !

마무리하면서

진리를 알았슨. 코테는 기세였슨!! 자신감가지고 하니까 다 풀림!! 장난이구 그냥 직접 써보면서 반례와 규칙성을 찾다보니까 잘 찾아졌다. 역시 직접 해보는게 중요한 것 같다!

매일 하겠다고 스스로 다짐했지만...
쉽지 않았다!!
하지만 그냥 또 도전하면 된다 !! 생각해보면 다시 시작하는게 제일 쉬움 
오ㅔ?!?!?!

그냥 하면 되기 때문 

배낭 DP

• 핵심개념 : 제한된 용량이 있는 배낭에 담을 물건을 골라 가치의 합을 최대로 만드는 문제 각 물건의 개수에 따라서 문제의 유형이 나뉜다.

• 배낭 문제 유형 :

1. 0-1 Knapsack: 각 물건은 넣거나 안 넣거나 두 가지 선택만 있음 (쪼갤 수 없음)
2. Unbounded Knapsack : 무한 배낭 문제로 각 물건을 여러번 담을 수 있음.

0-1 Knapsack (0-1 배낭 문제)

• 특징: 각 물건은 최대 1번만 담을 수 있음

• 점화식: 해당 무게 넣고, 가능한만큼 넣었을때 배낭의 가치(dp[i-1][w - weight[i]]) 의 합과, 해당 무게를 안넣었을때, 직전의 최댓값

  i : 아이템 번호
  w : 배낭의 현재 셋팅 무게 (점점 늘려가면서) 
  
  dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

  • dp[i][w]: i번째 물건까지 고려, 용량 w일 때 최대 가치
  • "안 담는다 vs 담는다" 중 큰 값 선택

배열 최적화

• 2차원 → 1차원 배열 dp[w]로 압축 가능
• 단, 같은 물건을 여러 번 쓰지 않으려면 뒤에서 앞으로 순회해야 함

  for i in range(n):
      for w in range(capacity, weight[i]-1, -1):
          dp[w] = max(dp[w], dp[w-weight[i]] + value[i])

Unbounded Knapsack (무한 배낭 문제)

• 특징: 각 물건을 여러 번 사용할 수 있음 (제한 없음)

• 배낭 무게 제한은 여전히 있음

• 점화식:

  dp[i][w] = max(dp[i-1][w], dp[i][w - weight[i]] + value[i]) 
  # -> 여전히 아이템 i를 고려하는 상황
  

  • 차이점: dp[i][...]를 참조 → 같은 아이템 반복 사용 가능

왜 무한 배낭 문제는 dp[i][w] 를 dp[i][w - weight[i]] + value[i], dp[i-1][w] 에서 고민할까?

무한 배낭 문제는 현재의 가치,무게를 가진 물건을 여러번 넣을 수 있다.

(1) dp[i][w - weight[i]] : s는 지금 물건을 여러번 넣을 수 있는 상황에서 새로 업데이트한 최댓값 (2) dp[i-1][w] : 아예 i번째 물건을 쓰지 않고 구한 최대 가치

내가 헷갈린 점; 그러면 dp[i][w - weight[i]] 는 i-1번째 물건은 아예 안넣은 최댓값인가? 아니다. dp[i][w - weight[i]] 값 또한 i-1번재까지 넣은 물건과 i번째 물건을 넣은 상태를 같이 고민해서 나온 최댓값이다.

배열 최적화

• 같은 물건을 여러 번 쓸 수 있으므로, 앞에서부터 순회 가능

  for i in range(n):
      for w in range(weight[i], capacity+1):
          dp[w] = max(dp[w], dp[w-weight[i]] + value[i])

배열최적화를 한다고 시간복잡도가 줄어드는 것은 아니다.

비교 정리 표

직접 문제를 풀어보자

• 12865 평범한 배낭

• 풀이 링크 : 🔗 개인 노션 링크

• 2293 동전 1

• 풀이 링크 : 🔗 개인 노션 링크

• 2294 동전 2

• 풀이 링크 : 🔗 개인 노션 링크

• 7579 앱

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 단순하게 디피 로직에 끼워맞히는게 아니라, 어떤 걸 찾으려고 DP를 적용하는 중인지 생각하면서 코드를 짜자 !!

다시 시작해보자

꾸준한 건 실패하지 않는게 아니라 실패해도 또 하는 것이다 

DP는 Dynamic Programming의 약자로 동적 프로그래밍이라는 뜻을 가지고 있다.

• 핵심아이디어 : 큰 문제를 작은 문제로 쪼개고, 작은 문제의 해를 저장해서 큰 문제를 푸는 방식

• 핵심 키워드 :

  • 점화식 : “큰 문제 = 작은 문제들의 관계”를 수식으로 표현
    • 저장 : DP 배열에 계산 결과를 저장해서 재활용

  ➡️ DP문제는 부분 문제의 해를 저장하고 점화식으로 표현하여 큰 문제의 답을 찾아가야한다.

1차원 DP의 접근 방식

1. 배열 dp[i]를 정의한다.
2. 작은 문제에서 큰 문제로 확장되는 규칙을 찾음 (실제 해보는 것도 도움)
3. 점화식으로 dp[i]를 dp[i-1], dp[i-2], ... 같은 이전 값으로 표현.
4. dp[1], dp[2] 같은 가장 작은 케이스(초기값)를 손으로 계산

주의할 점 : 배열 크기와 초기값을 0으로 할지 1로 할지 주의해야한다.

그렇지만 dp 는 최대한 많이 풀어보는게 중요한 것 같다 !!

직접 문제 풀어보기

1463 1로 만들기

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : dp배열을 정의하고, 각 단계에서 나올 수 있는 경우의 수를 구해보자

9095 1,2,3 더하기

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : dp 배열의 크기 최솟값을 고민했음. 직접 입력해야하는 값들의 크기에 따른 dp 배열의 최소 크기를 고민했다.

2579 계단 오르기 ⭐️ 추천

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : dp배열을 정의하고, 각 단계에서 나올 수 있는 경우의 수를 구해보자

1520 내리막길

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 힙 + dp 문제 dp 배열의 값을 순차적으로 업데이트 하는게 아니라 힙을 통해서 빠른 시간내에 최댓값을 찾고 접근하는 문제였다. 또 방문노드도 사용해서 이미 업데이트 한 인덱스는 접근하지 않도록 했다. 다익스트라 알고리즘에서 힙을 사용한 기억이 단서가 됐다.

정리하면서

더 많은 문제를 풀어본다면 오늘 내리막길 문제를 푼 것처럼 활용할 단서가 더 늘어날 것이라고 생각한다.
꾸준히 공부하고 싶어지는 하루였다
만족도 100
아주 행복함 ! 

외주를 받아 쇼핑몰 서비스를 개발하던 와중에 상품 도메인의 상품 옵션 도메인의 잘못된 설계로 이후, 장바구니, 구매 테이블에 문제가 생겼다.

그러나 당시에는 문제가 많다는 것을 뒤늦게 알게되었고, 재설계를 하기에는 마감 일자가 빠듯해 리팩토링하지 못했다.

내 데이터 베이스 설계에 어떤 문제점이 있는지와, 해당 문제로 인한 파급효과를 정리하고, 데이터 베이스 설계시 주의할 점을 정리해 앞으로는 해당 문제를 겪지 않도록 하고자 한다.

문제 설명

당시 요구사항

-해당 이미지는 네이버 쇼핑에서 들고온 사진으로 제가 실제로 개발한 서비스는 이닙니다._

상품

• 상품은 기본 옵션과 추가 옵션을 가진다.
• 기본 옵션은 상품이 필수로 가져야한다.
• 추가 옵션은 선택적으로 가질 수 있다.

장바구니

• 사용자 한명은 장바구니 하나를 가진다.
• 장바구니에는 원하는 상품여러개를 담을 수 있다.
• 담을 떄는 기본 옵션을 필수로 하나 이상 선택 후, 추가 상품은 자유롭게 선택할 수 있다.

주문

• 사용자는 원하는 상품 여러개를 구매할 수 있다.
• 상품은 기본 옵션을 필수로 하나 이상 선택, 추가 상품은 자유롭게 선택할 수 있다.

DB 설계

당시 나는 기본 옵션과 선택옵션의 비즈니스 로직에 차이가 있다는 것을 간과했고, 테이블 수가 줄어들면 엔티티나 관리해야하는 양이 줄어들 것이라고 생각했다. 따라서 기본 옵션과 추가 옵션을 같은 상품 옵션의 테이블로 넣고, 성격의 분리를 enum 값을 통해서 관리했다.

당시 설계도

실제 코드

_실제로는 여러 필드가 있지만 단축해서 가져왔다.! _

ProductEnum 클래스

• 기본 옵션과 추가 옵션 종류를 나타내는 Enum 클래스이다

  public enum OptionKind {
    OPTION,
    ADD_ON
  }

Product 클래스

• 양방향으로 뒀다고 가정하자
• 옵션이 테이블별로 구분되지 않기 때문에 OptionKind로 필터링하는 단계가 필요하다.
• 요구사항에 기본 옵션은 필수라는 조건 사항이 있지만 현재 엔티티로는 해당 요구사항을 제약조건으로 확인할 수 없다.

public class Product {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(nullable = false, length = 120)
    private String name;

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "category_id", nullable = false)
    private Category category;


    // 필터링 후 옵션 정보를 가져오는 메서드    
    public List<ProductOption> getOptions() {
        return options.stream()
                      .filter(o -> o.getKind() == OptionKind.OPTION)
                      .toList();
    }

    public List<ProductOption> getAddOns() {
        return options.stream()
                      .filter(o -> o.getKind() == OptionKind.ADD_ON)
                      .toList();
    }
}

ProductOption 클래스

• 상품옴셥은 옵션의 종류를 필드로 가진다.

  public class ProductOption {
  
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
  
    /** 옵션명(예: “화이트 / M”) */
    @Column(nullable = false, length = 100)
    private String name;
  
  

@Enumerated(EnumType.STRING)
private OptionKind kind;

/* 연관관계 */
@ManyToOne(fetch = FetchType.LAZY)
@JoinColumn(name = "product_id")
private Product product;

}

#### Order 클래스
```java
public class Order {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(unique = true, nullable = false)
    private String orderId;            // 외부 노출용 주문번호

    @ManyToOne(fetch = LAZY)
    @JoinColumn(name = "user_id", nullable = false)
    private User user;               
}

OrderProducts 클래스

• 주문 클래스는 상품의 가격이 변동될 수 있기 때문에 스냅샷으로 별도로 저장하였다.

• 주문 상품 옵션은 옵션의 종류를 필드로 가진다.

• 요구사항에 기본 옵션은 필수라는 조건 사항이 있지만 현재 엔티티로는 해당 요구사항을 제약조건으로 확인할 수 없다.

  public class OrderProduct {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
  
    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "order_id", nullable = false)
    private Order order;
  
    private Long productId;            // 원본 Product PK 가격과 정보들을 스냅샷으로 저장
  }

OrderProductOption 클래스

public class OrderProductItem {
    @Id @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "order_product_id", nullable = false)
    private OrderProduct orderProduct;

    // 옵션 스냅샷 
    private Long optionId;                 // ProductOption PK

    @Enumerated(EnumType.STRING)
    private OptionKind optionKind;         // BASIC / ADDON (기존 로직 그대로)
    private String optionNameSnap;         // 옵션명 스냅샷
    private Integer quantity;              // 수량
}

Cart클래스

public class Cart {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @OneToOne(fetch = FetchType.LAZY)                // 유저당 1개
    @JoinColumn(name = "user_id", nullable = false, unique = true)
    private User user;
}

CartItem 클래스

• 당시 상품 → 주문 → 장바구니 순으로 개발하였고 장바구니을 개발하면서는 해당 디비 설계에 문제가 있음을 알게되었다.

• 급한대로 장바구니아이템 테이블이라도 기본옵션과 추가 옵션을 분리하였다.

• 따라서 유일하게 장바구니 상품 옵션의 테이블은 옵션 종류를 가지고 있지 않다.

  public class CartItem {
    @Id @GeneratedValue
    private Long id;
  
    @ManyToOne(fetch = LAZY) @JoinColumn(name="cart_id")
    private Cart cart;
  
    private Long productId;
  
    private Long optionId;  //기본 옵션
    private Integer optionQuantity;
  
  

@OneToMany(mappedBy = "cartItem", cascade = CascadeType.ALL, orphanRemoval = true)
@Builder.Default 
private List<CartItemAddOn> addOns = new ArrayList<>(); // 추가 옵션 리스트

}

#### CartItemAddOption 클래스
```java
public class CartItemAddOn {
    @Id @GeneratedValue
    private Long id;

    @ManyToOne(fetch = LAZY)
    @JoinColumn(name = "cart_item_id", nullable = false)
    private CartItem cartItem;

    /** 상품_옵션 테이블 PK */
    private Long addOnOptionId;
    private Integer quantity;
}

상품 클래스의 getter 메서드만 살펴보아도 If가 여러번 필요함을 짐작할 수 있다. 이런 if 동작이 응답 객체를 만드는 과정, 요청객체를 내부 엔티티로 만드는 과정중에서 계속 해서 요구되고, 상품의 핵심 규칙을 검사하고 유효성을 확인하는 코드가 여러군데에 분산되게 되었다.

또한 협업의 측면에서도 다른 사람이 보기에 코드를 파악하기 어려운 스파게티 코드가 되었다. 입시 방편으로 쓴 장바구니 엔티티는 다른 상품, 주문와 다르기 때문에 또다른 혼란이 생길 수가 있다.

문제 원인 분석 : DB가 보장해야하는 핵심 불변 규칙을 모델로서 표현하지 못했다.

데이터베이스는 다음을 표현해야한다.

1. 식별/정체성 : 식별키(유니크속성)
2. 관계 : 참조 무결성 : 외래키
3. 도메인 무결성 : 들어가 있는 값에 흠이 없다. 값의 범위와 타입, 유무와 관련된 제약
4. 업무 무결성 중 변하지 않는 불변 규칙 : 항상 참이어야하는 규칙

내 서비스에서 “기본 옵션 최소 1개” 는 (쉽게) 변하지 않는 규칙이고, 상품의 값의 무결성과 관련된 규칙이다.

DB에는 올바른, 깨끗한, 무결성의 값들만 들어와야한다. 아래의 상황을 가정해보자

백엔드 코드에 문제가 생겨서, 디비에 기본옵션이 없고 추가 옵션만 가진 상품을 insert했다. DB는 잘못된 상품이 들어왔지만, 이를 파악할 수 없다. 이후 사용자가 해당 데이터를 조회하는 요청을 보냈고, 서버에서는 디비에 값을 조회할 것이다. ...?? 프로그램이 정상적으로 동작하지 않는다.

데이터베이스는 무결성을 보장해야한다. 나의 사례는 도메인 규칙을 제약조건이나 연관관계로 표현하지 않고Enum 으로만 표현했다.

이로인해 데이터의 무결성을 보장할 수 없게 되었다.

관계형 데이터 베이스의 무결성

무결성이란, 데이터 베이스에 저장된 데이터 값과 그것이 표현하는 현실 세계의 실제값이 일치함, 정확함을 의미한다.

즉, 데이터베이스가 무결성을 가진다는 것은 해당 데이터 베이스에 저장된 값들이 정확한 데이터들이 저장되어있고, 앞으로도 그럴 것을 보장함을 말한다.

무결성의 종류를 나눠본다면

1. 개체 무결성(Entity integrity) : PK는 NULL 안 되고, 유일해야 한다.
2. 참조 무결성(Referential integrity) : FK 값은 반드시 부모 테이블에 존재해야 헤야한다.
3. 도메인 무결성(Domain integrity) : 속성 값은 정해진 범위/형식 안에 있어야 한다. (예: 수량 ≥ 0, 이메일 형식 체크.)
4. 업무 무결성(Business integrity, Semantic integrity) : 특정 애플리케이션/업무 규칙에 따라 항상 참이어야 한다. (예: “주문은 최소 1개의 기본 옵션을 가져야 한다”, “마감일은 시작일보다 늦어야 한다”.)

결국 비즈니스 무결성을 보장하지 못했다.

위 무결성의 정의와 종류를 살펴봤을 때, 나의 디비 설계는 “기본 옵션 최소 1개”같은 업무 규칙을 제약 조건으로 보장하지 못했고, 따라서 무결성을 지키지 못했다는 문제점이 있다.

해당 문제를 해결하기

먼저 비즈니스 규칙을 주고 제약 조건을 줄 수 있도록 테이블을 분리한다.

자바 코드에서도 수정하기 (상품 테이블만)

ProductEnum 클래스

• 해당 클래스는 더이상 사용하지 않는다.

Product 클래스

• "최소 1개" 제약 조건은 어노테이션으로 둘 수 없기 때문에 서비스 레이어와 엔티티 레벨에서 메서드로 검사 로직을 둬야한다.
• @PrePersist,@PreUpdate어노테이션은 데이터베이스에 저장되기 직전에 필수 옵션 개수를 검사하도록 강제

public class Product {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(nullable = false, length = 120)
    private String name;

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "category_id", nullable = false)
    private Category category;

    @OneToMany(mappedBy = "product", cascade = CascadeType.ALL, orphanRemoval = true)
    private List<ProductBasicOption> basicOptions; //별도로 분리 

    @OneToMany(mappedBy = "product", cascade = CascadeType.ALL, orphanRemoval = true)
    private List<ProductAddOnOption> addOnOptions; //별도로 분리 


    //DB 저장/업데이트 전 호출되어 '기본 옵션 최소 1개' 규칙을 강제
    @PrePersist
    @PreUpdate
    private void validateBasicOptions() {
        if (basicOptions == null || basicOptions.isEmpty()) {
            throw new IllegalStateException("상품은 반드시 1개 이상의 기본 옵션을 가진다.");
         // 실무에서는 Custom Exception 을 권장
        }
    }


}

ProductBasicOption 클래스

• 상품옴셥은 옵션의 종류를 필드로 가진다.

  // 상품 기본 옵션 엔티티
  public class ProductBasicOption {
  
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
  
    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "product_id", nullable = false)
    private Product product;
  
    @Column(nullable = false, length = 100)
    private String name;
  
    private int price;
  }
  

#### ProductAddOnOption 클래스
```java
// 상품 추가 옵션 엔티티
public class ProductAddOnOption {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "product_id", nullable = false)
    private Product product;

    @Column(nullable = false, length = 100)
    private String name;

    private int price;
}

다른 코드 또한 기본 옵션과 추가 옵션을 분리하도록 하자.

마무리하면서

처음에 상품 테이블을 설계하면서 단순하게 테이블 개수를 줄이고 싶다는 판단을 내렸다. 그러나 이렇게 데이터베이스의 무결성등 기본 이론을 고려하지 않고 사용한다면 단순 저장소 정도로 사용하게 된다.

제약 조건과 여러 정규화를 통해 올바른 DB를 설계했을때 믿을 수 있는 DB를 사용할 수 있다.

덧붙이자면, 항상 DB를 설계할때 Join 의 성능을 걱정하게 되는데, 실제로는 얼마나 join 연산이 오래걸리는지 확인해본적이 없다.

고로 다음글은 !!! Join 의 성능을 테스트해보자 !

✅ 다익스트라
✅ 플로이드 삼중 for문 

최단 경로

다익스트라

대표적인 최단 경로 탐색

• 결과 : 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로 ( s->e 만 구하는 것이 아님)

• 제약 조건 : 간선(거리)가 음의 값을 가진다면 사용할수 없다.

• 점화 식 :

  if dp[e] > dp[u] + w :
    dp[e] = dp[u] + w
    heapq.heappush(h, (dp[e], e))` 

설명

• 필요한 값

  • 노드간 거리 배열 : 현재 내 코드에서는 2차원 배열
  • 디피 배열 (시작점으로부터의 모든 노드까지의 거리를 저장하는)
  • 방문 여부를 저장하는 방문 배열
  • 미방문 중에서 가장 가까이 위치한 노드 정보를 담는 힙 : ( 선형 탐색으로 구현시 시간 복잡도가 크다)

• 과정

  1. 힙에 탐색할 시작점과 인접한 노드 정보 푸시 + 시작점을 방문 표시
  2. 힙이 빌때까지 아래 과정 반복 2-1. 힙에서 꺼내기 2-2. 방문한 노드라면 넘어가기,//해당 노드 방문 처리 2-3. 다른 노드에 대해서, 해당 노드를 거쳐가서 시작점에 가는 경우가 더 빠른 경우 디피배열 업데이트 2-4. 업데이트가 일어났다면 힙에 푸시 ()
  3. 디피 배열 완성

다이나믹 프로그래밍 (DP)

• DP는 부분 문제 해를 저장하고 활용한다

큰 문제를 작은 문제로 쪼개서 해결하고, 그 결과를 저장해두고 재활용하는 방식. “부분 최적해의 누적” = 전체 최적해로 이어진다. 다익스트라는 시작점과 정점사이의 거리를 저장하고 더 짧은 거리를 선택하는 점화식을 사용하며 갱신한다. (여기에 그리디한 선택까지 ! )

플로이드 삼중 for문(플로이드–워셜 알고리즘)

• 결과 : 모든 정점 쌍 최단 거리 구하기

• 제약 조건 : 시간 복잡도가 O(N³)으로 노드 수가 크면 비효율적이다. (보통 N ≤ 400 정도까지 실용적)

• 점화 식 :dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

설명

노드 a에서 노드 b로 가는 거리가 노드 c를 거쳐 가는 경우가 더 짧을 수있다. 모든 경우에 대해서 삼중 포문을 돌린다.

초기 상태

k = 2, i = s, j = 3 

dist[s][3] = min(dist[s][3], dit[s][2] + dit[2][3]

k = 2, i = s, j = e
dist[s][e] = min(dist[s][e], dit[s][2] + dit[2][e] => 여긴 갱신 X

➡️ 이때 s -> 3 경로가 2를 거쳐가는 짧은 경로로 업데이트 된다.

k = 3, i = s, j = e

dist[s][e] = min(dist[s][3], dit[s][3] + dit[3][e]

➡️ 이때 s -> e 경로 업데이트

직접 문제 풀어보기

11724 연결요소의 개수

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 시간, 메모리를 아끼려면 인접 노드 그래프 형식으로 바꿔야한다 ! 노드간에 가중치가 있는 경우에는 [{노드 : 가중치, 노드 : 가중치} ... ] 형식으로 저장

1916_최소비용

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 도착,출발) 이 동일한 버스 노선이 존재할 수 있었다..^^

11404_플로이드

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 플로이드 위셜 알고리즘은 N ≤ 400 정도까지 실용적 이고, k가 가장 바깥 !

1956_운동

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 플로이드?!

마무리하면서

꾸준함이 이긴다 ! 

✅ 다중 시작점 BFS
✅ 최단거리 응용

BFS 심화

다중 시작점 BFS

• 개념 : 일반 BFS는 보통 시작점이 하나이지만 다중 시작점 BFS는 시작점이 여러 개일 때, 모두 동시에 출발시키는 방식이다.
• 구현 : 단순히 여러개인 시작점 모두를 큐에 집어넣고 시작하면 된다.
• 이점: 동시에 시작하기 때문에 시작점이 여러개 일때 모든 시작점으로부터의 최소 거리를 구하기 쉽다.

최단거리 응용

• 개념 : BFS는 간선 가중치가 동일할 때 최단거리를 보장한다. 또한 단순 최단거리뿐 아니라, 특정 레벨까지만 탐색이나 탐색하면서 상태(조건)를 함께 고려같은 확장이 가능
• 거리 계산 : dist[next] = dist[curr] + 1 로 거리 배열을 관리

거리 계산방법

저번 미로 찾기 문제에서는 거리를 방문 큐에 같이 저장하면서 활용했다.

queue.append((i, j, d+1))

만약 각 지점 별 거리를 활용해야한다면 별도의 거리 배열을 만들어서 사용할 수 있다.

dist[next] = dist[curr] + 1

문제 풀기

7576 토마토

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 토마토 개수를 세서, 토마토를 찾을때마다 -1 연산해주기

1012 유기농 배추

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 배추 밭 배열을 별도로 만들지 않고 바로 dict으로 만들었다. 배추밭배열을 만드면 n * m 배열을 무조건 순회해야하는데 이 코드에서는 그런 반복문이 빠져서 시간이 많이 단축된 것 같다 !! ^_^ 이번 기회에 dict도 한번 더 정리해봣어요

11724 연결요소의 개수

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 양방향 그래프 만들기

추가 정리) 파이썬 dict

d = {"a": 1, "b": 2}

# 안전한 조회
d.get("a", 0)       # key 없으면 0 반환

# key, value 순회
for k, v in d.items():
    ...

# 다른 dict 합치기 / 값 갱신
d.update({"b": 3, "c": 4})

# key 삭제 & 값 반환
d.pop("a", 0)       # 없으면 기본값 반환

# 전체 삭제
d.clear()

# key / value만 보기
d.keys()
d.values()

오랜만입니다요 
토스 시험준비때문에 알고리즘을 잠시 ^^ 하지 못했습니다.

그렇다면 얼른 DFS,BFS를 공부하러 가봅시다

그래프 탐색 기초 : DFS, BFS

학습 목표

✅ 인접리스트/행렬 구현
✅ 재귀 DFS vs 큐 BFS 비교

DFS

• 핵심 포인트: 깊게! 갈 수 있을 때까지 끝까지 들어가고, 막히면 뒤로 돌아옴.
• 구현 방법:
  • 재귀 구현 (스택 원리)
  • 스택 자료구조 사용
• 특징: 경로 추적, 백트래킹, 경우의 수 탐색에 적합 방문 순서가 한쪽으로 쭉 뻗어나가는 느낌

구현 코드

from collections import deque

# 예시 그래프 (인접 리스트)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

# ----------------
# DFS (재귀)
# ----------------
def dfs_recursive(v, visited):
    visited.add(v)
    do_something(v)  # <- 여기서 노드 방문 시 원하는 동작
    print(v, end=" ")
    for nxt in graph[v]:  # 연결된 리스트 탐색 
        if nxt not in visited: # 해당 노드를 방문하지 않았을 경우
            dfs_recursive(nxt, visited)

# ----------------
# DFS (스택)
# ----------------
def dfs_stack(start):
    visited = set()
    stack = [start]
    while stack:  # 비어질때까지
        v = stack.pop()
        if v not in visited:
            visited.add(v)
            print(v, end=" ")
            # 역순으로 넣어야 작은 번호 먼저 방문 가능
            stack.extend(graph[v])

왜 DFS는 스택을 쓰고, 왜 BFS에서는 큐를 쓸 까

DFS는 깊이 우선 탐색이고, BFS는 너비 우선 탐색이다.

DFS는 깊이가 끝인, 더 탐색할게 없는 리스트에 갈때까지 탐색한다. 그러다보니 동일 뎁스에 있는 다른 리스트가 있더라도, 내가 탐색하는 리스트의 하위 리스트를 먼저 가야한다. 해당 상황을 실제 스택의 상태로 설명해보자

1. 노드 A를 탐색하기 시작 : [(이전 뎁스 노드), ... ,(동일 뎁스 노드)] -> 노드 A를 맨 뒤에서 꺼냄
2. 노드 A에 연결된 하위 노드의 리스트 : graph[A] = [a,b,c]

3. 하위 노드 담기 동작 후 : [(이전 뎁스 노드), ... ,(동일 뎁스 노드), a, b, c]  

이후 탐색할 노드에 접근하기 위해서는, 방금 전에 들어온 노드를 꺼내는 선입 후출의 스택이 필요하다. 앞에서 꺼내면, 하위 노드가 아닌 엉뚱한 노드를 탐색하게 된다. 반대로 동일 뎁스의 노드에 접근해야하는 bfs는 선입 선출의 큐를 쓰는 것이다.

또한, DFS의 자료구조때문에 노드 순서가 반전된다는 것을 유의하자,

BFS

• 핵심 포인트: 넓게! 시작점에서 가까운 노드부터 탐색.
• 구현 방법:
  • 큐(Queue) 사용 (FIFO 원리)
• 특징: 최단 거리 문제에 자주 사용 (특히 간선 가중치가 1일 때) 방문 순서가 동심원처럼 퍼져나가는 느낌

구현 코드

from collections import deque

# 예시 그래프 (인접 리스트)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}


# ----------------
# BFS (큐)
# ----------------
def bfs(start):
    visited = set([start])
    queue = deque([start])
    while queue:
        v = queue.popleft()
        print(v, end=" ")
        for nxt in graph[v]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)

인접 행렬 vs 인접 리스트

인접 행렬: 2차원 배열, graph[a][b] = 1 이면 연결됨.

• 장점: 구현 간단, 연결 여부 확인 O(1)
• 단점: 메모리 많이 차지 (O(N²))

인접 리스트: 각 노드마다 연결된 노드를 리스트로 저장.

• 장점: 메모리 절약 (O(N+E))
• 단점: 특정 연결 여부 확인은 느림

재귀 DFS vs 큐 BFS 비교

❗️간선이 동일하다는 것의 의미 : 노드간의 거리가 모두 1로 동일 -> 따라서 이 경우에는 BFS에서 어떤 노드에 처음 도달한 순간이 곧 최단 거리임을 보장

실제 문제 풀어보기

1260 DFS와 BFS

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 숫자리스트요소를 공백구분해서 한줄 출력 print(" ".join(map(str, bfs)))
  

2606 바이러스

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 굿 ^_^

2667 단지 번호 붙이기

• 풀이 링크 : 🔗 개인 노션 링크

2178 미로탐색

• 풀이 링크 : 🔗 개인 노션 링크

• 한줄 정리 : 기준인덱스의 유효한 상하좌우 좌표 구하기

    #외부에서 좌표 설정
    dirs = [(-1,0),(1,0),(0,-1),(0,1)] 
  
    #상대 좌표
    for dx, dy in dirs:
      #절대 좌표로 변경
      nx, ny = x + dx, y + dy
  
      #절대 좌표의 유효성 검사
      if 0 <= nx < n and 0 <= ny < n \
         and grid[nx][ny] == 1 and not visited[nx][ny]:
          # 원하는 동작
  

  

단지번호붙이기의 더 좋은 코드

기존 코드의 문제

1. 불필요한 route 사용

   차례대로 순회해도 동일

2. get_index 라는 함수 불필요

    #외부에서 좌표 설정
    dirs = [(-1,0),(1,0),(0,-1),(0,1)] 
   
    #상대 좌표
    for dx, dy in dirs:
      #절대 좌표로 변경
      nx, ny = x + dx, y + dy
   
      #절대 좌표의 유효성 검사
      if 0 <= nx < n and 0 <= ny < n \
         and grid[nx][ny] == 1 and not visited[nx][ny]:
          # 원하는 동작

개선코드 : 내부에서 방문 표시

import sys
from collections import deque

input = sys.stdin.readline

# 깊이 탐색 아니면 너비 탐색?

n = int(input())
arr = [[int(x) for x in input().strip()] for _ in range(n)]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

visited = [[0] * n for _ in range(n)]

k = []
sum = 0

stack = deque()

for i in range(n):
    for j in range(n):
        if arr[i][j] == 1 and visited[i][j] != 1:
            stack.append((i, j))
            number = 0

            while stack:
                # 꺼내기
                x, y = stack.pop()
                # 방문 검사와 방문 표시
                if visited[x][y] == 1:
                    continue
                visited[x][y] = 1
                number += 1
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] == 1:
                        stack.append((nx, ny))

            if number != 0:
                k.append(number)

k.sort()
print(len(k))
for x in k:
    print(x)

개선코드 : push 전에 방문 검사

import sys
from collections import deque

input = sys.stdin.readline

# 깊이 탐색 아니면 너비 탐색?

n = int(input())
arr = [[int(x) for x in input().strip()] for _ in range(n)]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

visited = [[0] * n for _ in range(n)]

k = []
sum = 0

stack = deque()

for i in range(n):
    for j in range(n):
        if arr[i][j] == 1 and visited[i][j] != 1:
            stack.append((i,j))
            visited[i][j] = 1
            number = 1

            while stack:
                # 꺼내기
                x, y = stack.pop()

                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] == 1 and visited[nx][ny] != 1:
                        visited[nx][ny] = 1
                        number += 1
                        stack.append((nx, ny))

            if number != 0:
                k.append(number)

k.sort()
print(len(k))
for x in k:
    print(x)

마무리하면서

더 열심하자

오늘 무사히 해낸다면, 작심3일을 한번 해낸 것이겠죠??

이분 탐색(이진 탐색)

• 아이디어 : 이미 정렬된 배열에서 원하는 값을 중간값과 비교하면서 탐색
• 시간 복잡도 : O(log n)

대표적인 유형

• 정수 탐색 : 배열에서 특정 수 찾기
• 조건 만족 탐색 : 최소?, 최대?
• Lower Bound / Upper Bound: 처음/마지막 위치 찾기

사실 이분 탐색 자체는 쉬운 알고리즘이에요
그렇지만, lower_bound/upper_bound는 은근 조건식이 까다로워서 한 번 정리를 하지 않으면 못 풀겠더라고요.

경계선를 찾는 이분 탐색 (lower_bound / upper_bound)

lower_bound / upper_bound 는 단순히 최대값, 최소 값이 아니라 x 이상(>=)이 처음으로 나오는 위치와 x 초과(>)가 처음 나오는 위치이다.

해당 값으로 첫 등장 인덱스번호, 마지막 인덱스 번호, 두가지를 사용해서 값의 개수를 셀 수도 있다.

일단 각각의 표준 정의부터 알아보자

upper_bound

• upper_bound 란, target보다 큰 값이 처음으로 등장하는 인덱스
• 문제에서 “마지막으로 조건을 만족하는 값”을 찾으라고 할 때

• 예시

  arr = [1, 2, 4, 4, 4, 5]
  upper_bound(4) → 5 (마지막 4 다음 인덱스)  ```

• 조건식 패턴

  - 종료 조건 : while s < e:     
  - arr[mid] > x  →  e = mid
  - arr[mid] <= x → s = mid + 1

  lower_bound

• lower_bound 란, target과 크거나 같은 값이 처음으로 등장하는 인덱스

• 문제에서 “처음으로 조건을 만족하는 값”을 찾으라고 할 때

• 예시

  arr = [1, 2, 4, 4, 4, 5]
  lower_bound(4) → 2 (첫 번째 4의 인덱스)

• 조건식 패턴:

  - 종료 조건 : while s < e:     
  - arr[mid] >= x  → e = mid  : 해당 값이 같은 경우 처음으로 등장한 인덱수 일 수 있다.
  - arr[mid] < x → s = mid + 1
  
  

백문이 불여 일타 !!

조건식을 실제로 적용해보자

1. 단순 이분 탐색처럼 해보기

인덱스 : 0 1 2 3 4 5
값    : 1 2 4 4 4 5 

3의 upper_bound: 2 = 3보다 큰 수가 처음으로 등장한 인덱스⭐️

이분 탐색의 조건식은 보통 +-1 을 하며 mid값을 조정한다.

• arr[mid] > x → e = mid
• arr[mid] <= x → s = mid + 1

1회차 : 1 2 4 4 4 5 
       s   m     e  : 4 > 3 ==> e = m - 1

2회차 : 1 2 4 4 4 5 
       s e 
       m             : 3 > 2 ==> s = m + 1 

3회차 : 1 2 4 4 4 5 
         s,e,m        ==> 1번 인덱스가 나옴  

예상한 2가 아닌 1이 나왔다. 왜그런걸까??

1회차에서 mid값이었던 4이 3보다 큰 수 중에 처음으로 등장한 수일 수도 있었다는 사실을 간과했기 때문이다. 따라서, 비교값이 타겟값보다 큰 경우에 해당 값을 범위에서 제외하지말고 포함시키기 위해 e = mid 해야한다.

2. upper_bound에는 arr[mid] > x → e = mid를 쓰자.

1회차 : 1 2 4 4 4 5 
       s   m     e   : 3 < 4 ==> e = m

2회차 : 1 2 4 4 4 5 
       s   e
         m             : 3 >= 2 ==> s = m + 1 

3회차 : 1 2 4 4 4 5 
         s e           : 3 >= 2 ==> s = m + 1 
         m

4회차 : 1 2 4 4 4 5 
           s
           e           : 3 < 4 ==> e = m
           m

그러면 4에 대해서도 생각해보자. (값이 값은 경우)

인덱스 : 0 1 2 3 4 5
값    : 1 2 4 4 4 5 

4의 upper_bound: 5 = 4보다 큰 수가 처음으로 등장한 인덱스⭐️

따라서 이 경우에 비교값이 같은 경우에는 큰 수는 무조건 mid보다 오른쪽에 있기 때문에 s = mid + 1 연산을 한다.

초 간단 정리

• “x 이상 중 제일 작은 값” → lower_bound(x) (= 첫 위치)
• “x 초과 중 제일 작은 값” → upper_bound(x)
• “x 이하 중 제일 큰 값” → upper_bound(x) - 1 (= 마지막 위치)
• “x 미만 중 제일 큰 값” → lower_bound(x) - 1
• “x의 개수” → upper_bound(x) - lower_bound(x)

조건식 기반 경계 탐색

지금까지의 lower_bound / upper_bound는 "정렬된 배열 안에서 값의 경계"를 찾았다면,
코딩 테스트에서는 배열 원소가 아닌 조건을 만족하는 경계값을 찾는 문제도 매우 자주 나온다.
이를 흔히 파라메트릭 서치(Parametric Search)라고 부른다.

예시: 백준 2805 나무 자르기

• 절단기 높이 H를 정했을 때, 잘라낸 나무 합이 M 이상이면 "가능", 아니면 "불가능".
• 가능한 H 중 가장 큰 값을 찾는 문제 → 조건을 만족하는 경계의 마지막 위치를 찾는 것.
• 즉, 배열에서 upper_bound(x) - 1을 구하는 패턴과 똑같다.

조건식 기반 경계 탐색의 일반 구조

l, r = 0, MAX   # 탐색 범위 (예: 절단기 높이)
ans = -1
while l <= r:
    mid = (l + r) // 2
    if condition(mid):       # 조건 만족 → 더 오른쪽으로
        ans = mid            # 후보 저장
        l = mid + 1
    else:                    # 조건 불만족 → 왼쪽으로
        r = mid - 1
# ans = 조건을 만족하는 최댓값

• condition(mid) : 문제마다 정의 (ex. "잘라낸 나무 길이 >= M")
• 만족하는 값 중 가장 큰 값 → "마지막 true" → upper_bound - 1 패턴
• 반대로 "처음으로 true"가 필요하다면 → lower_bound 패턴을 쓰면 된다.

정리

• 배열 내 경계 찾기 → lower_bound, upper_bound
• 조건식 경계 찾기 → 파라메트릭 서치 (원리적으로 동일, 대상이 "배열 원소"가 아니라 "조건식")

즉,

• 첫 등장 → lower_bound 패턴
• 마지막 등장 → upper_bound - 1 패턴
• 조건 만족 최소/최대 → 파라메트릭 서치 (조건식 기반 이분 탐색)

오늘은 코테의 기본 문법인 스택, 큐, 덱의 파이썬 문법을 배우고 관련된 기본 문제들을 풀어봅시다! 

- 학습 알고리즘: 스택, 큐, 덱
- 학습 방법: 자료구조별 동작 방식 직접 구현해보기, 응용 문제로 패턴 익히기
- 풀어야할 문제:
    ❎ 1874 스택 수열 (실패! -> 주말에 ㄱㄱ)
    ✅ 9012 괄호
    ✅ 2493 탑
    ✅ 5430 AC / 3190 뱀

스택

• 선입 후출 : 나중에 들어온게 제일 먼저나간다.
• 스택은 뒤에서 꺼내면 되기 때문에 list로 사용해도 충분하다.

  stack = []
  stack.append(x) → 삽입 (push)
  stack.pop() → 삭제 (pop, 마지막 원소 반환)
  stack[-1] → top 확인
  not stack → 비었는지 확인

큐

• 선입 선출 : 제일 먼저 들어온게 제일 먼저 나간다.
• 리스트로 사용하면 앞에서 꺼내는 동작이 O(n)이라서 비효율적이다. 따라서 dequeue 를 쓴다.

from collections import deque
queue = deque()

queue.append(x) → 삽입 (뒤에 추가)
queue.popleft() → 삭제 (앞에서 꺼냄)
queue[0] → front 확인
not queue → 비었는지 확인

덱

• Deque는 양쪽 끝에서 삽입/삭제가 모두 가능하다. 따라서 큐를 쓸 떄 사용한다 ~!

from collections import deque
dq = deque()

dq.append(x) → 오른쪽 삽입
dq.appendleft(x) → 왼쪽 삽입
dq.pop() → 오른쪽 삭제  =>  스택
dq.popleft() → 왼쪽 삭제 => 큐!!
dq[0], dq[-1] → 양 끝 원소 확인

실제 문제 풀이

9012 괄호

• 풀이 링크 : [🔗 개인 노션 링크]
• 한줄 정리 :print("\n".join(r)) - 리스트를 여러줄로 간단히 출력하는 방법

5430_AC

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 :-1/1 사용하기 간단 !

2493_탑

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 형변환에 신경쓰자

마무리하면서

원래 2일차가 제일 힘들다. 
이정도면 만족 !! 아주 잘했어 !! 

생각 안나는 스택 수열은 주말로 미뤄서 이번주 내로 설명하면 굿굿 그자체 !! 

오랜만에 dequeue 문법도 정리해서 아주 좋았음 !! 굿굿

pop(), popleft() 기억하자!!

그리디 알고리즘

• 미래를 고려하지 않고, 현재 기준 가장 좋은 선택을 내리는 알고리즘, 미래에 어떤 영향을 줄지에는 고려 X, 선택하고 나면 다시 고려하지 않음

그리디 알고리즘을 적용할 수 있는 조건

1. 미래의 선택을 따져보지 않아도, 현재의 선택만으로 선택할 수 있어야한다.
2. 작은 문제들의 최적의 선택이 모여서 전체 최적의 선택이 된다. : 조금 더 풀어서 이야기하면, 문제를 부분적으로 쪼갤 수 있어야하고, 쪼갠 문제들의 최적해가 곧 전체 문제의 최적해가 된다는 것이다.

결국, 미래의 선택 고려 없이 현재만 고려해도 최적의 답을 찾을 수 있도록 정렬해야한다.

그리디와 다른 알고리즘을 비교해보자

무조건 부분해로 쪼갤 수 있으면 그리디일까?

여러 알고리즘을 공부하다보면 점점 유형 구분이 헷갈려진다. 물론 _"문제를 쪼갠다"_는 건 알고리즘의 전반적인 특성이다.

하지만 왠지 부분해라는 대목에 꽂혀서 부분해 => 그리디??라는 로직이 생겨버렸다.. 대표적으로 쪼개서 푸는 알고리즘은 그리디말고도 분할정복, 다이나믹 프로그래밍이 있다.

이 세가지 유형도 나눠서 정리하고 앞으로는 헷갈리는 일 없이 넘어가보자 !!

분할정복 : Divide & Conquer

분할정복은 기본적인 알고리즘인데 큰 문제를 작은 문제로 나눠서 해를 만드는 알고리즘 전략이다. 보통 병합으로 최종 해를 찾지만, 병합없이도 최종해를 찾을 수 있다. 대표적인 예시가 나눈 후 찾기만 하는 이분탐색이다.

계속 작은 문제로 반복해서 나누는게 핵심이다보니 보통 재귀를 사용한다

일반적으로 분할정복은 부분문제가 다른 부분문제와 독립적인 경우가 많다. 나눠진 부분문제끼리 의존적이지 않아서 독립적으로 선택할 수 있고, 해당 해를 합치기만 하면 최종해가 나오게 된다.

반대로 DP는 나눈 문제가 의존적으로 하나의 부분해가 다른 부분에 영향을 준다. 결국 의존성이 너무 크다면 DP 쪽으로 고민해볼 수 있다

그리디

그리디는 분할 정복보다는 당장 최선의 선택이 계속 이어진다고 이해하면 쉬울 것 같다. 합치는 과정없이 연속적인 선택의 결과가 최종해가 된다. 지금의 선택이 뒤의 선택에 직접적인 영향을 주고, 선택 이후에는 다시 고려하지 않는다. 해를 저장할 필요도 없다.

완전탐색와 DP, 그리디

• 완전 탐색의 방식 : 모든 경우를 계산한다.
• DP의 방식 : 최적해를 보장하기 위해 부분문제의 답을 활용하여 계산하고 저장
• 그리디의 방식 : 당장의 최적선택이 최종최적선택으로 보장되는 경우에 사용 (실무에서는 보장되지 않아도 사용 가능)

📌 그리디 vs 분할정복 vs DP 비교 표

그리디 대표 문제들

11047 동전0

• 한줄 복습 : 그리디 기본 문제 !
• 문제 풀이 : 🔗 개인노션링크

1931 회의실 배정

• 한줄 복습 : 앞서 선택한 회의와 지금 회의를 비교해서 추가, 교체하는 최선의 선택 내리기
• 문제 풀이 : 🔗 개인노션링크

11399 ATM

• 한줄 복습 : 연산식이 헷갈려서 틀렸던 문제, 수학적인 감이 부족하면 직접해보자
• 문제 풀이 : 🔗 개인노션링크

1202 보석 도둑

• 한줄 복습 : 그리디에 시간 단축을 위해 우선순위합을 사용! 최대힙으로 쓰고 싶을때는 -(넣을 값)으로 음수 변환하기, 힙큐는 힙큐 메서드로만 다뤄야 최소힙 보장⭐️
• 문제 풀이 : 🔗 개인노션링크

오늘의 최종 한마디 🌱

시간 단축을 위해서는 우선순위 힙 큐를 사용하자
특히 최소값, 최댓값을 계속해서 한 리스트에서 찾아야할때는 자료구조를 힙큐로 관리하자
힙큐는 힙큐 메서드로만 다루자. 안그러면 최소힙을 유지할 수 없다.!

열심히 했던 프로젝트를 반년이 지난 후에 읽으니 나조차 읽을 수 없었다..!!

당시에는 좋은 코드라고 생각했던 구조가 지금 보니 단점이 보였고 그렇게 깨달은 점에 대해서 적고자 한다~! ^_^

문제상황 ps. 우리 그때 로그인 과정이 어떻게 되었죠?

같이 했던 팀원님이 카카오 로그인 흐름을 물어봤는데, 당시 제 프로젝트가 소셜로그인을 한 후, 서비스 이용을 위해서는 추가 닉네임 + 회원 유형을 입력하도록 했습니다.

따라서 유저 상태가 소설로그인만 완료한 상태와 소셜로그인을 완료하고, 추가적인 정보까지 등록한 완전한 상태로 나뉘는 거죠!

이 과정은 기억이 나는데 어디서 저 유저의 상태값을 검사하고, 업데이트하는지를 전혀전혀 전혀! 찾을 수 없었습니다.

PR을 열어봐도 찾기가 어려웠음

당시 진행했던 프로젝트

카카오 부트 캠프 3단계에서 전세 사기 관련 종합 서비스를 기획하고 개발했다.

당시 프론트 3명, 백 4명이었고, 나는 백엔드 개발자로 백엔드 팀장을 맡았었다.

객체 어떻게 만들거에요??

객체를 만드는 방식에는 여러개가 있고, 우리 팀도 이를 고민했었다.

4명 모두 생각이 달랐고, 통일하는 것에도 필수다, 선택이다 논의했던것 같다. 당시 프로젝트를 봐주시던 멘토님께도 의견을 물어봤었다.

1. 서비스 코드 중간에서 직접 빌더를 사용한다.
2. 원 객체에 스태틱 메서드로 변환 매서드를 둔다.
3. 요청 객체를 매개변수로 받는 생성자를 둔다
4. 별도의 팩토리 클래스를 둔다.

4가지 방법에 대해 실제 코드를 확인하고 싶으시다면!! 관련해 팀원과 토의한 내용을 정리한 깃허브 문서

멘토님의 조언

• 통일이 필수 🔄. 1번을 제외한 어떠한 방식을 사용해도 괜찮음.
  • 멘토님은 별도의 Mapper 클래스를 만들어 변환 로직을 관리하는 것을 가장 선호한다고 하셨지만, 1번을 제외한 어떠한 방식을 사용해도 괜찮다고 하셨다. (4번과 유사)

결국 요청 객체 + 생성자를 선택했다!

계속 이야기가 길어져서 투표를 통해 요청 객체 + 생성자 를 사용하기로 결정했다.

@Entity
public class User {

    public User(JoinRequest joinRequest) {
        this.name = joinRequest.name();
        this.email = joinRequest.email();
    }
}

왜 그렇게 선택했을까요? ps. 메서드를 신뢰한다

당시에는 깊게 생각하지 않았지만, 내가 팀장을 맡고 있었고, 
내가 3번 전략을 희망해서 3번을 하게 된 이유도 있었던 것 같다.. 
(팀원들 미아내 🙏)

당시 내 판단의 이유는 이렇다.

1. 객체의 상태를 조절하고, 책임지는 주체가 생성자를 호출할 외부클라이언트가 아닌 객체가 되길 바랬다. 2. 따라서, 유저의 상태를 파악하고, 역할 ROLE을 지정하는 주체는 서비스 코드가 아니라 객체라고 생각했다. 3. 또한 이렇게 둬야지, 메서드 내부 흐름을 외부에서 신경쓰지 않아도 되는 신뢰도 있는 메서드를 구축했다고 생각했다.

당시 나는 믿고 맡기는 코드, 호출하는 메소드가 알아서 다 해주겠지! 믿고맡긴다! 너가 알아서 해~? 스타일을 선호했다.

반년이 지난 지금은요...

질문을 받았을 떄는 나조차 답변하고, 해당 위치를 찾기 너무 어려웠다. 
그렇지만 결국 찾아서 답변을 해주긴했다 😰
그런 과정에서 내 문제점 두가지를 찾았다.

프로젝트의 코드를 모두 알 수 있을까?

개발 당시에는 팀장이여서 pr을 확인하고 머지하면서 대부분의 코드를 읽고 이해하고 있었다. 하지만 시간이 지나니 코드의 정확한 위치나 역할이 기억나지 않았다.

다른 팀원들은 모든 코드를 이해하고 있었을까?? 그리고 모든 코드를 이해하는 것이 생산성측면에서 과연 도움이 되는 것일까?

나는 아니라고 생각한다.

이미 시작한 프로젝트에 합류할 수 있는 것이고, 프로젝트 크기가 점점 커지면, 모든 코드를 알 수 없을 것이다. 또한 내가 다 알고 있으니 팀원 또한 그럴 것이다라고 생각하는 것은 팀원들에게 부담을 주고, 팀 전체의 생산성 저하로 이어질 것이다.

그리고 역시 개발자의 역할은 마감기한 내 구현이지 코드 프로잭트 코드 모두 읽기는 아니니까! 

생성자에는 어떤 의미도 포함 시킬 수 없다.

setName() 메서드보다는 updateName() 매서드가 좋다는 것에는 대부분의 개발자들이 동의할 것이라고 생각한다. 메서드 명으로만 이 메서드의 역할과 결과를 유추할 수 있기 때문이다.

나또한 이렇게 생생한 메서드명으로 호출하는 개발자에게 메서드의 정보를 주고, 믿고 사용할 수 있도록 하는 구조를 선호했던 것이다.

그러나 생성자 + 매개변수 조합으로만 메서드의 역할,결과를 믿는 것은 너무 도박이다!!

오히려 감추려고 했던 의도가 반대로 작용해 이 생성자가 어디까지 담당해야하는지 매번확인하게 만든다. 결국 이것또한 생산성 저하다. 💦

추가로, 한 메소드가 완벽한 역할을 한다는 건 그만큼 유연하지 못하다는 뜻?!

어떤 메서드가 너무 완벽한, 딱딱한 역할을 가지게 된다는 것은 그만큼 유연하지 못하다는 뜻인 것 같다.

굳이 따지자면 내 코드에서는 생성자 내부에 1. 객체 생성 / 2.상태 확인 후 적절한 멤버 역할 부여 두가지의 역할이 유연하지 못하게 담겨 있었고, 한 메서드가 하나의 책임만 가져야한다는 규칙을 위배했다고도 생각한다.

과거로 돌아간다면...?

생성자 + 매개변수 전략을 유지한다면, 멤버롤을 업데이트 하는 메서드를 따로 두어 유연성을 높이고 메서드역할을 분리할 것이다. 아예 전략을 바꾼다면 스태틱메서드로 이 메서드가 어떤 유저를 만드는지 명시하고 내부에 생성자를 두는 방식을 선택할 것 같다.

지금으로서는 이런 생각이지만, 앞으로 더 많은 경험을 통해서 더 좋은 정답에 도달할 것이라고 생각하고 또 좋은 생각이 든다면 추가로 적어놓겠다

이 회고를 통해서 내가 느낀점은... ! ^_^ 👍

결국 시간이 지나고서야 내 코드의 문제점을 확인 할 수 있었다.

1. 프로젝트의 코드를 모두 알 수 없다는 점 2. 메서드에 의도와 결과를 표현하고 싶으면 메서드명으로 표현해야한다. ps. 짐작은 서로 피곤해지는 것 3. 어떤 단위로 메서드의 역할을 결정해야하는가.

또한 팀원들과 함께 우려되는 점과 의견을 더 들었다면 위 문제점을 토의중에서 발견할 수 있었지 않았을까??라는 생각도 들었다. 내가 너무 내 생각을 밀어 붙였나라는 생각도 조금은 했다.

또 나는 경력이 절대적으로 부족하니까 그만큼 늘 내 코드의 문제점과 부작용을 고민해봐야겠다는 생각을 했고, 가장 크게 깨달은 것은 시간이 지나고 다시 내 코드를 읽는 건 정말 큰 공부가 된다는 사실이다.

역시 회고는 귀찮은 것이지만 ..^^ 이만큼 가성비 있는 깨달음도 없다는 걸 다시 생각해보며.. 오늘의 회고를 마치겠다..!!

찐 찐 찐 마무리에용

마지막으로 나에게 물어봐줘서 회고의 기회를 준 우리 팀원과 나와 함께 열심히 개발했던 팀원들 모두에게 이 깨달음의 영광을 돌림니다.. ^_^