대학원 면접 질문 대비 (자료구조 / 네트워크 / DB / 전공지식)

• C언어와 객체지향언어의 차이점
  
  C언어는 절차지향언어로 객체를 순차적으로 처리해야 하며, 프로그램 전체가 유기적으로 연결되어 있어야 함.
  실행속도가 빠르다는 장점이 있지만, 비효율적이며, 유지보수가 어렵다는 단점이 있음
  
  객체지향언어는 객체 간 상호작용이 가능하며, 캡슐화, 추상화, 상속, 다형성의 특징이 있음.
  자바, 파이썬, C++등이 해당함.
  
  캡슐화는 데이터와 알고리즘을 하나의 캡슐로 만드는 것이며, 외부에서 데이터와 코드의 형태를 알 수 없음
  추상화는 프로그램을 만드는데 필요한 공통적인 부분만 추출하고 필요하지 않은 부분을 제거하는 것 (인터페이스와 구현을 분리)
  상속은 상위클래스의 모든 것을 하위 클래스가 이어 받는 것
  다형성은 상속과 연관된 개념으로 하나의 객체가 다른 여러 객체로 재구성되는 것
  
  
  
• 트랜잭션의 특징과 각각의 의미 (ACID)
  
  트랜잭션은 데이터베이스에서 여러 작업을 하나의 논리적 단위로 묶는 것으로, 데이터의 일관성과 무결성을 유지하기 위해 설계됨. 트랜잭션의 특징은 4가지 속성(ACID)으로 요약됨.
  
  원자성(Atomicity)
  트랜잭션 내 모든 연산이 완벽하게 완료되거나, 전혀 실행되지 않아야 함.(All-or-Noting) (ex.은행 이체)
  모든 작업이 반영되거나, 모두 롤백(roll-back)되는 특성
  
  일관성(Consistency)
  데이터가 미리 정의된 규칙에서만 수정이 가능한 특성으로, 무결성 제약 조건이 준수되어야 함을 의미함.
  
  독립성(Isolation)
  여러 트랜잭션이 동시에 실행될 때 각 트랜잭션이 서로 영향을 주지 않도록 보장하는 특성을 의미함. (동시성 제어)
  
  지속성(Durability)
  트랜잭션이 완료된 후 그 결과가 영구적으로 저장되어야 함.
  
  
  
•  IP / TCP / UDP
  
  IP (Internet Protocol)
  OSI 7계층 중 3계층(Internet 계층)에 해당.
  컴퓨터 간 통신규약으로 발신지부터 수신지까지의 라우팅 경로를 결정
  비연결성 (패킷을 받을대상이 없거나 서비스 불능상태여도 패킷 전송)이며, 비신뢰성 (패킷소실 및 패킷 전달순서 보장 못함)임.
  
  TCP (Transmission Control Protocol)
  OSI 7계층 중 4계층(Transport)에 해당.
  연결형 프로토콜로 보장된 패킷을 전달하여 신뢰성이 높다는 장점이 있으며, 연결을 위한 초기 설정 시간이 소요된다는 단점이 있음. (ex. 메일, FTP, SMTP, HTTP)
  3-way handshake과정을 활용함 (SYN → SYN ACK → ACK)
  
  UDP (User Datagram Protocol)
  OSI 7계층 중 4계층(Transport) 에 해당.
  비연결형 프로토콜로 데이터 도착여부를 모르기때문에 신뢰성이 떨어진다는 단점이 있으나, 빠르다는 장점이 있음. 신뢰성보다는 속도가 요구될 때 많이 사용 (ex. 스트리밍, TFTP, SNMP)
  
  
  
• OSI 7계층, TCP/IP 프로토콜
  
  

  

  
  1계층 : Physical Layer(물리계층)
  컴퓨터 간 물리적 연결을 정의하는 계층으로 장비들 간 bit를 전송
  
  2계층: Data Link Layer(데이터링크 계층)
  MAC address로 물리적 주소를 지정함으로써 데이터 전송에 신뢰성 제공
  
  3계층: Network Layer(네트워크 계층)
  IP를 정의해 경로선택 및 라우팅을 관리하는 계층으로, packet으로 정보를 분할하여 전송하며 패킷의 이동경로 결정
  
  4계층: Transport Layer(전송 계층)
  TCP, UDP 프로토콜을 통해 흐름제어 및 오류제어를 하며, segment 전달
  
  5계층: Session Layer(세션 계층)
  세션을 관리함으로써 통신하는 두 호스트의 최초연결 및 연결유지를 담담
  
  6계층: Presentation Layer(표현 계층)
  압축 및 암호화를 수행하며, 데이터 포맷을 변환하고 결정하는 계층 (ex.jpg, png)
  
  7계층: Application Layer(응용 계층)
  사용자가 이용하는 응용프로세스의 정보교환을 담당함. telnet, http, ftp protocol 등이 있음 
  
  
  
• OSI 7계층과 TCP/IP 프로토콜의 차이
  
  OSI 7계층
  장비 개발자가 어떻게 표준을 정할 지 결정
  
  TCP/IP
  실질적으로 사용되는 프로토콜에 대한 정보로 신뢰성이 더 높음
  
  
  
• http는 어느계층인지 설명
  
  OSI 7계층 중 7계층(Application)에 해당.
  HTTP는 웹페이지를 요청하고 받기 위해 사용되는 프로토콜로 응용계층에서 웹서버와 클라이언트 간 통신을 담당함.
  
  
  
• Linked List
  
  노드와 링크로 구성되어 있는 리스트로, 순차적으로만 접근이 가능하며 연속적이지 않은 메모리를 사용함.
  (링크로 순서를 유지함)
  단일 연결 리스트 (단방향)과 이중 연결 리스트 (양방향)으로 구성됨.
  동적인 자료구조로 미리 크기를 지정할 필요 없이 필요할때마다 할당할 수 있음.
  
  
  
• Queue
  
  FIFO (First In First Out)으로 입구와 출구가 따로 있는 자료구조임. rear에서 삽입되며, front에서 삭제됨.
  (ex. 은행업무, 콜센터 대기, BFS, 캐시 구현)
  
  
  
• Stack
  
  LIFO(Last-In-First-Out)으로 top을 통해서만 데이터 접근이 가능함.
  (ex. 함수 호출,   반환주소 및 복귀주소 저장, 웹브라우저 방문기록 뒤로가기, 실행취소, 수식 괄호검사)
  Heap과같은 다른 메모리 영역으로 stack을 일부 대체할 수 있지만, 힙은 메모리관리가 매우 복잡하고 속도가 상대적으로 느리기 때문에 stack은 필수적임.
  
  
  
• Heap
  
  이진트리이면서 모든 노드에 저장된 값이 자식노드에 저장된 값보다 크거나 작아야 하는 구조임.
  힙은 루트노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있기 때문에 우선순위 큐를 구현할 수 있음.
  (저장된 노드를 뺄때마다 우선순위가 높은 데이터가 먼저 빠져나오기 때문)
  
  
  
• Tree
  
  노드(vertex)와 링크(edge)로 구성된 비선형 자료구조임.
  최상위 노드인 root를 제외한 모든 노드는 한 개의 부모노드를 가지며, 여러 개의 자식노드를 가질 수 있음.
  연결되어 있는 노드는 1개 이상이 될 수 없음 (경로가 유일함)
  
  
  
• Binary Tree
  
  최하위 노드(leaf node)를 제외한 모든 노드가 2개 이하의 자식노드를 갖는 트리를 의미하며, left child, right child로 구분함.
  Full binary tree와 complete binary tree로 구분할 수 있음.
  
  Full binary tree
  leaf 노드를 제외한 모든 레벨이 2개의 자식을 갖는 트리를 의미함.
  (모든 노드가 0개 or 2개의 자식노드)
  
  Complete binary tree
  모든 레벨이 완전히 채워져 있어야 하며, 마지막 레벨의 노드는 왼쪽에서 오른쪽으로 채워져 있어야 함.
  (ex. Heap 정렬)
  
  
  
• Tree Traversal (트리 순회)
  
  모든 노드를 체계적으로 방문하는 과정으로 3가지 방법으로 구분됨.
  
  전위 순회 (Pre-order Traversal)
  루트 → 왼쪽 서브트리   → 오른쪽 서브트리로 방문.
  
  중위 순회 (In-order Traversal)
  왼쪽 서브트리 → 루트 → 오른쪽 서브트리로 방문.
  
  후위 순회 (Post-order Traversal)
  왼쪽 서브트리 → 오른쪽 서브트리  → 루트로 방문.
  
  
  
• Hash
  
  데이터를 효율적으로 관리하기 위한 자료구조 기법으로, 고정된 크기의 배열 인덱스로 변환시켜 데이터의 삽입,검색, 삭제를 빠르게 수행할 수 있음. ( O(1) )
  
  Hash Function(해시 함수)
  key값을 고정된 길이의 hash로 변경해주는 함수.
  hash는 저장위치를 의미함.
  
  Hash Table
  Hash function을 통해 key를 hash값으로 매핑하고, hash값을 index나 주소로 삼아 데이터를 key와 함께 저장하는 자료구조를 의미함.
  key - value로 이루어져 있음.
  
  장점으로는 빠르게 데이터 접근 및 관리가 가능함.
  단점으로는 hash 충돌이 발생할 수 있어 이를 해결하기 위한 추가적인 자료구조가 필요함.(ex. 선형탐사법, 연결볍)
  또한, hash function의 성능에 따라 hash table의 성능이 크게 달라질 수 있음(의존성이 높음)
  
  
  
• 파일 시스템과 DB 시스템의 차이
  
  파일 시스템
  파일을 생성하여 자료들을 추가,수정,삭제,검색 등의 조작이 가능한 시스템.
  순차접근으로 수행되며, 독립된 파일단위로 데이터를 저장하기 때문에 데이터 중복성, 일관성, 동시성 문제 발생함.
  
  DB 시스템
  파일 시스템의 문제를 해결하여 데이터의 독립성, 일관성, 무결성을 유지함.
  실시간 접근이 가능하며, 계속적인 변화가 가능하고, 공용성이 보장되며, 내용에 의한 참조가 가능하기 때문에 통합관리에 용이함.
  응용프로그램과 DB 사이의 중재를 위해 DBMS가 사용됨.
  
  
  
• DBMS
  
  응용프로그램과 데이터베이스 사이의 중재자로 정의, 조작, 제어 기능을 가짐.
  사용자 요구에 의해 데이터를 읽어오는 random access가 가능하며, 데이터의 추가나 수정, 삭제가 용이하기 때문에 많이 사용함.
  장점으로는 독립성, 무결성이 보장되고 일관성을 유지되어 실시간으로 데이터 통합관리가 가능하지만, 단점으로는 비용이 많이 들고 시스템이 복잡함.
  
  
  
• 스키마(메타데이터)
  
  데이터베이스의 구조와 제약조건에 대한 명세를 기술한 것으로 데이터사전(시스템 카탈로그)에 저장됨.
  외부 스키마와 개념 스키마, 내부 스키마로 구분됨.
  
  외부 스키마: DB의 전체 데이터 중 사용자가 접근할 수 있는 부분
  개념 스키마: 일반적 스키마로 DB전체의 논리적 구조를 가지며, 무결성 규칙을 가짐. DBA가 설계
  내부 스키마: 실제 데이터가 저장되는 DB의 물리적 저장 구조
  
  

• Binary Search Tree (BST, 이진탐색트리)
  
  정렬된 binary tree로 다음과 같은 속성이 있음.
  
  속성
  1) 노드의 왼쪽 하위트리는 노드 키보다 작음
  2) 노드의 오른쪽 하위트리는 노드키보다 큼
  3) 하위트리도 각각 BST여야 함
  4) 중복된 키를 허용하지 않음
  
  트리의 높이가 낮고, 좌우 균형이 맞을 때 가장 좋은 성능,
  In-order traversal 시 모든 키를 정렬된 순서로 가져올 수 있음
  
  검색방식: 루트와 키값 비교 → 작으면 왼쪽재귀,크면 오른쪽재귀 → 동일값 찾을때까지 반복(없으면 null 반환)
  
  시간 복잡도
  

	Worst	Average	Best
삽입	O($N$)	O($\log N$)	O($\log N$)
검색	O($N$)	O($\log N$)	O($\log N$)
제거	-	O($\log N$)	-

 

• Balanced Tree
  
  모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 특정 값을 넘지 않도록 유지하여, 트리의 균형을 맞추는 트리로,
  연산과정에서 최악의 성능을 내지않기 위해 사용함.
  B-Tree, AVL Tree, Red-Black Tree가 해당함.
  
  
  
• Binary Balanced Tree (균형이진트리)
  
  트리의 모든 노드에서 왼쪽과 오른쪽 자식 트리의 높이 차이가 최대 1이 될 수 있도록 유지되는 트리임.
  한쪽으로 쏠릴수 있는 데이터도 트리의 높이를 균형적으로 유지시켜줌.
  balanced Tree이기 때문에 Worst Case가 없음. 항상 O($\log N$)의 검색 성능
  
  
  
  
• B-Tree (Balanced Tree)
  
  하나의 노드 당 2개 이상의 자식을 가질 수 있는 자체 균형 트리구조이며,
  하나의 노드가 여러 데이터를 가질 수 있음.
  외부검색에 효율적인 검색구조로 DB시스템에서 많이 사용됨.
  
  
  
• AVL Tree
  
  각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이가 서로 균형을 이루는 이진 탐색 트리임.
  스스로 균형을 잡는 self-balancing 이진탐색트리임.
  (한쪽으로 이진트리가 치우쳐지면 트리의 높이가 높아지기 때문에 높이를 낮춰야 함)
  왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이며, 높이차이가 1보다 커지면 회전을 통해 균형을 잡음.
  시간복잡도는 O($\log N$)임.
  
  
  
• Red-Black Tree
  
  이진탐색 트리 중 가장 효율이 좋은 트리로 balanced tree에 속하며, 노드가 블랙 또는 레드의 색깔을 가짐.
  다음과 같음 조건이 존재함.
  
  1) root와 leaf 노드는 모두 black
  2) Red 노드의 자식은 모두 black
  3) Black 노드의 자식은 Red or Black
  4) Root 노드부터 leaf 노드까지의 Black 노드 개수는 어느경로나 동일
  5) root 노드부터 가장 먼 경로까지의 거리 < 2 x 가장 가까운 경로까지의 거리
  
  스스로 균형을 잡는 self-balancing 이진탐색트리임.
  시간복잡도는 O($\log N$)
  
  
  
• AVL Tree vs Red-Black Tree
  
  Red-Black Tree는 AVL보다 빠르게 삽입/삭제 연산이 가능하며, 메모리도 적게 사용
  (AVL은 BF라는 int값을 추가로 사용하기 때문)
  
  
  
• Graph
  
  vertex와 edge로 이루어진 자료구조로 객체간 연결을 모델링함.
  directed 그래프와 undirected 그래프로 구분됨.
  
  Directed 그래프
  출발노드와 도착노드가 정해져 있음.
  
  Undirected 그래프
  출발노드와 도착노드의 구분이 없음 
  
  
  
• Spanning Tree (신장트리)
  
  그래프의 부분 그래프 중 모든 vertex와 연결되어 있는 부분 그래프 (cycle이 없는 그래프)
  (cycle: 처음 vertex와 끝 vertex가 같은 경로)
  
  
  
• Minimum Spanning Tree (MST, 최소신장트리)
  
  Spanning tree에서 가중치(edge 비용의 합)이 최소인 트리로, 구현을 위해 다익스트라 알고리즘을 사용함. 
  (ex. 지하철역 최단거리, 최소비용으로 통신망연결)
  
  MST를 표현하기 위한 알고리즘으로는 Kruskal과 Prim 알고리즘이 있음.
  
  Kruskal
  최소비용을 가진 edge들을 차례로 탐색해 나가면서 cycle이 없는 경로(트리)를 찾는 방법
  O($E\log V$)
  트리정렬: O($E\log E$) + cycle 생성여부 검사시간: O($E$) = O($E \log E$) = O($E\log V$)
  
  Prim
  임의의 vertex를 기준으로 비용이 가장 적은 edge를 탐색해 나가는 방식임.
  (cycle이 없는 경로를 찾음)
  밀집그래프(dense graph)에서 가장 효과적임.
  
  
  
• 보안의 3대 요소
  
  기밀성(Confidentiality)
  인가된 사용자만 접근가능 (ex. 방화벽, 패스워드)
  
  무결성(Integrity)
  적절한 권한을 가진 사용자만 인가한 방법으로 정보 변경 (접근 통제)
  
  가용성(Availability)
  언제나 정보에 대한 접근이 가능하도록 함 (ex. 백업)