TIL (Today I Learned)

TIL_230327-0401

남 희 2023. 4. 2. 17:20
더보기

3월 27일 (월)

  • CS 스터디 진행 - 자료구조
  • 채용 설명회 참여

3월 28일 (화)

  • 알고리즘 풀이 및 피드백 - 완전 탐색

3월 29일 (수)

  • CS 스터디 진행 - 데이터베이스
  • CS 스터디 복습 - 운영체제
  • 프로젝트 경험 정리

3월 30일 (목)

  • 알고리즘 풀이 및 피드백 - 구현
  • CS 스터디 진행 - 데이터베이스
  • 직무 면접 대비 연습

3월 31일 (금)

  • 프로젝트 코드 리뷰 및 PR 완료
  • CS 스터디 복습 - 디자인 패턴 (싱글턴, 이터레이터 손코딩)

4월 1일 (토)

  • 알고리즘 풀이 및 피드백 - 완전탐색

1️⃣ 자료 구조 : 이진트리 (Binary Tree)

트리 (Tree)

Directed Acyclic Graph(방향성이 있는 비순환 그래프)의 한 종류. 노드 N개라면 항상 간선 N-1개.

이진트리 (Binary Tree)

자식 노드 수가 2개 이하인 트리
  • 정이진트리 (Full Binary Tree) : 자식 노드 수 0 or 2
  • 변질 이진 트리 (Degenerate Binary Tree) : 자식 노드 수 1
  • 완전 이진 트리 (Complete Binary Tree) : 왼쪽부터 채워져 마지막 레벨을 제외하고 완전히 채워진 트리.
  • 포화 이진 트리 (Perfect Binary Tree) : 리프 노드 제외 자식 노드 수가 모두 2. 리프 노드 수가 해당 레벨 최대 수 만족.
  • 균형 이진 트리 (Balanced Binary Tree) : 왼쪽, 오른쪽 노드의 높이 차가 1 이하.

 

이진 탐색 트리 (Binary Search Tree)

노드의 오른쪽 하위 트리는 '노드보다 큰 값', 왼쪽 하위 트리는 '노드보다 작은 값'이 들어 있는 트리.
  • 평균 O(logN)
  • 최악 O(N), 한쪽으로만 노드가 몰리는 경우 (선형적 트리)
  • 저장된 값이 같더라도 들어오는 순서가 다르면 이진 탐색 트리 모습이 달라질 수 있음.

 

AVL 트리 (Adelson-Velsky and Landis Tree)

선형적 트리가 되는 것을 방지하고 '스스로 균형을 잡는' 이진 탐색 트리
  • 균형 이진 트리 모습을 유지, 만족
  • 평균 & 최악 모두, 탐색 & 삽입 & 삭제 O(logN)
  • 삽입, 삭제 시 높이 균형 성질이 무너지기 때문에 이때 회전(Rotation) 동작 실행. 

 

AVL 트리 회전

원래 z가 root인 부분 트리를 b를 root로 하는 새로운 부분 트리로 바꾸는 것
a가 b의 왼쪽 자식 T0, T1은 a의 왼쪽, 오른쪽 자식
c가 b의 오른쪽 자식, T2, T3는 각각 c의 왼쪽, 오른쪽 자식
  • x, y, z : 자식 노드, 부모 노드, 할아버지 노드
  • a, b, c : x, y, z를 inorder순으로 나열한 것
  • T0, T1, T2, T3 : x, y, z의 부분 트리를 inorder순으로 나열한 것
  • Single rotation : b = y일 때, y를 z와 회전시키는 것처럼 보이기 때문
  • Double rotation : b = x일 때, x를 y와, 그리고 다시 z와 회전시키는 것처럼 보이기 때문

 

레드 블랙 트리 (Red-Black Tree)

각각 노드가 레드 또는 블랙 색상 속성을 가지고 있는 자기 균형 이진 탐색 트리.
  • 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트 저장. 이를 이용해 균형 유지.
  • 평균 & 최악 모두, 탐색 & 삽입 & 삭제 O(logN)

 

유효한 레드 블랙 트리 조건

  1. Node = Red or Black
  2. Root Node = Black
  3. Leaf Node = Black
  4. Red Node Child = Black
  5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드까지 도달하는 모든 경로에는 리프 노드 제외해 모두 같은 개수의 Black Node 존재.

 

2️⃣ 자료 구조 : 힙 (Heap)

완전 이진 트리 기반 자료 구조. 루트 노드에 있는 키는 모든 자식에 있는 키 중 최적값.
  • 최대 힙 : 루트 노드 키가 모든 키 중 최대 값.
  • 최소 힙 : 루트 노드 키가 모든 키 중 최소 값.

  • 삽입 과정
    1. 힙에새로운 요소가 들어오면 마지막 노드에 삽입
    2. 새로운 노드를 부모 노드와 크기를 비교해 힙의 성질을 만족할 때까지 swap
  • 삭제 과정
    1. 최댓값인 루트 노드 삭제
    2. 마지막 노드를 루트 노드로 올림
    3. 루트 노드에서 아래로 내려가면서, 힙의 성질 만족할 때까지 swap

 

3️⃣ 자료 구조 : 우선순위 큐 (Priority Queue)

높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료 구조.
같다면 순서에 의해 처리.
  • 힙을 기반으로 구현 가능. (하지만 다른 방법으로도 구현될 수 있음. 힙 /= 우선순위 큐)
  • 최소 지원 연산
    • insert_with_priority : 하나의 원소를 우선순위를 지정해 큐에 추가
    • pull_highest_priority_element : 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환

 

 

4️⃣ 자료 구조 : 맵, 셋, 해시 테이블 (Map, Set, Hash Table)

연관 배열 (Associative Array)

키 하나와 값 하나가 연관되어 있으며, 키를 통해 연관되는 값을 얻을 수 있는 자료 구조

맵 (Map)

키와 매핑된 값의 조합으로 형성된 자료 구조
  • 키와 데이터를 같이 저장
  • 키에 대한 중복은 없음

셋 (Set)

맵과 유사하나 고유한 요소를 저장하는 자료 구조
  • 중복을 허용하지 않는다.

 

해시 테이블 (Hash Table)

무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
  • 해시 함수를 사용해 색인을 버킷이나 슬롯의 배열로 계산
  • 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도

 

각 자료구조는 언어별로 구현 세부 사항이 다르므로 참고.

 

 

5️⃣ DB : 용어

  • 필드(Field) : 속성
  • 레코드(Record) or 튜플(Tuple) : 테이블에 쌓이는 행
  • 관계 : 1:1, 1:N, N:M 관계가 있으며, 화살표로 나타낼 수 있음. 0 포함이냐 아니냐에 따라 화살표 표기가 달라짐.
  • 키(Key) : 테이블 간의 관계를 좀 더 명확하게 하고 테이블 자체 인덱스를 위해 설정된 장치

 

키 (Key)

  • 유일성 : 해당 필드의 값들은 모두 달라야 함. 유일해서 데이터 식별 가능.
  • 최소성 : 최소한의 속성들로 구성.
  • 기본키(Primary Key, PK) : 유일성과 최소성을 만족하는 키. 자연키 또는 인조키 중 골라 설정.
  • 자연키 : 원래 데이터에서 유일한 값이 있어서 뽑을 수 있는 키, 언젠가 변할 수도 있음. (예 : 전화번호)
  • 인조키 : 인위적으로 생성한 키. 보통 인조키가 기본키가 됨. (예 : 유저 아이디)
  • 외래키(Foreign Key, FK) : 다른 테이블의 기본키를 그대로 참조한 값. 개체와의 관계 식별에 사용. 중복 허용.
  • 후보키(Candidate Key) : 유일성과 최소성 만족. 기본키가 될 수도 있는 후보들. 대체키와 기본키 모두 포함.
  • 대체키(Alternate Key) : 후보키가 2개 이상일 경우, 하나를 기본키로 지정하면 나머지가 모두 대체키.
  • 슈퍼키(Super Key) : 유일성을 갖춘 키. 각 레코드를 유일하게 식별할 수 있는 키.

 

 

6️⃣ DB : ERD (Entity Relationship Diagram)

릴레이션 간 관계들을 정의한 구조도
  • 데이터베이스 구축 시, 가장 기초적 뼈대
  • 관계형 구조를 표현할 수 있는 데이터를 구성하는 데 유용.
  • 비정형 데이터는 충분히 표현할 수 없다.

 

7️⃣ DB : 정규화 (Normalization)

릴레이션 관계가 잘못 표현되어 데이터베이스 이상 현상이 발생한 것을 해결하는 과정 or
저장 공간을 효율적으로 사용하기 위해 릴레이션을 여러 개로 분리하는 과정

이상 현상

  • 갱신 이상 : 반복된 데이터 중 일부를 갱신할 시 데이터 불일치 발생.
  • 삽입 이상 : 불필요한 정보를 함께 저장하지 않고는 정보 저장이 불가능.
  • 삭제 이상 : 필요한 정보를 함께 삭제하지 않고는 정보 삭제가 불가능.

정규형 원칙

  1. 자료 중복성 감소
  2. 독립적 관계는 별개의 릴레이션으로
  3. 각 릴레이션은 독립적 표현 가능

제1 정규형

모든 도메인이 더 이상 분해될 수 없는 원자 값만으로 구성
  1. 어떤 테이블에 속한 모든 도메인이 원자 값만으로 구성
  2. 모든 속성에 반복되는 그룹 X
  3. 기본키를 사용해 관련 데이터 집합을 고유하게 식별

제2 정규형

제1 정규형 + 부분적 함수 종속을 제거한 형태
  • 부분적 함수 종속 : 릴레이션에서 종속자가 "기본키가 아닌 다른 속성에 종속"되거나, 기본키를 구성하는 "여러 속성들의 부분집합 중 일부분에만 종속"

제3 정규형

제2 정규형 + 기본키가 아닌 모든 속성이 이행적 함수 종속이 없는 형태
  • 이행적 함수 종속 : A -> B, B -> C 존재 시, 논리적으로 A -> C가 성립. 이때 C가 A에 이행적으로 함수 종속되었다 함

보이스/코드 정규형 (BCNF)

제3 정규형 + 결정자가 후보키가 아닌 함수 종속 관계를 제거해 릴레이션의 함수 종속 관계에서 모든 결정자가 후보키인 상태

 

 

 

참고 자료

 

'TIL (Today I Learned)' 카테고리의 다른 글

TIL_230405  (0) 2023.04.06
TIL_230403  (0) 2023.04.03
TIL_230323-0324  (0) 2023.03.24
TIL_230321-0322  (0) 2023.03.22
TIL_230320  (0) 2023.03.20

'TIL (Today I Learned)'의 다른글

  • 현재글TIL_230327-0401

관련글

티스토리툴바