Skip to content

Latest commit

 

History

History
101 lines (79 loc) · 7.21 KB

기술 면접 대비.md

File metadata and controls

101 lines (79 loc) · 7.21 KB
Raw

공부 및 풀어볼 문제 링크

  1. 신입 프로그래머 기술(실무) 면접 준비(미작성)
  2. IT 면접 질문 정리
  3. it 기술 면접 질문들(수정중)
  4. 신입 개발자 기술면접
  5. Interview_Question_for_Beginner

데이터베이스

  1. PK, FK, ER 모델 :

    • PK : Primary Key, 기본키, 최소성, 유일성을 만족하며 테이블의 모든 records(tuple, row)를 식별 가능, 후보키 중 선택받은 것.
    • FK : Foriegn Key, 외부키,두 테이블을 서로 연결하는 데 사용되는 키, 데이터 무결성을 위해서도 필요함.
    • 참고할 링크
    • ER 모델 : Entity-Relation Model, 개체-관계 모델, 그래픽 형태로 개체간의 관계를 표현할 수 있음(데이터 모델 Mapping).

  2. DB의 데이터 무결성

    1. 영역 무결성 : 한 컬럼에 대해 NULL의 허용 여부, 타당한 데이터 값의 범위 등을 지정
    2. 참조 무결성 : 기본 키와 외부 키 간의 관계가 항상 유지됨을 보장. 참조되는 테이블의 행을 참조하는 키가 존재하는 한 삭제될 수 없고, 기본키도 변경 불가. 사용자의 실수로 관련 데이터가 삭제되는 것을 막아줌.
    3. 개체 무결성 : 테이블의 모든 행들이 유일한 식별자를 가짐.

  3. DBMS

    • 데이터베이스 내의 정보를 검색하거나 저장하는 등 관리하기 위한 시스템.
    • 대표적인 세 가지 기능으로 정의, 조작, 제어가 있다.
    • 정의(Definition) : DB에 저장될 자료 구조와 응용 프로그램이 그것을 이용하는 방식을 정의 (레코드 구조, 물리적 구조 등)
    • 조작(Manipulation) : 사용자가 DB에 저장된 자료를 검색, 갱신, 삽입, 삭제하는 방식을 제공
    • 제어(Control) : DB의 내용에 대한 일관성, 중복 제거, 접근 제어에 대한 기능을 지원

  4. RDBMS

    • 관계형 데이터베이스 관리 시스템, 모든 데이터를 2차원 테이블로 표현하며 상호 관련성을 가진 테이블의 집합이다. 확장이 용이하다는 장점이 있다.

  5. NoSQL

    • 분산처리 기능을 목적으로, 단순 검색 및 추가 작업을 위한 매우 최적화된 키 값 저장 공간으로, 레이턴시와 스루풋 관련하여 성능 이익을 내는 것이 목적이다.
    • 분산형 구조를 통해 여러 대의 서버에 분산해 저장하고, 특정 서버 장애 발생시 데이터 유실이나 서비스 중지가 없는 형태의 구조다.

  6. NoSQL이 RDBMS와 다른 점

    • 스키마가 없다 -> 데이터 관계와 정해진 규격(table-column의 정의)이 없다.
    • Join이 불가능하다.
    • 트랜잭션을 지원하지 않는다.
    • 분산처리(수평적 확장)의 기능을 쉽게 제공.

  7. DB Normalization

    • 데이터의 일관성 및 중복을 최소화하고 최대의 데이터 안정석 확보를 위해 테이블을 분리하는 작업.
    • 1(원자값으로 구성) -> 2(부분 함수 종속 제거) -> 3(이행 함수 종속 제거) -> BC(결정자 함수이면서 후보키가 아닌 것 제거) -> 4(다치 종속성 제거) -> 5(조인 종속성 제거)
    • 저장 공간을 최소화하고, 데이터 무결성을 유지하고, 자료구조 안정성을 최대화시키기 위한 작업.

  8. Transaction

    • 더 이상 쪼갤수 없는 하나의 작업 단위. 원자성, 일관성, 고립성, 영속성.
    • 데이터 작업시 문제가 생기면 데이터 작업을 하기 이전 시점으로 모든 데이터를 원상 복구하는 것을 말함.

  9. Commit, Rollback

    • Commit : 쿼리문을 수행한 후 그 결과에 대해 작업을 확정짓겠다는 의미
    • Rollback : 쿼리문 수행 결과에 대해 번복을 하기 위해 원상복귀 하겠다는 의미

  10. Join이 무엇인지에 대한 설명

    • Inner Join : 2개 이상의 테이블에서 교집합만을 추출
    • Left Join : 2개 이상의 테이블에서 from에 해당하는 부분을 추출
    • Right Join : 2개 이상의 테이블에서 join하는 테이블에 해당하는 부분을 추출

자료구조 & 알고리즘

  1. Red Black Tree

    • BST를 기반으로하는 트리 형식의 자료구조.
    • search, insert, delete에 O(log N). 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어다. complete binary tree
    • 다음의 정의를 만족해야 한다.
      1. 각 노드는 red or black 색깔을 갖는다
      2. Root node의 색깔은 black 이다.
      3. 각 leaf node는 balck이다.
      4. 어떤 노드의 색깔이 red라면 두 개의 children 색깔은 모두 black이다.
      5. 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다.
        • Black-Height : 노드 x로부터 노드 x를 포함하지 않은 leaf node까지의 simple path 상에 있는 black nodes의 개수
    • 특징
      1. BST의 특징을 모두 갖는다.
      2. Root node부터 leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. 이러한 상태를 balaced 상태라고 한다.
      3. 노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL 들을 leaf node로 간주한다.
    • RBT는 BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조다.
      • BST는 편향 트리로 구성될 때 O(n)의 탐색 속도를 갖게 되며, 배열에 비해 탐색의 장점을 가지려했더만 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다.
      • 이를 해결하기 위한 Rebalancing 기법중 하나가 RBT다.
    • 삽입 : BST의 특성을 유지하며 노드의 색깔을 RED로 지정한 뒤 삽입. 삽입 결과 RBT 특성 위배시 노드의 색깔을 조정하고, Black-Height가 위배되었다면 rotation을 통해 height를 조정한다. 이 과정을 통해 RBT의 동일한 height에 존재하는 internal node들의 Black-Height가 같아지게 되고, 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지된다.
    • 삭제 : BST의 특성을 유지하며 노드를 삭제한다. 삭제될 노드의 child 개수에 따라 rotation 방법이 달라진다. 만약 지워진 노드의 색깔이 Black이라면 Black-Height가 1 감소한 경로에 balck node가 1개 추가되도록 rotation하고 노드의 색깔을 조정한다. 지워진 노드의 색깔이 red라면 위배되지 않으므로 RBT가 그대로 유지된다.

  2. AVL

  3. B-Tree

  4. Hash Function

  5. Minimun Spanning Tree

  6. Kruskal Algorithm

  7. Prim Algorithm

  8. Dijkstra Algorithm

프로그래밍 기본

  1. C 언어와 C++ 언어의 차이점 *