programming

(면접) IT 기술면접 준비

limmmmm 2023. 1. 17. 14:42
반응형
반응형

# 자료구조

# OS

1. 자료구조

1.1. 스택

  • 바구니에 위에서 물건을 담는다고 하면 됨
  • 먼저 넣은놈을 맨 마지막에 꺼냄(FILO)

1.2. 큐

  • 파이프에 물건을 넣는다고 하면 됨
  • 먼저 넣은놈을 처음으로 꺼냄(FIFO)

1.3. 힙

  • 최소 또는 최대 이진탐색트리
  • 삽입 : 리프노드에 삽입 후 부모노드와 비교하여 정렬
  • 삭제 : 루트노드와 리프노드의 위치를 변경한 후 리프노드 삭제 후 정렬

1.4. 이진탐색트리

  • 왼쪽노드 < 부모노드 < 오른쪽노드
  • 한쪽으로 편향될 수 있기 때문에 시간복잡도가 O(logN) ~ O(N)임

1.5. 자가균형트리

  • 이진탐색트리가 한쪽으로 편향되는걸 방지하기 위한 트리
  • AVL, RedBlack Tree가 있음

1.6. 해시

  • Key-Value로 이루어짐
    ex) 1~10까지 있을 때 10으로 나누어 나머지를 비교하여 저장
  • 충돌이 일어날 가능성이 있음
  • 충돌회피기법으로는 Open Address, Chaining이 있음
    • Open Address : 메모리에 자리가 차있으면 다음으로 넣음
    • Chaing : 연결리스트로 저장

1.7. 그래프

  • Vertex(노드), Edge로 이루어짐
  • 표현방식 : 인접행렬(0, 1..), 인접 리스트가 있음
  • 그래프 순회 : 노드 방문(?)으로 이해하면 되고, preorder, inorder, postorder가 있음
    • preorder : 자기자신 -> 자식
      ex) F-B-A-D-C-E-G-I-H
    • inorder : 자식 -> 자기자신 -> 자식
    • postorder : 자식 -> 자기자신
      ex) C-E-D-A-B-H-I-G-F

1.7.1. DFS(깊이 우선 탐색)

  • 깊이를 우선적으로 탐색
    ex) F-B-A-D-C-E-G-I-H

1.7.2. BFS(너비 우선 탐색)

  • 옆으로(층) 탐색
    ex) F-B-G-A-D-I-C-E-H

1.7.3. DAG

  • 방향이 있는 그래프

1.7.4. 대표적인 탐색 알고리즘

  • BellmanFord(벨만포드) 알고리즘
    • 모든 Edge를 탐색하면서 출발지와 현재까지의 오는 거리를 계산
    • O(N^3)
  • Dijkstra(다익스트라) 알고리즘
    • 최소 비용을 확인하면서 거리를 계산
    • 음의 값이 존재하면 안됨
    • 피보나치 heap을 사용하였을 경우 O(N^2)의 시간이 걸림

2. OS

  • 폰노이만 구조 참고
  • 메모리(RAM) 구조 : 코드(소스코드), 데이터(변수), 스택(함수), 힙(동적메모리)
  • CPU 스케줄링
    • 선점형 : 고정되지 않고 가변적이라고 생각하면 됨, 조건에 맞는 프로세스가 선점하여 동작함
      • SRF : 잔여시간 짧은 순
      • RR(라운드 로빈) : 타이머 설정해서 바꿔가면서 선점(타이머를 너무 길게 설정하면 비선점과 동일, 프로세스가 바뀔 때 비용(소요시간 등)이 발생하기 때문에 너무 짧게 선정하면 역효과가 나타날 수 있음)
      • 우선순위 : 우선순위 정해서 선점
    • 비선점형 : 실행되는 프로세스가 끝날때까지 기다렸다 실행
      • FCFS : 먼저 들어간 프로세스 먼저 처리
      • SJF : 실행 시간 짧은 순 먼저

2.1. 데드락(교착상태)

  • 프로세스가 자원을 얻지못해 다음작업을 진행하지 못하는 상황
    ex) A와 B 프로세스가 있다고 할 때, A는 B가 끝나길 기다리고, B는 A가 끝나길 기다리는 무한대기 상황
  • 4가지 조건이 필수로 성립해야 함 : 상호배재, 점유대기, 순환대기, 비선점

2.2. 경쟁상태(Race Condition)

  • 공유 자원에 여러 프로세스가 접근하는 상황

2.3. 문맥교환(Context Switching)

  • 현재 CPU를 사용중인 프로세스의 CPU 제어권을 다른 프로세스로 넘기는 과정

3. 프로그래밍 관련

3.1. 절차지향과 객체지향의 차이

  • 절차지향은 순차적으로 실행되는 프로그램이며 C언어가 가장 대표되는 언어이고, 객체지향은 다수의 객체를 만들어 상호작용 하도록 만드는 프로그램이며 JAVA가 가장 대표되는 언어
    • 절차지향 : 청소할 때 눈앞에 보이는 순으로 청소
    • 객체지향 : 청소할 때 사람을 구역별로 나누어 청소

3.2. 탐욕 알고리즘(그리디 알고리즘)

  • 최적해를 구하는데에 사용되는 방법이며, 경우의 수 중 하나를 결정해야할 때마다 최적이라고 생각되는 것을 선택하는 방법

3.3. 프로세스와 스레드의 개념

  • 프로세스는 실행되는 프로그램 단위이고, 스레드는 프로그램 안에서 실행되는 흐름 단위
  • 프로세스 내의 스레드 끼리는 자원을 공유함
    • 프로세스 : 게임
    • 스레드 : 게임 스킬, 상점 ...

4. 기타

4.1. 분산처리와 병렬처리의 차이

  • 병렬처리 : 여러 가지의 일을 동시에 실행되게끔 만드는(시분할)
  • 분산처리 : 하나의 일을 다른 컴퓨터로 보내서 처리하게 만든 후 결과를 수집

기본적인 개념만 다루고 있으니 참고용으로 보시면 되고, 틀린부분있으면 말씀해주세요!

반응형