자료구조&알고리즘

• 선형 구조 비선형 구조

• 2의 보수 형식

• 부동소수점 형식

• 배열을 이용한 선형리스트 구현

• 연결 리스트(단순, 원형, 이중)

• 스택(순차, 연결 자료구조를 이용한 구현)

  • 역순 문자열
  • 시스템 스택
  • 전위, 중위, 후위 표기법

• 큐(순차, 연결 자료구조를 이용한 구현, 원형큐, 덱)

  • 운영체제 작업 큐
  • 시뮬레이션 큐잉 시스템

• 트리(순차, 연결 자료구조를 이용한 구현)

  • 포화, 완전, 편향 이진트리
  • 이진 트리 전위, 중위, 후위 순회
  • 이진 탐색 트리
  • 힙, 힙정렬
  • fenwick tree(binary indexed tree)
  • segment tree
  • 서로소 집합(union find)

• 그래프

  • 인접 행렬, 인접 리스트
  • DFS, BFS
  • 최소 비용 신장 트리
    • Kruskal, Prime
  • 그래프 점간의 최소거리 구하기
    • Dijkstra, Floyd-Warshall, Bellman-Ford

• 정렬

  • 버블, 셸, 트리
  • selection sort
  • insertion sort
  • stable, unstable sort
  • quick sort
  • radix sort
  • counting sort
  • merge sort
  • topological sort

• 검색

  • 색인 순차 검색
  • 이진 검색(binary search)
  • 해싱
    • 중간 제곱 함수, 제산 함수
    • 선형 개방 주소법(선형 조사법), 체이닝

• 동적 계획법

  • 최장 증가 부분 수열(LIS)

• 그리디 알고리즘

  • knapsack 알고리즘

• permutation, combination

• backtracking 알고리즘

• 외판원 순회 문제

• 소수 판단 문제

  • 제곱근까지 루프
  • 에라토스테네스의 체

OS

• 7 layers OSI model
• kernel mode, user mode
  • system call
• Monnolithic kernel, Microkernel
• Hypervisor(Xen, KVM, container)
• Event handling mechanisms
  • Interrupt
  • Trap, Exception
• I/O 처리 기법
  • Polling
  • Direct Memory Access
• I/O divice access 기법
  • I/O instruction
  • Memory Mapped I/O
• 프로그램이 프로세스가 되는 과정
  • compiler, linker, loader
• Dynamic Linking, Static Linking
• Process
  • code, data, heap, stack
  • context switch
  • pcb
  • Transition of process state
  • Scheduling Criteria
    • CPU 활용률
    • 처리량
    • 응답시간
    • 대기시간
    • Trunaround time
  • Scheduling Algorithms
    • FCFS
    • SJF
    • Priority
    • Round-Robin
    • Multilevel Queue
    • Multilevel Feedback Queue
  • Multi core scheduling
    • Load balancing
  • IPC
    • Shared memory
    • Pipe
    • message Queue
    • Signal
    • Socket
• Thread
  • Process와 Thread의 차이
  • Thread 구성요소
  • Multi processing, Multi threading
  • User thread, Kernel thread
  • Threading pools
  • Thread간 IPC
    • 공유 메모리 방식
• 동기화
  • Peterson Solution(mutex)
  • Semaphore
• Deadlock
  • 발생 조건
  • 해결방법
• Monitor synchronized in Java
• Dining-Philosophers Problem

DB

• Database란
• file system대신 DBMS를 사용하게 된 이유
• superkey, candidate key, primary key, foreign key
• Schema Diagram 보는법(University Database)
• Relational Algebra
  • Basic
  • Additional
• Domain Types(MySQL, ...)
• Aggregate Function
  • 뜻 : multiset of values of a coulmn of a relation에서 작동하여 값을 리턴
  • 종류
• join
• Mapping Cardinalities
  • one to one
  • one to many
  • many to one
  • many to many
• E-R model design
• index
  • dense, sparse
  • primary, secondary
  • multilevel index
• B+ tree
• Hashing for rile organization
• Hash index
  • static hashing
  • dynamic hashing
• Bitmap index
• 정규화
• Transaction
• 분산 데이터베이스
• 데이터웨어하우스
• OLAP
• Hadoop, NoSQL

컴퓨터구조

• LRU cache

네트워크

확률 통계