알고리즘 공부2

김민재·2024년 11월 3일

20241103 트리

트리

계층적 데이터 구조로써 여러 개의 노드가 부모-자식 관계로 연결된 자료구조

루트: 가장 위쪽 노드
부모: 어떤 노드들의 상위 노드
자식: 어떤 노드의 하위 노드들(F,G)
형제: 같은 부모를 가지는 노드들(D,E)
리프 노드: 자식이 없고 가장 깊은 곳에 있는 노드(레벨 3)
노드: 데이터를 저장하는 요소들(트리의 각 점)
간선: 노드 간의 관계를 나타내는 선
레벨: 트리에서 루트로부터의 깊이(루트는 0)

이진 탐색 트리

이진 트리(각 노드가 최대 두개의 자식만을 가지는 트리)의 한 종류로써 탐색에 최적화된 구조를 가진다.

왼쪽 서브트리 값 < 부모 노드 값
오른쪽 서브트리 값 > 부모 노드 값
이런 규칙들이 모든 노드에서 재귀적으로 적용되기 때문

이런식의 구조에서
찾는 값이 현재 노드보다 작으면 왼쪽 서브트리로
찾는 값이 현재 노드보다 크면 오른쪽 서브트리로 탐색하며 찾는다.

이런 구조를 통해서 탐색,삽입,삭제에 대해서 O(log N)의 시간 복잡도를 가진다.

이진트리와 이진탐색트리의 차이점

DFS?

깊이 우선 탐색(Depth First Search)의 줄임말로
트리나 그래프를 최대한 깊이 들어가서 탐색하는 방법이다.
(한 경로를 끝까지 탐색하고 난 후 다른 경로로 이동한다.)

DFS는 모든 경우의 수(모든 경로), 퍼즐을 풀기 등에 사용하는 탐색 알고리즘이며 재귀를 통하여 구현한다.
그렇지만 너무 많이 부르게되면 overflow가 일어날 수 있으므로 적당히 해야만 한다.

일반적으로 기본 시스템에서 스택의 크기는 1~8MB이며 이는 4바이트 크기의 항목이 최대 2097152개의 항목을 저장할 수 있다고 한다.
여러모로 찾아보니 vscode에서는 .vscode 폴더를 만들어서 내부에 launch.json과 같은 파일들을 설정하여 스택의 크기를 조정할 수 있다고 한다!

{
  "version": "2.0.0",
  "tasks": [
    {
      "label": "build",
      "type": "shell",
      "command": "gcc",
      "args": [
        "main.c",
        "-o",
        "main",
        "-Wl,-stack,16777216"  // 스택 크기를 16MB로 설정
      ],
      "group": {
        "kind": "build",
        "isDefault": true
      }
    }
  ]
}