모의면접 키워드 정리 2021-11-04

해시함수 : 입력값과 출력값, 암호화 기법, 키값

• 출력값을 통해 입력값을 알 수 있으면 안된다.
• 암호화 기법으로, 키값을 출력한다.

 

 

해시 충돌 해결 기법

1. 체이닝 : 연결리스트

• 해시 충돌이 발생하면 버킷에 연결리스트로 데이터를 연결한다.
• 연결리스트가 길어질수록 성능 저하
• (Closed Addressing)

 

2. 개방 주소법(Open Addressing) : 다른 버킷에 삽입

• 해시 충돌이 일어나면 다른 버킷에 데이터를 삽입한다.

*해시 충돌 : 서로 다른 (두 개의) 입력값에 대해 동일한 출력값을 내는 상황

 

 

 

분할 정복 알고리즘의 종류 : Merge sort, Quick sort

합병 정렬 : stable sort, 데이터를 절반의 크기로 분할

퀵 정렬 : unstable sort, 피벗(중앙값에 가까울수록 성능 우수)을 기준으로 데이터 분할

 

 

 

트리 vs 그래프 (사이클, 루트노드, 방향)

트리 : 사이클 허용X, 하나의 루트노드, 하나의 경로(한 방향)

그래프 : 사이클 허용, 루트노드X, 단방향 및 양방향

* 이진트리 : 자식 노드가 최대 2개

 

 

트리 순회기법

선위 순회 : 루트 먼저, 루트 노드 --> 왼쪽 노드 --> 오른쪽 노드

중위 순회 : 중간에 루트, 왼쪽 노드 --> 루트 노드 --> 오른쪽 노드

후위 순회 : 마지막에 루트, 왼쪽 노드 --> 오른쪽 노드 --> 루트 노드

 

 

이진트리

완전 이진트리 : 포화 이진트리에서 오른쪽 leaf node부터 제거한 트리

포화 이진트리 : leaf node를 제외한 모든 노드가 자식노드 2개를 가진 트리

 

 

 

DFS의 성능

DFS : 재귀로 구현, 함수호출 시 반복문보다 성능이 느림

 

 

 

TCP vs UDP 

TCP : 흐름제어, 혼잡제어로 신뢰성 보장, 전송속도 느림, 메일

UDP : 신뢰성 보장X, 패킷 손실 가능, 전송속도 빠름, 실시간 동영상