[BACKEND] 백엔드 개발 기술면접 준비(4) 자료구조와 알고리즘

기술면접 준비(4) 자료구조와 알고리즘 뒤죽박죽

 

 

Q. Big-Oh Notation

A. 알고리즘의 효율성(시간 복잡도)을 표기하는 방법이다.

 

Q. 동적 프로그래밍(다이나믹 프로그래밍, Dynamic Programming)

A. 큰 문제를 한번에 해결하기 어려울 때 작은 문제로 나눠 푸는 방법

* 분할/정복과 비슷하나 분할/정복은 작은 단위 문제로 나눴다가 다시 합병하며 해결하는 방법이고 동적 프로그래밍의 경우 작은 문제가 반복하여 일어난다. 이 작은 문제들의 결과값은 항상 같은데 이 값을 저장해놓고 이용한다(Memorization). 같은 문제의 답은 항상 같다.

가장 대표적인 예로 피보나치 수열이 있다.

 

Q. Call by Reference / Call by Value

A. 함수 호출 방식이다.

• Call by Reference(참조에 의한 호출)
  인자로 받은 값의 주소를 참조하여 직접 값에 영향을 준다.
• Call by Value(값에 의한 호출)
  인자로 받은 값을 복사하여 처리한다. 인자 자체값에는 영향을 주지 않는다.
  지역변수와 매개변수 값이 스택에 저장된다.

 

Q. 큐(Queue)

A. 큐란 선입선출(먼저 넣은 데이터가 먼저 나오는 방식)의 자료구조로 양방향으로 접근이 가능하다. 주로 정해진 순서대로 일을 처리해야 하는 경우 사용한다.

삽입(enqueue), 삭제(dequeue) 시 O(1)이 소요되고 탐색 시 O(n)이 소요된다.
예) 콜센터의 대기 시간, 프린터 대기 목록, 프로세스 관리, BFS

* Array로 구현하면 dequeue시 앞당기는 연산이 필요함으로 List(Linked List)로 구현하는 것이 좋다.

 

* 자바에서의 큐

import java.util.LinkedList;
import java.util.Queue; 

Queue<Integer> queue = new LinkedList<>();
// 자바에서 큐는 LinkedList를 활용하여 생성해야 한다.


queue.add(1); // enqueue 성공 시 True, 실패 시 IllegalStateException 반환
queue.offer(2); // enqueue

queue.poll(); // dequeue 맨 앞의 값 반환하고 삭제, 비어있다면 null
queue.peek(); // 값을 꺼내지 않고 맨 앞의 값 확인
queue.remove(); // dequeue, 맨 앞의 값 삭제, 없다면 NoSuchElementException 반환
queue.clear(); // 큐 초기화

 

 

Q. 스택(Stack)

A. 스택이란 후입선출(마지막에 넣은 데이터가 먼저 나오는 방식)의 자료구조로 한쪽 방향으로만 삽입, 삭제가 가능하다. 자료가 없을 때 pop하면 stack underflow, 스택 크기 이상의 자료를 push하려하면 stack overflow 문제가 발생한다.

삽입(push), 삭제(pop) 시 O(1)이 소요되고 탐색 시 O(n)이 소요된다.

예) 웹 브라우저의 방문 기록, 이전 실행 취소, 수식의 괄호 검사, 시스템 콜 스택 등

 

* List로 구현하면 객체를 제거하는 작업이 필요하다. 하지만 Array로 구현하면 인덱스를 하나만 줄이면 됨으로 Array로 구현하는 것이 좋다.

 

* 자바에서의 스택

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.pop();
stack.clear(); // 스택 전체 초기화
stack.peek(); // 값을 꺼내지 않고 가장 상단 출력
stack.size(); // 스택 크기
stack.empty(); // 스택이 비어있는지 여부 Boolean으로 출력
stack.contains(1) // 스택에 해당 값이 있는지 Boolean 반환

 

[정리] 큐와 스택이란 무엇인가

큐는 먼저 넣은 데이터가 먼저 반환되는 구조의 자료구조로 한쪽 방향으로만 데이터 접근이 가능하고 스택은 가장 마지막에 넣은 데이터가 먼저 나오는 구조의 자료구조로 양방향으로 데이터 접근이 가능하다. 둘 다 삽입과 삭제에 O(1) 시간이 소요되고 탐색에 O(n)이 소요된다.

 

Q. 우선순위 큐(Priority Queue)

A. 큐 자료형에 우선순위 개념을 도입한 것으로 우선순위가 높은 데이터가 먼저 나간다. 활용 예로 CPU 스케줄링이 있다.

 

Q. 그래프(Graph)

A. 노드와 노드를 연결하는 간선으로 이루어진 자료구조이다.

간선의 방향 유무에 따라 방향그래프와 비방향 그래프로 나뉜다. 모든 정점쌍에 대해 항상 경로가 있는 경우를 연결 그래프(대표적으로 트리가 있다), 어떠한 정점 쌍에 대해 경로가 없는 경우 비연결 그래프라고 한다. 단순 경로의 시작과 끝이 동일한 경우 순환 그래프 아닌 경우 비순환 그래프라고 한다. 완전 그래프는 모든 정점이 연결되어있는 경우를 말한다.

탐색(순회)은 BFS/DFS를 통해 이루어진다.

활용 예로 지도, 지하철 노선도, 선수 과목 표 등이 있다.

 

Q. 트리(Tree)와 이진트리(Binary Tree), 이진탐색트리(Binary Search Tree)

A. 트리는 하나의 루트 노드를 가지며 루트 노드는 0개 이상의 자식 노드를 갖고 그 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 노드들은 간선으로 연결되어 있으며 트리에는 사이클이 존재할 수 없다(비선형 자료구조). 계층적 관계를 표현한다. 그래프의 한 종류이며 사이클이 없는 하나의 연결 그래프이며 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.

그 중 이진트리는 최대 2개의 자식 노드를 갖는 트리이다. 

이진탐색트리는 모든 노드가 특정 순서(규칙)을 따르는 트리이다. 규칙은 {모든 왼쪽 자식 <= n < 모든 오른쪽 자식, n은 모든 노드}이다.

완전이진트리는 마지막 레벨을 제외하고 모두 꽉 찬 이진트리이다. 마지막 레벨의 경우 꽉 차 있지 않아도 되지만 왼쪽부터 오른쪽으로 채워져야 한다. 완전이진트리는 배열을 통해 효율적으로 표현 가능하다.

 

* AVL TREE

한 쪽으로 값이 치우치는 이진 균형 트리의 한계점을 보완하기 위해 만들어진 균형 잡힌 이진트리이다. 양쪽 서브트리 높이 차이가 최대 1이다. 항상 좌/우 데이터를 균형잡힌 상태로 유지해야하기 때문에 추가적인 연산이 진행된다.

 

* RED BLACK TREE

모든 노드를 빨간색 또는 검은색으로 칠한다. 연결된 노드는 색이 중복되지 않도록 관리한다.

 

* 이진탐색트리의 단점

평균 시간복잡도는 O(logN)이지만 최악의 경우(균형이 잡히지 않았을 때) O(N) 소요

 

Q. 트리 구현 방법

A. 트리 구현 방법에는 배열과 리스트가 있다.

• 배열
  포화이진트리나 완전이진트리, 중간중간 빈 공간이 생겨 메모리 낭비 발생 가능
  인덱스로 부모와 자식 관계 연결
• 리스트
  왼쪽 자식, 값, 오른쪽 자식 정보를 가진 노드로 표현됨

 

Q. 힙(Heap)

A. 완전이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조로 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.

최대힙은 부모 노드의 값이 자식 노드보다 크거나 같은 완전트리이고 최소힙은 반대로 부모 노드의 값이 자식 노드보다 작거나 같은 완전이진트리이다.

힙을 저장하는 표준 자료구조는 배열이다. 쉬운 구현을 위해 첫 번째 인덱스 0에 자료를 저장하지 않는다.

 

Q. Array(배열)과 리스트(Linked List, 연결리스트) 차이점

A. 두 자료형 모두 가진 데이터들을 묶어 효율적으로 관리하기 위한 자료형이다. 

Array은 연속된 메모리 공간으로 이루어져있으며 인덱스로 접근 가능하다. 정의와 동시에 길이를 지정하여 바꿀 수 없는 정적 자료형으로 삭제 시 공간 낭비가 발생한다. 삽입과 삭제 시 리스트보다 느리다.

LinkedList는 순서가 있는 데이터들의 집합이다. 불연속적인 메모리 공간을 사용하며 인덱스가 없고 포인터로 접근 가능하다. 포인터가 다음 위치를 가르키고 있어 삽입과 삭제가 용이하다. 크기가 정해져있지 않은 동적 자료형이다. 하지만 검색 성능이 좋지 않다. 

 

Q. 해시 알고리즘

A. 해시란 데이터를 다루는 기법 중 하나로 검색과 저장을 빠르게 하는 자료구조이다. 데이터 저장 시 키와 값 형태로 데이터가 존재하고 키 값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어난다. 키값을 고정된 길이의 해시로 변환하는 것이 해싱, 이 함수를 해시 함수라 한다. 해시 함수에서 키값을 해싱 과정을 통해 해시 값, 해시 코드로 변경하며 이 값이 저장 위치가 된다. 서로 다른 키가 같은 해시가 되는 것을 해시 충돌이라하는데 충돌이 날 확률을 줄이는 것이 중요하다.

 

* 해시테이블

(키, 값) 형태의 데이터를 저장하는 자료구조로 빠른 데이터 검색 시 유용하다. 키 값에 해시 함수를 적용해 고유한 인덱스를 지정하고 해당 인덱스에 값을 저장한다. 인덱스로 값을 조회하기 때문에 O(1) 시간복잡도를 갖는다.

 

Q. 정렬 방법

A. 다양한 정렬 알고리즘이 존재한다.

1. 버블정렬(Bubble Sort)
   바로 뒤의 데이터와 비교하여 정렬을 진행하며 1회 실행하면 가장 큰 원소가 맨 뒤로 이동한다.
   시간복잡도 O(N) - O(N^2)
2. 삽입정렬(Insertion Sort)
   두 번째 자료부터 시작하여 앞의 자료들과 비교 후 삽입될 위치를 찾아 정렬한다.
   최악의 경우는 역순으로 정렬되어 있을 때이다.
   시간복잡도 O(N) - O(N^2)
3. 선택정렬(Selection Sort)
   리스트의 최소 값을 가장 앞으로 정렬하여 앞에서부터 정렬해 나간다.
   시간복잡도 항상 O(N^2)
4. 힙정렬(Heap Sort)
   최대힙이나 최소힙을 구성해 정렬하는 방식으로 마지막 노드에 삽입 후 부모 노드와 비교하여 위치를 찾는다.
   부가적인 메모리 사용이 없다.
   전체 정렬이 아니라 가장 큰 값 몇개만 필요할 때 유용하다.
   시간복잡도 O(N*logN)이지만 다른 알고리즘에 비해 느린 편, 안정성이 낮음
5. 병합정렬(Merge Sort)
   재귀를 이용한 정렬로 가운데 인덱스 기준으로 계속 분할하여 요소가 1개가 될때까지 나눈 다음 양쪽과 비교하여 배열을 합치고 이를 반복해 정렬을 해나간다.
   안정성이 높지만 공간이 많이 필요하다.
   시간복잡도 O(N*logN)
6. 퀵정렬(Quick Sort)
   문제를 분리하여 해결하는 분할 정복 방법으로 합병정렬과 비슷하나 피벗을 기준으로 비균등하게 그룹을 나눈다. 데이터 그룹을 나누는 피벗을 선택한 후 이를 기준으로 그룹을 나누는 것을 반복하여 각 그룹이 1개가 되면(분할이 불가능하면) 멈춘다.
   시간복잡도 O(N*logN)으로 가장 빠른 알고리즘이지만 최악의 경우(리스트가 불균형하게 나눠지는 경우) O(N^2)이 소요된다.
   정렬된 배열에서 피벗을 최소 또는 최대로 잡는 경우가 최악의 경우 예이다.
   * N개의 수 중 K번째 수를 찾는 문제 대게 퀵정렬 이용

 

Q. 가장 빠른 정렬

A. 가장 빠른 정렬은 퀵정렬이다. 퀵정렬은 평균적으로 O(NlogN)의 시간복잡도를 지니지만 최악의 경우 O(N^2) 시간복잡도를 갖는다.
짧은 시간동안 반복적으로 접근하는 데이터를 참조하는 특성을 지역성이라 하는데 퀵정렬은 합병정렬보다 지역성을 높게 띤다.

퀵정렬이 빠른 이유는 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터 이동을 가능하게 하기 때문이다.

 

Q. 이진탐색트리 탐색 속도

A. 이진 탐색의 시간 복잡도는 O(logN)이며 삽입이나 삭제가 불가능하다. 연결리스트 탐색 시간 복잡도는 O(N)으로 삽입이나 삭제 시 O(1)이 소요된다. 이 둘을 합친 것이 이진 탐색 트리로 탐색 효율을 높히고 자료의 삽입과 삭제를 가능하게 한다.

이진탐색트리 탐색 시간복잡도는 O(logN)이다(노드가 N개일 때 트리 높이는 log(N)).

 

Q. BFS / DFS

A. 그래프 탐색 방법이다.

• BFS(너비우선탐색)
  

  

  
  루트 노드(시작 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법이다. 멀리 있는 노드를 마지막에 방문하게 된다. 두 노드 사이의 최단경로를 찾을 때 사용된다.
  어떤 노드를 방문했는지 노드 방문 검사를 해야함으로 자료구조 큐를 사용한다.
• DFS(깊이우선탐색)
  

  

  
  루트 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법
  예를 들어 미로찾기에서 한 루트로 계속 가다가 막다른 길이면 바로 직전 갈림길로 돌아가 다른 길을 찾는 방법이라고 할 수 있다.
  모든 노드를 탐색하고자 할 때 사용하며 BFS보다 간단하지만 검색 속도 자체는 BFS에 비해 느리다.
  자기 자신을 호출하는 재귀 형태이다.
  마찬가지로 어떤 노드를 방문했는지 노드 방문 검사를 꼭 해야하며 스택을 이용한다.

 

Q. 이진탐색트리 탐색 방법

A. 이진탐색트리 탐색 방법에는 전위/중위/후위 탐색 방법이 있다.

• 전위순회
  루트에서 왼쪽으로 순회하고 더 이상 왼쪽이 없다면 부모로 올라와 오른쪽을 확인한다.
  F -> B -> A -> D -> C -> E -> G -> I -> H (root -> left -> right)
• 중위순회
  중위 순회는 왼쪽 노드부터 루트, 오른쪽 노드 순으로 순회한다.
  A -> B -> C -> D -> E -> F -> G -> H -> I (left -> root -> right)
• 후위순회
  왼쪽 노드부터 오른쪽, 루트 순으로 순회한다.
  A -> C -> E -> D -> B -> H -> I -> G -> F (left -> right -> root)
• 레벨순회
  A -> B -> G -> A -> D -> I -> C -> E -> H

 

Q. Vector에서 메모리는 언제 얼만큼 할당되는가

A. 사용할 메모리 영역을 처음 선언할 때 정해진 값만큼 할당한 후 이를 넘어서게 되면 현재 할당한 크기의 1/2배의 크기로 재할당된다.