먼저 비선형 자료 구조가 무엇일까

비선형 자료 구조, 데이터가 일렬로 나열되어 있지 않고 계층적이거나 여러 갈래로 복잡하게 연결된 구조

트리

트리란, 하나의 최상위 노드에서 시작해 가지처럼 여러 하위 노드로 뻗어 나가는 순환이 없는 비선형 계층적 자료구조이다

하나의 요소가 여러요소와 연결될 수 있음, 최상위 루트노드가 있고 부모 자식관계가 형성되며 레벨이 나누어짐, 한 노드에서 출발하여 이동했을때 자기 자신에게로 되돌아갈 수 없음 (되돌아갈 수 있다면 그건 그래프)

용어 정리

링크: 노드들을 연결하는 선

노드 : 트리의 기본 구성 요소로, 데이터를 저장하는 단위

• 루트 노드: 트리의 꼭대기에 위치하는 최상위 노드로 부모노드가 없는 노드
• 단말 노드: 자식이 없는 노드 (말단 노드)
• 부모 노드: 자식 노드를 가진 노드
• 자식 노드: 부모 노드를 가진 노드
• 형제 노드: 같은 부모를 가진 노드

이진 트리 : 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 -> 단순하고 효율적 등 여러 장점이 있기에 지금부터 이진트리를 기준으로 얘기하도록 함

• 완전 이진 트리: 왼쪽 자식 노드 부터 순서대로 노드가 채워져 있는 트리
• 포화 이진 트리: 모든 레벨의 노드가 꽉 채워져 있는 트리
• 편향 이진 트리: 최소 개수의 노드 개수를 가지며 왼쪽 혹은 오른 쪽의 서브 트리만을 가진 트리

그리고

• 노드의 깊이: 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨: 루트 노드로부터 떨어진 거리
• 노드의 높이: 어떤 노드에서 단말 노드까지 가장 긴 경로의 간선 수
• 노드의 차수: 하위 트리의 개수

순회

탐색 전략에 따라 크게 2가지로 구분

1. DFS:깊이 우선 탐색 (스택)

갈 수 있는 최대 깊이까지 간 후 되돌아가며, 루트 노드를 언제 처리하냐에 따라 이름이 구분됨

• 전위: 루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 루트를 가장 먼저 방문하기 때문에 트리의 구조를 출력하거나 복제할 때 유용하게 사용

  • 위 그림에서 전위 순회 결과: A, B, D, F, C, G, H

  void pre_order(Node* node) {
      if (node != NULL) {
          printf("%d ", node->value); 
          pre_order(node->left);      
          pre_order(node->right);     
      }
  }

• 중위: 왼쪽 서브 트리 -> 루트 -> 오른쪽 서브 트리 이진 탐색 트리에서 중요한 역할을 하며, 노드들을 순서대로 출력하거나 오름차순 정렬할 때 사용

  • 위 그림에서 중위 순회 결과: D, B, F, A, G, C, H

  void in_order(Node* node) {
      if (node != NULL) {
          in_order(node->left);      
          printf("%d ", node->value); 
          in_order(node->right);     
      }
  }

• 후위: 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 자식 노드를 먼저 모두 처리한 후 부모 노드를 처리할 때 사용, 삭제나 메모리 해제와 같은 작업

  • 위 그림에서 중위 순회 결과: D, F, B, G, H, C, A

  void post_order(Node* node) {
      if (node != NULL) {
          post_order(node->left);      
          post_order(node->right);     
          printf("%d ", node->value); 
      }
  }

2. BFS:너비 우선 탐색 (큐)

레벨 순회와 동일한 방식으로, 한 레벨에 있는 노드를 모두 방문한 후 다음 레벨로 내려가 탐색을 계속하는 방식 최단 경로 탐색과 같은 문제 해결에 적합하다

루트 -> 다음 레벨의 노드를 왼쪽에서 오른쪽으로 방문 -> 모든 레벨에 반복

• 위 그림에서 레벨 순회 결과: A, B, C, D, F, G, H

void level_order(Node* root) {
    // 루트가 NULL이면 탐색할 트리가 없으므로 종료
    if (root == NULL) {
        return;
    }

    // 레벨 순회를 위한 큐 생성
    Queue* q = create_queue(); 

    // 첫 번째로 루트 노드를 큐에 삽입
    enqueue(q, root); 

    // 큐가 빌 때까지 반복 → 모든 노드를 순서대로 방문
    while (!is_empty(q)) {

        // 큐에서 가장 먼저 들어온 노드를 꺼낸다(FIFO)
        Node* current = dequeue(q);

        // 현재 노드의 값 출력
        printf("%d ", current->value); 

        // 현재 노드의 왼쪽 자식이 존재하면 큐에 삽입
        if (current->left != NULL) {
            enqueue(q, current->left);
        }

        // 오른쪽 자식이 존재하면 큐에 삽입
        if (current->right != NULL) {
            enqueue(q, current->right);
        }
    }

    // 큐 사용이 끝났으므로 메모리 해제
    // (큐 내부에서 동적할당한 배열/노드가 있다면 별도 해제가 필요할 수 있음)
    free(q);
}

트리의 루트노드를 큐에 넣으며 시작 -> 큐가 빌 때까지 큐의 맨앞 노드를 꺼내 방문처리, 꺼낸 노드에게 자식 노드가 있다면 왼쪽 자식부터 순서대로 큐의 맨뒤에 넣는다 -> 큐가 비면 탐색 완료

• 큐의 선입 선출 방식

노드 개수, 높이 구하기

1. 노드 개수 구하기

트리안의 노드의 개수를 계산, 각각의 서브트리에 대하여 순환 호출한 다음 반환되는 값에 1을 더해 반환한다

• 노드가 NULL이면, 0을 반환
• 노드가 NULL이 아니면, 현재 노드 + 왼쪽 서브트리의 노드 개수 + 오른쪽 서브트리의 노드 개수를 반환

int get_node_count(TreeNode*node)
{
    int count = 0;
    if(node != NULL)
        count = 1 + get_node_count(node->left) + get_node_count(node->right);
    return count;
}

2. 높이 구하기

서브 트리에 대하여 순환호출하고 서브 트리들의 반환값 중에서 최대값을 구하여 반환

• 노드가 NULL이면 0을 반환
• NULL이 아니라면, 왼쪽 서브트리와 오른쪽 서브트리의 높이를 비교하여 큰값 + 1 (현재 노드)을 반환

int get_height(TreeNode*node)
{
    int height = 0;
    if(node != NULL)
        height = 1 + max(get_height(node->left), get_height(node->right));
    return height;

}

탐색, 삽입, 삭제, 성능 분석

이진 탐색 트리 (BST) : 각 노드마다 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 속성을 가짐

왼쪽 서브트리 key <= 루트 노드 key <= 오른쪽 서브트리 key

또한 탐색 작업 시간이 단축된다는 장점이 있음

1. 탐색 연산

특정한 키 값을 가진 노드가 트리 내에 존재하는 지 찾는 연산

• 특정한 키 값보다 작으면 왼쪽 서브 트리
• 크면 오른쪽 서브 트리
• 같으면 현위치 값 반환하여 트리 내에 존재 확인
• NULL이면 찾는 값이 트리에 존재하지 않음

2. 삽입 연산

특정한 값을 노드에 삽입하는 연산

• 먼저 탐색연산 수행
• 새로운 노드 값이 현재 노드 값보다 작으면 왼쪽으로
• 크면 오른쪽으로 이동
• NULL이면 삽입 연산을 수행

3. 삭제 연산

특정 노드를 삭제하는 연산으로, 트리의 BST속성을 유지해야하므로 총 3가지 상황으로 나뉜다

1. 삭제할 노드가 단말 노드인 경우 그냥 단말노드를 삭제하면 됨

2. 삭제할 노드의 자식이 하나 있는 경우 노드를 삭제하고 자식 노드를 삭제된 부모 노드 위치에 연결

3. 삭제할 노드의 자식이 둘인 경우 먼저 오른쪽 서브트리의 최솟값을 찾는 과정이 필요함 그후 오른쪽 서브트리의 최솟값을 가지는 노드를 삭제할 노드의 위치에 연결

코드

// 탐색 (Search)
Node* search(Node* root, int key) {
    // 노드가 없거나 값이 일치하면 해당 노드를 반환
    if (root == NULL || root->value == key) {
        return root;
    }

    // 찾는 값이 더 작으면 왼쪽 서브트리에서 탐색
    if (key < root->value) {
        return search(root->left, key);
    }

    // 더 크면 오른쪽 서브트리에서 탐색
    return search(root->right, key);
}

// 삽입 (Insert)
Node* insert(Node* root, int key) {
    // 비어 있는 위치에 도달하면 새 노드를 생성하여 삽입
    if (root == NULL) {
        return create_node(key);
    }

    // key가 작으면 왼쪽에 삽입
    if (key < root->value) {
        root->left = insert(root->left, key);
    }
    // key가 크면 오른쪽에 삽입
    else if (key > root->value) {
        root->right = insert(root->right, key);
    }
    // 같으면 아무 것도 하지 않음 (BST는 중복 허용X가 일반적)

    return root;  // 루트 반환
}

// 삭제 (Delete)
// 오른쪽 서브트리에서 가장 작은 값을 가진 노드 찾기 (후계자 찾기)
Node* find_min(Node* node) {
    Node* current = node;

    // 가장 왼쪽 끝이 가장 작은 값
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

Node* delete_node(Node* root, int key) {
    if (root == NULL) {
        return root;   // 삭제할 노드가 없음
    }

    // 1) 삭제할 노드를 탐색
    if (key < root->value) {
        root->left = delete_node(root->left, key);
    } 
    else if (key > root->value) {
        root->right = delete_node(root->right, key);
    }

    // 2) 삭제할 노드를 찾았을 때
    else {
        // (1) 자식이 없거나 하나만 있는 경우
        if (root->left == NULL) {
            Node* temp = root->right;   // 오른쪽 자식(있을 수도, NULL일 수도)
            free(root);                 // 현재 노드 삭제
            return temp;                // 자식(혹은 NULL) 반환
        } 
        else if (root->right == NULL) {
            Node* temp = root->left;    // 왼쪽 자식
            free(root);
            return temp;
        }

        // (2) 자식이 둘 다 있는 경우
        // 오른쪽 서브트리에서 가장 작은 값을 찾음 (중위 후속자)
        Node* temp = find_min(root->right);

        // 현재 노드 값을 후속자의 값으로 교체
        root->value = temp->value;

        // 후속자 값을 실제로 삭제
        root->right = delete_node(root->right, temp->value);
    }

    return root;
}

4. 성능 분석

탐색 속도가 BST의 성능과 같다 이는 삽입, 삭제 연산을 할 때에도 탐색과정이 필요하기 때문이다

연산의 시간 복잡도: 트리높이(h) + 1 NULL까지 확인하기 때문에 1더함

시간복잡도를 분석할 때 빅오 표기법을 사용, 연산횟수에 가장 지배적인 요소만을 남기고 삽입과 삭제의 시간복잡도는 아래와 같다

삽입 시간복잡도: O(h) 삭제 시간복잡도: O(h)

• 최선의 경우: 균형 잡힌 트리
• 최악의 경우: 편향된 트리 -> 이를 방지하기 위해 AVL 트리(:자가 균형 이진 탐색 트리, 높이의 균형을 유지함) 사용

그래프

그래프란, 연결되어있는 객체간의 관계를 나타낸 구조이며 정점과 간선으로 이루어짐

그래프 구조를 배울 때 알아야하는 용어와 개념에 대해

용어 정리

정점: 여러가지 특성을 가질 수 있는 개체나 위치를 나타내는 점으로 식별이 가능하다 (노드)

• V (그래프) = {정점의 집합}: 예시 V(G) = {A, B, C, D}

• 인접 정점: 두 정점이 간선으로 연결되어 있다면 두 정점은 인접하다

간선: 정점들 사이의 관계를 나타내는 선 (링크)

• E (그래프) = {간선의 집합}:

  • 무방향: 예시 E(G) = {(A, B), (B, C), (C, A)}

  • 방향이 없는 그래프이다

  • ( ) 소괄호로 묶어 표현한다

  • (A, B)와 (B, A)는 같은 간선이다

  • 방향: 예시 E(G) = {<A, C>, <B, A>, <C, D>, <D, B>}

  • 방향이 있는 그래프이다

  • <> 꺽쇠로 묶어 표현한다

  • <A, B>와 <B, A>는 다른 간선이다

그래프 표현 방법

1. 인접행렬 (이중 배열로 구현)

인접행렬은 두 정점의 간선의 유무를 이중 배열에 저장한다 인접되어 있으면 1로, 인접되어 있지 않으면 0으로 표현한다 n개의 정점을 가진 그래프를 n x n으로 나타낸다

무방향

양쪽 방향으로 연결되어 있어 A-B가 연결이면, B-A도 연결되어야 함

그래서 무방향 그래프에서는 행렬이 대칭이 된다 (edge[a][b] == edge[b][a])

ex) 정점의 개수: 3

  edge[0][1] = 1;
  edge[1][0] = 1;

  edge[1][2] = 1;
  edge[2][1] = 1;

  //출력결과
  //[0, 1, 0]
  //[1, 0, 1]
  //[0, 1, 0]

방향

한쪽 방향으로만 연결되어 있어 A->B는 연결이지만, B->A는 아닐 수 있음

ex) 정점의 개수: 3

  edge[0][1] = 1;
  edge[1][2] = 1;

  //출력결과
  //[0, 1, 0]
  //[0, 0, 1]
  //[0, 0, 0]

구현이 간단하고 연결여부를 빠르게 확인 가능하다는 장점이 있지만, n x n만큼의 메모리를 차지하여 노드 개수가 많을수록 메모리가 낭비된다

2. 인접리스트 (포인터 배열로 구현)

인접리스트는 두 정점을 연결한 간선의 유무를 연결리스트에 저장한다 즉 누구랑 연결되어 있는지만 따로 저장해둔 형태이다 정점의 개수가 총 n개라면, n개의 연결리스트가 있게 된다 구조체를 계속 만들어서 동적할당하므로 구조체의 개수에 따라 메모리가 늘어난다

무방향

각 간선을 두 정점 모두의 리스트에 저장하여 양쪽 방향의 연결을 표현하는 그래프이다 간선이 양방향으로 존재하므로 특정 노드에 연결된 이웃 노드를을 각 정점의 인접리스트에 모두 추가한다

방향

간선을 출발 노드에만 저장한다 정점 A에서 B로 가는 방향 간선이 있다면 A의 인접 리스트에만 B를 추가함

필요한 간선만 저장하여 메모리 사용과 특정 정점에 연결된 모든 정점을 찾을 때 효율적이며 시간복잡도 측면에서 좋다는 장점이 있다. 특정 정점이 연결되어 있는지 확인하려면 리스트 전체를 탐색하므로 연결 여부 확인 속도가 느리다

그래프 순회 / 탐색

하나의 정점에서 시작하여 중복없이 차례대로 모든 정점을 한번씩 방문하는 과정이다

1. DFS (Depth First Search:깊이 우선 탐색)

한 방향으로 갈 수 있을 때까지 가다가 더이상 갈 수 없게 되면 가장 가까운 길로 되돌아감 가장 최근에 넣었던 정점을 꺼내어 그 정점의 다른 이웃을 탐색하기 위해 스택을 사용

• 수직적인 탐색(최대한 아래로 갚숙히 내려가면서 탐색을 진행)
• 한 서브트리나 경로가 완전히 탐색되기 전까지는 다른 서브트리로 넘어가지 않음

void dfs(Graph* graph, int start_node, int visited[]) {
    // 1. 현재 노드를 방문 처리하고 출력
    visited[start_node] = 1;
    printf("%d ", start_node);

    // 2. 현재 노드의 인접 리스트 순회
    Node* current = graph->adj_list[start_node];
    while (current != NULL) {
        int neighbor = current->to;

        // 3. 인접 노드가 아직 방문되지 않았다면 재귀 호출
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
        current = current->next;
    }
}

2. BFS (Breadth First Search:너비 우선 탐색)

시작 정점으로 부터 가까운 (최단 경로) 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문 방문 순서가 선착순이기에 큐를 사용해서 구현됨 + 반복문

• 수평적인 탐색(같은 레벨을 먼저 탐색한 후 거리가 멀어지는 정점들로 넓혀감)
• 시작 정점에서 가까운 정점들을 먼저 방문한다

특징

• 이동거리가 같은 애들은 붙어서 출력
• 특정 정점기준 뒤로는 이동거리가 크거나 같다

ex) A(루트) BC(이동거리 1) DEF(이동거리 2)

void bfs(Graph* graph, int start_node, int visited[]) {
    // 1. 큐 초기화 및 시작 노드 삽입
    Queue* q = create_queue();
    visited[start_node] = 1;
    enqueue(q, start_node);

    // 2. 큐가 빌 때까지 반복
    while (!is_empty(q)) {
        // 3. 큐에서 노드를 꺼내고 출력
        int current_node = dequeue(q);
        printf("%d ", current_node);

        // 4. 현재 노드의 인접 리스트 순회
        Node* current = graph->adj_list[current_node];
        while (current != NULL) {
            int neighbor = current->to;

            // 5. 인접 노드가 아직 방문되지 않았다면 방문 처리 후 큐에 삽입
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                enqueue(q, neighbor);
            }
            current = current->next;
        }
    }
    // 큐 메모리 해제

코딩테스트를 풀며 다른 사람의 풀이를 보았을 때 처음 보는 함수와 메서드를 많이 배웠고 이를 정리하기위해 이 블로그를 쓴다

그럼 여기서 함수와 메서드의 차이는 무엇일까?

함수(function): 독립적인 코드 블록 - functionName()과 같이 이름으로 직접 호출 메서드(method): 특정 객체에 속한 함수, 호출하는 객체가 있음 - object.method()와 같이 점표기법을 사용, 객체를 통해 호출 -> 모든 메서드는 함수이지만, 모든 함수는 메서드가 아님

length

Array인스턴스의 속성으로 배열, 문자열의 요소 수나 길이를 나타냄

• 예시

  for(let i = 0; i < 100; ++i){
    if(n[i] === undefined)
        break;

  몰랐을 때는 위 코드와 같이 if문을 적어 문제를 해결했지만 이러한 방식은 배열의 길이를 모르는 상태에서 100보다 크기보다 작다는 가정에 따라 작성하기 때문에 가정을 벗어난 경우에서는 사용하기 힘들고 쓸데없는 코드가 많아 계산 시간이 걸린다
• 예시

  for(let i = 0; i < n.length; ++i)

  코드를 줄이고 계산 시간도 줄일 수 있다

sort

배열을 정렬하기 위해 사용하는 함수

오름차순: 배열.sort((a,b) => a-b); 내림차순: 배열.sort((a,b) => b-a);

화살표 함수를 이용하여 작성되었다

a, b에 배열 내에 두요소를 전달해서 a-b가 양수면 b가 앞으로 이동해서 작은 수가 앞으로 오게 된다 하지만 함수 내에 파라미터가 입력되지 않으면 문자열의 유니코드대로 정렬한다 (오름차순 정렬)

• 예시 보통 오름차순 정렬을 하기위해 아래와 같이 코드를 작성한다

  for(let i = 0; i < sides.length; i++)
    for(let j = 0; j < sides.length; j++)
        if(sides[i] < sides[j]){
            answer = sides[i];
            sides[i] = sides[j];
            sides[j] = answer;
        }

• 예시

  const [long, a, b] = sides.sort((a,b) => a-b);

push

배열의 끝에 명시된 요소를 추가하고 배열의 새로운 길이를 반환하는 메소드 배열에 요소를 추가할 때에는 push()메소드를 사용함, 이 메서드를 몰랐다면 이러한 방식으로 문제를 풀기 어려웠을 듯하다

• 예시

for(let i = num1; i < num2+1; i++){
    answer.push(numbers[i]);
}

• content: 텍스트와 이미지가 나타나는 내용의 부분으로 width, height 등의 속성을 통해 크기를 조절한다
• padding: content주위에 있는 빈 공간으로 content와 border 사이의 간격을 뜻한다
• border: content, padding을 감싼 테두리를 뜻하며 두께와 색을 조절 가능하다
• margin:가장 바깥쪽 영역으로 이 상자와 다른 요소 사이의 거리를 조절한다

예시)

.box {
  width: 350px;
  height: 150px;
  margin: 10px;
  padding: 25px;
  border: 5px solid black;
}

위와 같은 css코드에서 box가 실제로 차지하는 공간은 가로 (350+25+25+5+5) 410, 세로 (150+25+25+5+5) 210 이다

상자의 영역은 테두리까지만 적용되며 여백은 상자의 실제 크기에 포함되지 않는다.

Block, Inline

display 속성이란 요소를 어떻게 배치하고 보여줄지를 결정하는 것, display의 속성값으로는 대표적으로 none, block, inline, inline-block이 있다

그중에서 Block, Inline의 차이를 설명하겠습니다

• Block 요소 : 전체 칸을 사용하는 태그로는 div, p, h1 등이 있다 : 부모요소의 전체 공간을 차지하여 블록을 만든다, 한줄을 전체 차지함 : 기본적으로 새로운 줄에서 실행을 한다 : 너비, 높이, 상하 margin이나 padding의 크기를 지정할 수 있다

• Inline 요소 : 글자 있는 부분만 공간을 차지하는 태그로는 a, span, em 등이 있다 : 요소를 구성하는 태그에 할당된 공간만을 차지한다 : 새로운 줄을 만들지 않는다 : margin, padding 속성은 좌우간격만 반영되며 상하간격은 반영되지 않는다

box-sizing

box-sizing 속성은 요소의 너비와 높이를 계산하는 방법을 지정한다 content-box:

1. 지정을 따로 해주지 않으면 기본값으로 content-box가 설정된다
2. 요소의 width, height 속성은 콘텐츠 영역의 크기를 나타낸다
3. 너비가 100px이라면 content영역이 100px을 가지고 padding, border가 요소의 겉에 더해져 요소의 총 크기를 정한다

   예시 width: 100px; padding: 10px; border: 5px; 인 요소의 실제 너비는 100+10+10+5+5= 130px이다

border-box:

1. 요소의 width, height 속성이 padding, border의 크기를 포함한 전체 크기를 나타낸다
2. padding, border 속성을 추가하게 되면 콘텐츠의 크기는 작아지며 일정한 크기를 유지하게 된다

   예시 width: 100px; padding: 10px; border: 5px; 인 콘텐츠 영역의 너비는 100-10-10-5-5=70px이다