[ KB IT's Your Life 7기 ]코딩테스트 알고리즘 특강 후기

 

 

안녕하세요! KB IT's Your Life 7기 기자단입니다!

코딩테스트 특강이 어느덧 끝나가고 있는데요!

 

아직도 너무너무 어렵고 힘드네요 ㅠㅠ...

오늘은 트리의 기본 개념부터 DFS, BFS 구현, 그리고 전위·중위·후위 순회까지

수업에서 배운 내용을 정리해봤으니 끝까지 읽어주세요!

---

트리(Tree)가 뭔데?

트리는 그래프의 특수한 형태예요.

일방향이고, 비순환이고, 부모-자식 관계로 맺어지는 계층형 자료구조죠

쉽게 말하면 컴퓨터 폴더 구조를 생각하면 돼요. C드라이브 안에 문서 폴더가 있고, 그 안에 또 하위 폴더가

있는 것처럼 위에서 아래로 뻗어나가는 구조가 바로 트리예요.

 

여기서 꼭 알아야 할 용어들이 있는데요!!

 

루트 노드: 트리의 맨 꼭대기에 있는 노드. 부모가 없는 유일한 노드예요.

리프 노드: 자식이 하나도 없는 맨 끝단 노드.

차수: 특정 노드에 연결된 자식 노드의 개수. 트리 전체의 차수는 가장 자식이 많은 노드의 차수를 따라가요.

레벨: 루트 노드에서부터의 거리. 루트가 레벨 0이면 바로 아래가 레벨 1, 그 아래가 레벨 2...

조상 노드: 특정 노드의 부모, 부모의 부모, 쭉 올라가는 모든 노드.

이 용어들이 나중에 문제 풀 때 계속 나오니까 여기서 확실히 잡고 가는 게 좋아요!

 

트리의 종류 — 이진트리, 완전 이진트리, N진트리

 

트리에도 종류가 있어요. 그래프에 종류가 있듯이!

이진트리(Binary Tree): 모든 노드가 최대 2개의 자식만 가지는 트리예요.

왼쪽 자식, 오른쪽 자식 이렇게 부르고, 하나만 있어도 괜찮아요.

 

완전 이진트리: 이진트리인데 마지막 레벨 빼고는 다 꽉 채워져 있고,

마지막 레벨도 왼쪽부터 순서대로 채워진 형태예요.

N진트리: 자식 노드를 N개까지 가질 수 있는 일반적인 트리.

특별한 제약 없이 자유롭게 뻗어나가는 형태라고 보시면 돼요.

 

강사님이 "트리의 종류는 그래프 종류보다 문제에서 직접적인 연관이 있다"고 하셨는데

실제로 이진트리냐 N진트리냐에 따라 코드 구현 방식이 달라지더라고요.

---

트리 구현 — 인접 리스트, 간선 리스트, 클래스

출처 입력

트리를 코드로 어떻게 표현하느냐? 이게 핵심이었어요.

 

 

인접 리스트

그래프 때 했던 그 인접 리스트 맞아요! 트리도 결국 그래프의 일종이니까 똑같이 쓸 수 있어요.

일방향 트리면 부모에서 자식 방향으로만 넣으면 되고

양방향으로 주어지는 경우도 있는데 그때는 문제에서 루트 노드를 따로 알려줘요.

 

간선 리스트

"0번이랑 1번 연결, 0번이랑 2번 연결, 2번이랑 3번 연결..."

이런 식으로 연결 정보만 쭉 나열한 형태인데 DFS나 BFS 쓰려면

결국 인접 리스트로 변환해야 해서 한 단계를 더 거쳐요.

 

클래스 구현 (노드)

이게 좀 새로웠어요! 이진트리를 클래스로 구현하면 이런 식이에요:

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }
}

 

value에 값을 저장하고, left랑 right로 자식 노드를 가리키는 구조. 루트 노드 하나만 알면 거기서부터

left, right를 따라가면서 전체 트리에 접근이 가능해요.

 

N진트리일 때는 left, right 대신 List<Node> children으로 자식 노드를 리스트에 담으면 되고요.

---

트리 순회 — BFS (너비 우선 탐색)

 

자 이제 트리를 만들었으면 순회를 해야죠!

데이터를 저장해놨으면 꺼내서 확인할 수 있어야 의미가 있으니까요

BFS는 같은 레벨에 있는 노드들을 먼저 다 방문하고 그다음 레벨로 넘어가는 방식이에요.

그래서 레벨 순서 순회라고도 불러요.

 

구현도 그래프 때 했던 거랑 거의 똑같아요. 큐(Queue) 쓰면 끝!

근데 여기서 중요한 포인트가 하나 있었는데요, 일방향 트리에서는 visited 배열이 필요 없어요!

그래프에서는 양방향이라 갔던 데를 또 가고 또 가고 무한 루프가 돌 수 있잖아요.

근데 일방향 트리는 부모에서 자식으로만 가니까 한번 내려가면 다시 올라올 일이 없어요.

순환도 없고 일방향이니까 visited 체크 없이도 안전하게 돌 수 있는 거예요.

물론 양방향으로 주어지면 visited를 써야 합니다!

---

트리 순회 — DFS (깊이 우선 탐색)

 

트리에서는 사실 DFS가 훨씬 많이 쓰여요. 왜냐면 트리 자체가 재귀적인 구조거든요.

루트 노드 아래에 서브트리가 있고 그 서브트리도 자세히 보면 또 루트 노드와 서브트리로 이루어져 있고...

이게 딱 재귀 구조잖아요!

그래서 DFS로 트리를 순회할 때는 이런 흐름이에요

 

1. 현재 노드 방문
2. 자식 노드들에 대해 DFS 실행
3. 끝까지 갔다가 돌아오기

 

근데 여기서 현재 노드를 언제 처리하느냐에 따라 세 가지로 나뉘어요. 이게 바로 전위순회, 중위순회, 후위순회!

---

전위순회 · 중위순회 · 후위순회

 

전위순회 (Pre-order)

나 먼저 처리하고 → 자식 노드 DFS

현재 노드에 도착하자마자 바로 방문 처리를 하고 그다음 자식들을 탐색하는 방식이에요.

디렉토리(폴더) 구조를 출력할 때 이런 방식을 쓴다고 해요.

폴더에 들어가면 일단 폴더 이름을 확인하고 그 안에 있는 하위 폴더를 또 탐색하는 거죠.

 

중위순회 (In-order)

왼쪽 자식 DFS → 나 처리 → 오른쪽 자식 DFS

이진트리에서만 쓰이는 순회 방식이에요. 이진 탐색 트리(BST)를 중위순회하면 오름차순 정렬된 숫자가 나온다는 특성이 있어요. 강사님이 이건 출제 빈도가 높진 않다고 하셨지만 알아두면 좋은 개념!

후위순회 (Post-order)

자식 노드 DFS 다 하고 → 그 다음에 나 처리

코딩테스트에서 가장 많이 쓰이는 건 후위순회입니다!!

왜 그러냐면 자식 노드들이 알아서 자기 할 일 하고 결과를 리턴하면

부모 노드가 그 결과를 취합해서 최종 답을 만드는 구조가 대부분이거든요.

 

예를 들어 이 트리의 전체 노드 개수를 구해라 같은 문제. DFS 함수가 자식들한테 "니네 밑에 노드 몇 개야?"

시키면, 자식들이 알아서 세서 결과를 리턴하고 부모는 그거 다 더한 다음에 자기 자신 +1만 하면 끝이에요.

int dfs(int root, List<List<Integer>> tree) {
    int answer = 1; // 나 자신 포함
    for (int child : tree.get(root)) {
        answer += dfs(child, tree);
    }
    return answer;
}

 

이 코드 하나로 전체 노드 개수가 나와요.

 

같은 구조로 노드 값의 총합도 구할 수 있어요. answer = 1 대신 answer = values[root]로 바꾸면 끝! 자식들이 리턴한 합을 다 더하고, 나의 값을 더하면 전체 총합이 나오는 거예요.

**최대 깊이(Maximum Depth)**도 후위순회로 풀 수 있었어요. 자식들한테 "니네 쪽 최대 깊이가 몇이야?" 물어보고, 그중 제일 깊은 거 골라서 +1 하면 끝!

---

핵심 포인트를 정리할게요

- 노드가 N개면 간선은 N-1개 트리에서는 루트 노드 빼고 모든 노드가 부모와 연결돼 있으니까 간선 개수는 항상 노드 수 - 1이에요. 문제에서 "간선이 N-1개" 나오면 "아 이거 트리 문제구나!" 바로 파악 가능!

- DFS를 돌린다 = 트리의 정보를 취합하는 것 DFS 실행 자체가 서브트리의 정보를 모아서 위로 올려보내는 과정이에요. 자식한테 시키고 → 결과 받아서 → 내가 처리하는 구조.

 

- 재귀적 사고가 핵심 전체를 한번에 풀려고 하지 말고 내가 할 일을 정의하고

자식들한테 똑같이 시키면 트리 전체가 해결된다.

이게 트리 + DFS 문제 풀이의 본질이었어요.

 

마치며

아무리 봐도 봐도 어렵고 아직 갈 길이 멀지만 하나씩 쌓아가는 느낌이 들어서 좋습니다.

계속해서 반복하다보면 저도 고수가 될 수 있겠죠...?

지금까지 읽어주셔서 감사합니다 !! 다음 포스팅에서 봐요!