https://github.com/JaeYeopHan/Interview_Question_for_Beginner 위 링크에 있는 문제에 대한 답안을 정리해보았다.

1. 전산 기초

자료구조

Array vs Linked List

  • Array
    • index를 통해 element에 직접적으로 접근할 수 있다. 특정 element에 접근하는 시간 복잡도는 O(1)
    • memory 위치가 고정적이기에 삽입과 삭제 연산 시 시간이 많이 소요됨. 삭제 시 삭제한 원소보다 큰 인덱스의 원소들을 shift하는 비용이 발생, 시간 복잡도는 O(n). 삽입의 경우에도 비슷하게 O(n)
  • Linked List
    • 각각의 원소들이 자기 다음 원소만을 기억하게 함. 때문에 search시 시간 복잡도는 O(n)
    • 삭제와 삽입 시 다음 원소를 가리키는 값을 바꾸면 되므로 시간 복잡도는 O(n)
    • Tree 구조의 근간

Stack and Queue

  • Stack
    • Last In First Out (LIFO). 나중에 들어간 원소가 먼저 나옴.
  • Queue
    • First In First Out (FIFO). 먼저 들어간 원소가 먼저 나옴.

Tree

  • Stack이나 Queue와 다르게 비선형적 자료 구조.
  • Tree는 root와 leaf로 이루어짐
  • Binary Tree (이진 트리)
    • 모든 노드의 차수가 2 이하인 트리
    • Full Binary Tree (포화 이진 트리)
      • 모든 레벨에서 노드들이 모두 채워져있는 이진 트리
    • Complete Binary Tree (완전 이진 트리) - 마지막 레벨을 제외하고는 모든 노드가 자식 노드를 2개 가진 이진 트리
  • Binary Search Tree (이진 탐색 트리)
    • 모든 노드에 대하여
      • 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
      • 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 크고
      • 왼쪽과 오른쪽 서브트리 역시 각각 이진 탐색 트리여야 한다
    • 이진 탐색과 연결 리스트를 결합한 자료 구조의 일종
  • Red Black Tree
    • Search, Insert, Delete에 O(logn)의 시간 복잡도 소요
    • 정의
      • 각 노드는 Red or Black이란 색을 갖는다
      • 루트 노드는 블랙이다
      • 모든 리프 노드들은 블랙이다
      • 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다
      • 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다
    • 특성
      • 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 작다
      • 레드-블랙 트리는 개략적으로 균형잡혀있다
      • 시간 복잡도가 높이에 따라 결정됨
  • 참조
    • https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

Hash Table

  • 연관배열 구조를 이용해 key 값에 value를 저장하는 자료 구조
  • 해시 테이블은 key, hash function, hash, value, bucket(저장소)으로 이루어져 있다
  • key는 hash function을 통해 hash로 변경되며 value와 매칭되어 저장소에 저장 된다
    • key: 고유한 값, 해시 함수의 input.
    • hash function: key를 hash로 바꾸어 줌. 서로 다른 key가 같은 해시가 되는 경우 hash collision이 일어난다. collision을 최소화하는 방식이 필요.
    • hash: hash function의 결과물.
    • value: 저장소에 최종적으로 key와 매칭되어 저장되는 값
  • Insertion
    • 시간 복잡도는 O(1). key는 고유하며 해시함수의 결과로 나온 hash와 value를 저장소에 넣으면 되기 때문.
    • 최악의 경우 O(n)이 될 수도 있음. 해시 충돌로 인해 모든 value를 찾아봐야 할 경우.
  • Deletion
    • 시간 복잡도 O(1), 최악의 경우 O(n)
  • Search
    • 시간 복잡도 O(1), 최악의 경우 O(n)
  • Hash Collision을 해결하는 법
    • Seperate Chaining
      • 연결 리스트를 이용하는 방식
        • 각각의 bucket을 연결 리스트로 만들어 collision 이 발생하면 해당 bucket의 리스트에 추가. 연결 리스트의 특성을 물려받아 삭제 또는 삽입이 간단.
    • Open Addressing - 비어있는 해시를 찾아 데이터를 저장하는 방법 - 해시 테이블은 1개의 해시와 1개의 값이 매칭되어있는 방식으로 유지 - 장점 - 다른 저장공간 없이 해시테이블 내에서 저장 및 처리가 가능 - 다른 저장공간에서 추가적인 작업이 없음
      • 단점 - 해시함수의 성능에 따라 전체 해시테이블의 선응이 좌우됨 - 데이터의 길이가 늘어나면 해당하는 저장소 필요
  • 해쉬 테이블 구조의 단점
    • 순서가 있는 배열에 어울리지 않음
    • 공간 효율성이 떨어짐
    • Hash Function의 의존도가 높음
  • 참조
    • https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o

Graph

  • 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조
  • 연결되어 있는 객체 간의 관계를 표현할 수 있음
  • 트리 또한 그래프에 속하며, 그 중 사이클이 허용되지 않는 그래프임
  • 그래프의 종류
    • 무방향 그래프 vs 방향 그래프
      • 무방향 그래프 (Undirected Graph)
        • 간선을 통해 양방향으로 갈 수 있는 그래프
        • 정점 A와 정점 B를 연결할 수 있는 간선은 (A, B)와 같이 정점의 쌍으로 표시
      • 방향 그래프 (Directed Graph)
        • 간선에 방향성이 존재하는 그래프
        • A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다
        • 트리 또한 방향 그래프
    • 가중치 그래프 (Weighted Graph)
      • 간선에 비용이나 가중치가 할당된 그래프
      • ‘네트워크’라고도 한다
    • 연결 그래프 vs 비연결 그래프 - 연결 그래프 (Connected Graph) - 무방향 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 경우 - ex) 트리
      • 비연결 그래프 (Unconnected Graph) - 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
    • 사이클 vs 비순환 그래프 - 사이클 (Cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우 - 비순환 그래프 (Acyclic Graph) : 사이클이 없는 그래프
    • 완전 그래프 (Completed Graph) - 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프
  • 그래프의 구현
    • 인접 리스트 (adjacent list)
      • 각각의 정점에 인접한 정점들을 리스트로 표시
      • 장점
        • 어떤 노드에 인접한 노드를 쉽게 찾을 수 있다
        • 모든 간선의 수는 O(N + E)안에 알 수 있다 (정점의 수 + 간선의 수)
      • 단점 - vertex 간 연결되어 있는지 확인하는데 오래 걸림
    • 인접 행렬 (Adjancy Matrix) - matrix[i][j]가 true이면 i -> j로의 간선이 있음 - 정점의 개수가 n인 그래프를 인접 행렬로 표현할 때, 간선의 수와 무관하게 항상 n^2의 메모리 공간이 필요하다 - 장점 - 두 정점을 연결하는 간선의 존재여부를 O(1)에 알 수 있다 - 정점의 차수는 O(N) 안에 알 수 있다. 인접 배열의 i번째 행 또는 열을 전부 더하면 되기 때문
      • 단점 - 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다 - 그래프에 존재하는 모든 간선의 수를 파악하는데 O(N^2)이 소요됨
    • 정점의 개수가 적으면 인접 행렬, 많으면 인접 리스트를 사용하는 것이 효율적일 수 있음
  • 그래프의 탐색
    • 깊이 우선 탐색 (DFS)
      • 모든 노드를 방문하고자 할 때 사용
    • 너비 우선 탐색 (BFS)
      • 두 노드 사이의 최단 경로나 임의의 경로를 찾고 싶을 때 사용
  • 참조
    • https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html