모의 면접

1. 지수 백오프 알고리즘이란

• 네트워크 상에서 일시적인 오류가 발생했을 때, 재시도 간격을 점진적으로 늘려가며 재시도를 수행하는 알고리즘
• 서버가 과부하 상태일 때 과도한 요청을 방지하기 위해 사용
• 핵심: 지수적으로 대기 시간을 늘리는 것(양의 크기에 비례하는 비율로 대기 시간을 늘리는 것)
• 장점: 재시도 폭주를 방지하고 네트워크와 서버의 부하를 줄이는 데 큰 도움을 줌, 과도한 요청으로 인한 비용 증가를 막을 수 있음, 서버와 클라이언트 사이의 트래픽을 더 효과적으로 관리가 가능

2. 이진 트리와 이진 탐색 트리(BST)의 차이점

• 이진 트리: 자식노드가 최대 2개인 노드들로 구성된 트리
• 이진 탐색 트리: 이진 트리 기반의 탐색을 위한 자료구조, 정렬된 트리, 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 지닌 노드들로 구성, 오른쪽 서브 트리는 해당 노드이 값보다 큰 값을 지닌 노드들로 구성

3. DB에서 index 는 무엇이며 왜 사용하는지

• DB의 index: 추가적인 쓰기 작업과 저장 공간을 활용하여 DB Table의 검색 속도를 향상시키기 위한 자료구조

• 검색 속도 향상, 조인 성능 향상, 정렬된 결과를 반환할 때

3-1. 언제 사용하며 어떻게 구현하는지

• 검색을 많이 해야될 때
• ORDER BY, GROUP BY 연산을 사용할 때
• JOIN 연산을 사용할 때
• 특정 범위의 데이터를 검색할 때

3-2. 그럼 모든 컬럼에 대해 index를 설정할 수 있는지

• 할 수는 있지만 권장하지는 않음
• 불필요한 오버헤드를 초래할 수 있고 인덱스의 크기가 커지면 공간을 낭비함
• 인덱스의 삽입, 수정 시 성능 저하가 발생할 수 있음

4. SQL과 NoSQL은 어떤 차이가 있는지, SQL과 NoSQL을 어떤 경우에 사용하는지

• SQL: RDBMS, 미리 정의된 스키마가 있는 구조화된 데이터에 적합, 행열이 있는 테이블에 데이터 저장, 트랜잭션 관리를 위해 ACID속성을 따름, JOIN 및 복잡한 쿼리 지원, 정규화된 데이터 구조를 사용, 대량의 데이터를 처리하기 위해 수직 확장 필요

• 복잡한 쿼리 및 트랜잭션 관리가 필요한 애플리케이션에 사용

• NoSQL: 비관계형 DBMS, 비정형 및 반정형 데이터에 적합, 데이터 컬렉션 또는 문서에 저장, 반드시 ACID를 따르지 않음, JOIN 및 복잡한 쿼리를 지원하지 않음, 비정규화된 데이터 구조를 사용, 대량의 데이터를 처리하기 위해 수평 확장을 사용

• 웹 애플리케이션 및 모바일 앱과 같이 높은 성능과 확장성이 필요한 애플리케이션에 사용

5. 가장 좋아하는 정렬 알고리즘, 그 이유와 해당 알고리즘의 동작 방식

• 분할 정복, 힙 정렬: 최악, 최적, 평균 시간복잡도가 같다.(항상 비슷한 퍼포먼스 유지가 가능)

• 가장 작은 단위까지 분할을 한 뒤 결합과정에서 정렬을 하는 방법
• 오름차순 기준 최대 힙 속성을 충족하는 배열에서 루트와 마지막 노드의 값을 바꾸고 마지막 노드를 제외한 나머지 노드를 힙 속성을 복원 이를 반복

6. 도서관에 대한 정보를 저장하는 웹 사이트를 개발한다고 하고 각 도서에 대한 정보를 담는 자료구조를 만들 때, 어떤 자료구조를 왜 사용할 것인지
해시 테이블

7. 정렬 알고리즘에서 일반적으로 가장 빠른 알고리즘 설명

• 퀵 정렬
• 분할 정복을 기반으로 하는 정렬 알고리즘, 평균적으로 매우 빠른 속도를 가지고 여러 알고리즘 중에서 가장 효율적인 알고리즘 중 하나로 알려져 있음
• 기준으로 삼을 배열의 하나의 원소를 피벗이라 함
• 피벗을 기준으로 피벗보다 작은 값은 피벗의 왼쪽, 큰 값은 오른쪽으로 이동시키고 피벗을 중심으로 두 부분으로 분할
• 나눠진 부분을 재귀적으로 위 과정을 반복
• 부분 배열이 모두 정렬되면 이를 결합해서 결과를 도출
• 평균적으로 O(nlogn), 최악의 경우 O(n^2)의 시간복잡도

• 최악의 경우
• 이미 정렬된 데이터를 사용할 경우
• 피벗만 제자리를 잡고 나머지 모든 데이터가 하나의 부분 배열로 분할되는 경우
• 피벗이 배열의 항상 최댓값 또는 최솟값이 되는 경우

8. 논리적 설계와 물리적 설계에 대해서 상세히 설명

• DB의 설계 단계: 요구사항 분석 - 개념적 설계 - 논리적 설계 - 물리적 설계 - 구현

• 개념적 설계(정보 모델링, 개념화)
  현실 세계의 무한성과 계속성을 이해하고, 다른 사람과 통신하기 위해 현실 세계에 대한 인식을 추상적 개념으로 표현하는 과정
  개념 스키마 모델링과 트랜잭션 모델링을 병행 수행
  요구 분석 단계에서 나온 결과인 요구 조건 명세를 DBMS에 독립적인 E-R 다이어그램으로 작성
  DBMS에 독립적인 개념 스키마 설계

• 논리적 설계(데이터 모델링)
  현실 세계에서 발생하는 자료를 컴퓨터가 이해하고 처리할 수 있는 물리적 저장장치에 저장할 수 있도록 변환하기 위해 특정 DBMS에 지원하는 논리적 구조로 변환하는 과정
  개념적 설계를 통해 나온 데이터 타입과 이 데이터 타입들 간의 관계로 표현되는 논리적 구조의 데이터를 모델화
  개념 스키마를 평가 및 정제하고 DBMS에 따라 서로 다른 논리적 스키마를 설계하는 단계
  트랜잭션의 인터페이스 설계
  RDB에서는 테이블을 설계하는 단계

• 물리적 설계(데이터 구조화)
  논리적 설꼐를 통해 나온 논리적 구조로 표현된 데이터를 디스크 등의 물리적 저장장치에 저장할 수 있는 물리적 구조의 데이터로 변환하는 과정
  DB파일의 저장 구조 및 엑세스 경로를 결정
  저장 레코드의 형식, 순서, 접근 경로와 같은 정보를 사용하여 데이터가 컴퓨터에 저장되는 방법을 묘사

9. SQL에서 JOIN에 대해서 상세히 설명

• 복수의 테이블을 엮어서 원하는 데이터를 추출하고 싶을 때 사용
• INNER JOIN: 교집합, 두 테이블에 데이터가 모두 있는 것만 join
• LEFT JOIN(RIGHT JOIN): 왼쪽 혹은 오른쪽 테이블을 기준으로 join, 왼쪽 기준 오른쪽 데이터가 없으면 NULL로 처리하여 join
• OUTER JOIN: 합집합, 두 테이블 중 한 테이블이라도 있는 데이터를 모두 join

10. 퀵 정렬 알고리즘에서 최악의 시간복잡도를 방지하기 위한 방법

• 랜덤화: 배열의 랜덤한 두 개의 index를 바꾸어 배열이 정렬되어 있지 않도록 하는 방법
• 랜덤 기준점 선택: 피벗을 특정 인덱스가 아닌 난수를 사용하여 결정하는 방법
• Midian Of Three Pivot: 세 개의 후보를 중 중간값을 피벗으로 하는 방법