자료구조/알고리즘

• Stack

  : 데이터를 순서대로 쌓아 가장 먼저 들어간 입력이 가장 나중에 나오는 FILO(First In Last Out), LIFO(Last In First Out) 구조의 자료구조

  • Stack의 장점

    • 스택은 LIFO 구조로 삽입과 삭제가 항상 스택의 맨 위에서 이루어지기 때문에 삽입과 삭제 연산의 속도가 매우 빠르다.
    • 자바에서는 스택이 기본 자료구조이므로, 별도의 라이브러리나 모듈이 필요하지 않다.

  • Stack의 단점

    • 데이터를 저장할 때 크기 제한이 없어서 메모리 사용량이 불필요하게 늘어날 수 있다. 그래서 스택의 크기를 미리 정해놓거나, 동적으로 크기를 조절해야 한다.
    • 동적으로 크기를 조절하지 않기 때문에 데이터의 개수가 배열의 크기를 초과하면 기존 배열을 새로운 배열로 복사하는 작업을 수행한다. 그래서 크기가 자주 변해야하는 자료구조를 사용할 때는 다른 자료구조를 사용하는 것이 효율적이다.

• Queue

  : Stack과 반대로 가장 먼저 들어간 입력이 가장 먼저 나오는 FIFO(First In First Out) 구조의 자료구조

  • Queue의 장점

    • 자료를 넣은 순서대로 데이터를 꺼내 처리할 수 있으므로, 차례대로 처리할 작업이 많은 경우 효율적이다.
    • 삽입과 삭제가 각각 양 끝에서 이루어지므로 삽입과 삭제가 빈번한 상황에 효율적이다.
    • 자바에서는 큐가 기본 자료구조이므로, 별도의 라이브러리나 모듈이 필요하지 않다.

  • Queue의 단점

    • 중간에 있는 데이터를 조회하거나 수정하는 연산에 적합하지 않다.
    • 크기 제한이 없어서 메모리 낭비가 발생할 수 있다.
    • iterator()가 지원되지 않는다.

• Tree

  : 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조

  • Tree의 특징

    • 루트(Root)라는 하나의 꼭짓점을 시작으로 여러 데이터를 간선(edge)로 연결하며, 각 데이터를 노드(Node)라고 한다. 그리고 두 노드가 상하 계층으로 연결되면 부모/자식 관계를 가지고, 자식이 없는 노드는 리프 노드(Leaf Node)라 부른다.
    • 깊이(Depth) : 루트로부터 하위 계층까지의 깊이로 루트 노드는 깊이가 0 이다.
    • 레벨(Level) : 같은 깊이를 가지는 노드를 묶어 레벨로 표현하고, 깊이가 0인 루트 노드의 level은 1이다. 그리고 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라 한다.
    • 높이(Height) : 리프 노드를 기준으로 루트까지의 높이로 각 리프 노드의 높이 0이다.
    • 서브 트리(Sub Tree) : 큰 트리 내부에, 트리 구조를 갖춘 작은 트리

  • Tree의 장점

    • 계층 구조를 나타내는 데 효율적이다.
    • 정렬과 탐색에 효율적이다.
    • 삽입과 삭제 연산 시에 노드의 부모와 자식만 수정하면 되므로 삽입와 삭제가 쉽다.

• Binary Tree

  : 이진 트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리

  • 정 이진 트리 (Full Binary Tree)

    : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.

  • 완전 이진 트리 (Complete Binary Tree)

    : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨은 왼쪽부터 채워져 있어야 한다.

  • 포화 이진 트리 (Perfect Binary Tree)

    : 정 이진 트리이면서 완전 이진 트리인 경우이고, 모든 리프 노드의 레벨이 같고, 모든 레벨이 가득 채워져 있는 트리

• Binary Search Tree

  : 이진 탐색 트리란, 이진 탐색의 속성이 이진 트리에 적용된 특별한 형태의 이진 트리이다. 그리고 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.

  • 이진 탐색

    : 특정 값을 찾기 위한 탐색 알고리즘 중 하나로, 오름차순으로 정렬된 데이터를 같은 크기의 두 부분으로 나누고 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 범위를 제한하여 값을 찾는 알고리즘이다.

• Tree Traversal

  • 전위 순회 (Preorder Traverse)

    : 루트부터 왼쪽의 노드들을 차례로 탐색한 뒤, 왼쪽의 탐색이 끝나면 오른쪽 노드를 탐색한다.

  • 중위 순회 (Inorder Traverse)

    : 루트를 중간에 탐색하며, 왼쪽 끝의 노드부터 시작해 왼쪽 -> 부모 -> 오른쪽 차례로 탐색한다.

  • 후위 순회 (Postorder Traverse)

    : 루트를 가장 마지막에 탐색하고, 왼쪽 -> 오른쪽 -> 부모 차례로 탐색한다.

• Graph

  : 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조로 점을 정점(Vertex), 하나의 선을 간선(Edge)이라 한다.

  • Graph의 표현 방식

    • 인접 행렬

      : 서로 다른 정점들 사이 간선이 있는지 표시한 행렬로, 이어져 있다면 1, 아니면 0으로 2차원 행렬 형태로 나타낸다.

    • 인접 리스트

      : 각 정점이 어떤 정점과 인접하는지 표시한 리스트

• Graph Traversal

  • BFS (Breadth First Search)

    : 가장 가까운 정점부터 탐색하는 너비 우선 탐색으로 최단 경로를 찾을 때 사용
    

  • BFS 특징

    • 한 정점을 기준으로 해당 정점과 인접한 정점을 모두 방문한다.
    • 최단 경로 탐색에 유리하다.
    • 큐를 사용해 정점을 저장하기 때문에 그래프가 큰 경우 메모리 사용이 크다.
    • 방문 여부를 체크하는 자료구조를 사용해야 한다.

  • DFS (Depth First Search)

    : 한 경로를 끝까지 탐색한 후, 다음 경로로 가는 깊이 우선 탐색으로 모든 경로를 완전히 탐색할 수 있다.

  • DFS 특징

    • 한 분기, 경로를 완벽하게 탐색한 후, 다음 분기로 넘어갑니다.
    • 그래프 내 순환구조를 고려해 방문한 정점을 확인하고 이미 방문한 정점을 다시 방문하지 않도록 해야한다.