CS - 1 (자료구조, 데이터베이스)

Data Structure

• 스택 Stack
  • LIFO 후입선출
  • 함수의 콜스택, 문자열 역순 출력, 후위표기법
  • 스택 포인터, push, pop isEmpty, isFull
• 큐 Queue
  • FIFO 선입선출
  • 버퍼, BFS
  • front, rear, enQueue, deQueue, isEmpty, isFull
• 원형 큐
  • 큐 공간 전부를 사용할 수 있도록 1자리를 항상 비워둠
• 연결 리스트 큐
  • 배열로 구현된 원형 큐의 크기제한을 개선하여 크기제한이 없고 삭제가 편리함
• 우선순위 큐
  • 큐에 우선순위를 도입한 것으로 힙으로 구현하는 것이 가장 효율적
  • 시뮬레이션 시스템, 작업 스케쥴링, 수치 해석 계산
• 힙 Heap
  • 완전 이진 트리의 일종으로 중복된 값을 허용함
  • 최댓값과 최솟값을 빠르게 찾아낼 수 있음
  • 반 정렬 상태
  • 최대힙, 최소힙
• 트리 Tree
  • 노드와 엣지로 이루어진 자료구조
  • 사이클이 존재할 수 없으며, 사이클이 존재하면 그래프
  • 노드 N개, 간선 N-1개를 만족
  • 전위 순회, 중위 순회, 후위 순회, 레벨 순회으로 순회가능
• 이진탐색트리 BST Binary Search Tree
  • 탐색 빅오 O(logN)
  • 효율적인 탐색 능력을 가지고 있으며, 자료의 삽입/삭제도 가능
  • 각 노드 자식이 2개이하, 중복 노드 X, 왼쪽 자식이 부모보다 작음을 만족
  • 중위 순회로 순회
• 해시 Hash
  • 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
  • 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해
  • 언제나 동일한 해시값 리턴, 인덱스를 알면 검색이 빠름
  • 해시값 충돌
    • 체이닝: 연결리스트로 노드 추가
    • 오픈 어드레싱: 다른 주소에 데이터를 저장할 수 있도록
    • 선형탐사, 제곱탐사

Database

KEY : 검색, 정렬 시 튜플을 구분하는 기준 속성

• 후보키
  • 튜플을 유일하게 식별하기 위해 사용하는 속성들의 부분 집합
  • 유일성 : Key 로 하나의 튜플 식별가능
  • 최소성 : 꼭 필요한 속성으로만 구성
• 기본키 Primary Key
  • 후보키 중 선택한 main key
  • NOT NULL
  • 값 중복 X
• 대체키
  • 후보키 중 기본키를 제외한 나머지 키
• 외래키
• 다른 릴레이션의 기본키를 참조하는 속성의 집합
• 슈퍼키
  • 유일성은 만족하고, 최소성은 만족하지 못하는 키

정규화

• 데이터를 중복을 줄이고, 무결성을 향상시키는 이상현상을 없애는 과정
• 1NF : 원자값을 갖도록 테이블을 분리
  2NF : 모든 column이 완전 함수적 종속을 만족하기 위해 테이블 분리
  3NF : 이행적 종속을 없애기 위해 테이블 분리
  BCNF : 모든 결정자가 후보키
  4NF : 다치 종속 제거
  5NF : 조인 종속 제거

트랜잭션

• 데이터베이스의 상태를 변화시키기 위해 수행하는 작업단위

• 원자성, 일관성. 독립성, 지속성

  
  
  
  

  참고 : https://github.com/gyoogle/tech-interview-for-developer