[개념 콕] 그래프와 트리

내일배움캠프 수료생이 개발에 꼭 필요한 핵심 개념만 콕 집어 드립니다.

May 29, 2024

Contents

그래프 (Graph)트리 (Tree)내일배움캠프는 개발에 필요한 핵심만 배웁니다

✍🏼

개발을 시작하시는 여러분, 정보가 너무 많고 배워야 할 것도 산더미라 어디서부터 시작해야 할지 막막하신가요? 내일배움캠프 수료생들이 4개월 동안 배운 엄선된 핵심 개념을 직접 정리해서 알려 드립니다. 공부하다 막히거나 헷갈리는 개념이 있다면 개념 콕으로 정리해보세요.

그래프 (Graph)

그래프(Graph)란?

그래프(Graph)는 객체들 사이의 연결 관계를 표현하는 자료구조로, 노드(Node)와 엣지(Edge)의 집합으로 정의됩니다.

그래프 용어 정리

1) Node (노드): 그래프를 구성하고 있는 각각의 요소

2) Edge (간선): 그래프를 구성하기 위해 노드와 노드를 잇는 선

3) Weight (가중치): 노드 간 간선에 소모되는 일정 수치

위와 같은 그래프를 가중치 그래프라고 합니다. 가중치 그래프란 가중치 정보를 두어 구성한 그래프를 의미합니다. 반대는 비가중치 그래프로, 가중치 정보가 없는 그래프를 의미합니다.

또한, 그래프는 방향성에 따라 단방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나눌 수 있습니다.

단방향 그래프(Directed Graph): 엣지에 방향이 존재하여 노드 간 이동이 한 방향으로만 가능

무방향 그래프(Undirected Graph): 엣지에 방향이 없어 양방향 이동이 가능

그래프에서 노드와 엣지 개념을 지도로 생각하면 이해하기 쉽습니다.

정점(노드)은 각 지점을 나타내고, 간선(엣지)은 지점 간의 이동 경로를 나타냅니다. 두 지점 사이에는 여러 개의 이동 경로가 존재할 수 있으며, 각 경로마다 소요되는 시간이 다를 수 있습니다.

그래프의 자료구조

인접 행렬 (Adjacency Matrix)

2차원 배열을 사용하여 그래프를 표현하는 방식입니다.

행과 열은 노드를 나타내고, 해당 위치의 값은 두 노드 사이의 엣지 존재 여부 또는 가중치를 나타냅니다. 예를 들어 노드에서 나가서 노드으로 들어오는 간선이 있다면 1, 아니면 0으로 인접 행렬을 채웁니다.

장점

배열에 인덱스로 접근 할 수 있어, 시간 복잡도가 O(1) 입니다.

단점

노드의 개수가 많고, 엣지가 적은 경우 공간 효율성이 떨어집니다.
노드의 개수가 많을 경우 (자바의 경우 3만개 이상) 2차원 배열을 선언 할 수 없습니다.

3만 길이가 넘는 2차원 배열을 생성하면 자바에선 힙 스페이스 에러가 발생합니다.노드 개수가 많아질수록 메모리 사용량이 크게 증가합니다. (O(V^2), V: 노드 개수)

인접 리스트 (Adjacency List)

각 노드마다 인접한 노드들을 리스트 형태로 저장하는 방식입니다.

연결 리스트, 배열, 해시 테이블 등의 자료구조를 사용하여 구현할 수 있습니다.

장점: 노드의 개수가 많아져도 공간 효율이 좋아서 메모리 초과 에러가 발생하지 않습니다.

단점

구현이 복잡합니다.
인덱스로 접근 할 수 없어, 원소를 순회하며 돌아야하기 떄문에 최악의 경우 O(N) 의 시간 복잡도를 가질 수 있습니다.

트리 (Tree)

트리(Tree)란?

트리(Tree)는 그래프의 일종으로, 계층적인 구조를 표현하는 자료구조입니다. 순환 구조가 아니며, 1개의 루트 노드가 존재합니다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖습니다.

트리 용어 정리

루트 노드: 트리에서 가장 상위에 있는 노드를 의미합니다.

부모 노드: 두 노드 관계에서 상위 노드에 해당하는 노드입니다.

자식 노드: 두 노드 관계에서 히위 노드에 해당하는 노드입니다.

리프 노드: 트리에서 가장 하위에 존재하는, 자식 노드가 없는 노드를 의미합니다.

서브 트리: 전체 트리에 속한 작은 트리를 의미합니다.

이진트리

가장 기본적인 트리인 이진 트리에 대해 알아보겠습니다. 이진 트리는 부모 노드의 자식 노드의 개수가 최대 2개인 트리를 의미합니다.

편향 이진 트리

노드들이 한 쪽으로 편향된 이진트리입니다.

포화 이진 트리

트리의 높이가 모두 일정하고, 리프 노드가 꽉 찬 이진트리입니다.

완전이진 트리

마지막 레벨을 제외하고 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 이진트리입니다. 일반적으로 코딩 테스트를 할때는 완전 이진 트리 형태를 사용합니다

트리 표현

배열

배열의 각 요소는 트리의 노드를 나타내며, 노드의 값(알파벳)이 해당 요소에 저장됩니다. 트리의 층(level)에 따라 배열의 인덱스가 할당됩니다. 루트 노드는 0번 인덱스부터 시작하여, 각 층마다 인덱스가 증가합니다. 또한 배열의 크기는 트리의 최대 크기에 맞게 미리 할당되어야 합니다. 이 예시에서는 5개의 노드가 있으므로, 배열의 크기는 5입니다.

인접 리스트

인접 리스트를 이용한 트리 표현은 불균형한 트리나 희소 트리(자식 노드가 적은 트리)에 적합합니다. 루트 노드(A)는 별도로 저장되거나 인접 리스트의 첫 번째 요소로 표현되고, 각 노드의 인접 리스트에는 해당 노드의 자식 노드들이 저장됩니다

내일배움캠프는 개발에 필요한 핵심만 배웁니다

지금까지 꼭 필요한 개발 지식에 대해 알아보았습니다. 내일배움캠프에서는 전문가들이 선별한 핵심 개발 지식으로 개발 공부도, 취업도 보다 효율적으로 할 수 있는데요. 국내 유수의 IT기업 출신 튜터님들과 실습 위주의 독보적인 커리큘럼으로 개발자 취업을 체계적으로 준비해보세요. 내일배움캠프 4개월, 여러분 인생의 가장 큰 터닝 포인트입니다.

CREDIT

글 | 조원호 내일배움캠프 수료생 편집 | 정효재 팀스파르타 에디터