4주차: 비선형 자료구조(집합, 맵, 트리, 그래프)

0. 비선형 자료구조

  자료를 한 줄로 나열하는 리스트(배열), 스택, 큐, 덱 등의 자료 구조는 자료의 순차적 처리에 매우 유리합니다. 그런데 어떤 자료들은 선형적으로 관리하기 어렵습니다. 예를 들어, 2020 도쿄 올림픽 양궁 혼성 대진표를 데이터로 정리한다고 해봅시다.

  선형적 자료 구조로 표현하려면 어떻게 해야 할까요? 어디부터 자료를 정리해야 할지 좀 난감합니다. 이렇게 선형적으로 관리하기 어려운 자료들은 "비선형 자료구조"로 관리할 수 있습니다. 이 대진표의 경우는 "트리"로 관리하면 아주 쉽게 표현할 수 있습니다. 비선형 자료구조에는 어떤 것들이 있는지 알아봅시다!
 

1. 집합(set)

  집합하면 떠오르는 이미지가 있습니다.

  이 집합(set)도 set이 맞지만, 컴퓨터 과학에서 말하는 set은 보통 수학적인 집합과는 조금 다릅니다. 여기서 말하는 set은 "순서와 값의 중복이 없는 자료구조"를 말합니다. 그래서 만약 [1, 2, 3, 3, 4, 5] 라는 데이터를 set으로 저장하면 중복되어있는 3이 하나로 처리되어 {1, 2, 3, 4, 5}로 표현됩니다.
 
  파이썬에서 set을 생성하려면 set() 메소드를 사용합니다. 항목을 추가하려면 add() 메소드를 사용합니다. 여러 데이터를 한 번에 추가하려면 update() 메소드를 사용합니다.

S = set()
S.add(1)
S.add(2)
S.add(3)
S.add(3)
print(S)
# {1, 2, 3}

S.clear()
S.update([1, 2, 3, 3, 4, 5])
print(S)
# {1, 2, 3, 4, 5}

  set은 순서가 없는 자료구조이기 때문에 "인덱스"가 없습니다. 출력 결과만 놓고 보면 분명 순서가 있지만, 그건 표현상 그럴 뿐이고 실제로 set의 인덱스를 호출하면 TypeError가 발생합니다.

S = {1, 2, 3}
print(S[2])
# Traceback (most recent call last):
#   File "~.py", line 2, in <module>
#     print(S[2])
#           ~^^^
# TypeError: 'set' object is not subscriptable

  set은 어디에 써먹을 수 있을까요? 중복이 없다는 점에서 "종류의 수"나 "존재 여부" 등의 파악에 유용합니다. set에 특정한 값이 있는지 확인하려면 in 키워드를 사용합니다. in 키워드는 마치 논리 연산자 처럼 사용되어 결과로 boolean 값을 반환합니다.

S = set({"서울", "대전", "대구", "부산", "광주", "울산", "인천", "세종"})
if input() in S:
    print("찍고")
else:
    print("어디로 가야하죠 아저씨")

# >>>대전
# 찍고
# >>>파주
# 어디로 가야하죠 아저씨

  어떤 원소가 있는지 없는지만 확인하는 경우 set은 list보다 빠른 속도를 자랑합니다. 아직 다루지 않은 개념이지만 알고리즘에서 시간적 효율의 지표가 되는 시간복잡도에서 가장 빠른 속도인 상수시간을 소모합니다. 하지만 순서가 없다는 특징 때문에 특정한 원소를 찾는 작업은 배열에 비해 굉장히 느립니다. 문제 상황에 맞게 적절히 set을 사용할 것인지 list를 사용할 것인지 결정해야 하겠죠?
 
#예제1) 백준 1920 수 찾기
 

2. 맵(map)

  맵은 집합의 확장 버전이라고 생각할 수 있습니다. 민수, 윤수, 종수, 철수, 영수 다섯 명이 카페에 갔습니다. 오늘 처음 알바를 시작한 훈이가 주문을 받는데 다섯 명이 주문한 음료가 다 다릅니다. 일단 주문한 음료를 만들긴 했는데 누가 뭘 시켰는지 모르는 상황입니다. 다행이 훈이가 주문을 받으면서 메모를 해놨습니다.

자바 칩 프라푸치노: 민수
제주 팔삭 자몽 허니 블렌디드: 윤수
자몽 망고 코코 프라푸치노: 종수
헤이즐넛 오트 아이스 쉐이큰 에스프레소: 철수
제주 말차 크림 프라푸치노: 영수

  훈이가 만든 이 메모를 맵이라고 할 수 있습니다. 각 사람은 하나의 음료를 주문했습니다. 만약 여기서 서로 다른 사람이 같은 메뉴를 주문했다고 해도, 각 사람이 주문한 음료는 정해져 있습니다. 여기서 맵의 중요한 개념 두 가지가 필요합니다. 맵에 저장할 데이터의 주인이 될 "key"와 key가 받아서 저장할 데이터인 "value"가 있습니다. 음료는 key가 되고, 각 사람이 주문한 5명의 이름은 value가 되는 것이죠. 100명의 주문 목록을 기록했다고 해도, 그 안에 존재하는 key를 찾으면 그 음료를 누가 주문했는지 알아내는 것은 매우 쉽습니다. key에 담긴 value를 바로 꺼내오기만 하면 되기 때문입니다.

  만약 맵이 아닌 배열로 주문 목록을 관리해 주문한 순서대로(선형적으로) 주문 음료를 쭉 나열해두었다면 철수가 몇 번째로 주문했는지 확인한 다음에 주문 번호에 해당하는 음료를 찾아야 합니다. 하지만 맵으로 자료를 정리한다면 음료만 찾아서 바로 그 옆에 적인 주문자 이름을 확인하면 되기 때문에 역시 더 효율적입니다.

 
  파이썬에서 맵은 map() 함수를 사용해야 할 것 같지만 우리가 원하는 자료구조는 dict() 함수를 사용합니다. map() 함수는 셀 수 있는 자료(리스트, 튜플 등의 특징으로 iterable이라고 부릅니다.)의 원소를 각각 다른 형식으로 대응시켜 변환하여 다시 iterable로 내어놓는 함수입니다. 기능 자체는 맵이 맞지만 자료구조 자체로 사용할 수는 없죠. dict()로 맵을 생성해봅시다.

m = dict()
m["자바칩"] = "민수"
m["제주자몽"] = "윤수"
m["자몽망고"] = "종수"
m["헤이즐넛"] = "철수"
m["제주말차"] = "영수"

print(m["자몽망고"])
# 종수

print(m)
# {'자바칩': '민수', '제주자몽': '윤수', '자몽망고': '종수',
#  '헤이즐넛': '철수', '제주말차': '영수'}

  다섯 명의 음료가 key로 지정되어 주문자 이름을 value로 갖습니다. 그리고 dictionary의 key에 저장된 value를 알고 싶으면 배열을 다루듯이 인덱스가 들어갈 자리에 key를 넣어주면 됩니다. 사용법이 엄청 간단하죠? 여기서 주의할 점이 있습니다. key는 중복될 수 없습니다. key가 여러 개가 되어버린다면, 쉽게 value에 접근할 수 있다는 맵의 장점이 완전히 사라져버리겠죠. 그래서 한 번 만들어둔 key를 다시 불러 새 값을 지정하면, 새로운 key가 생겨나는 것이 아니라 기존 key와 연결된 value를 수정하게 됩니다.
 
#예제2) 백준 27160 할리갈리
 

3. 트리(tree)

  어떤 자료는 순서보다 서로의 연결 관계가 중요하기도 합니다. 자료의 연결 관계를 나타낼 때는 "트리(tree)"를 활용할 수 있습니다. 우리 주변에서 찾아볼 수 있는 가장 대표적인 트리인 디렉터리를 봅시다.

windos는 오타입니다ㅎ

  폴더 간에는 상하 관계가 있습니다. C: 드라이브 폴더 안에는 windows, program files, user 등의 폴더가 있고, windows 폴더 안에는 fonts 등의 폴더가 또 들어있습니다. 이렇게 하나의 폴더에서 출발해 하위 폴더로 쭉 이동할 수 있는 자료의 구조를 트리라고 합니다. 트리가 가진 중요한 특징은 "최상위 개체를 제외한 모든 개체가 유일한 부모를 갖는다."는 것입니다. 어떤 폴더를 보아도 상위 폴더가 2개인 경우는 없습니다. 이 조건을 만족한다면 트리가 될 수 있습니다.

  트리는 이름 그대로 나무의 모양을 닮았습니다. 최상위에 있는 개체는 나무의 시작점인 뿌리이기 때문에 "루트(root)"라고 부릅니다. 가장 마지막에서 하위 개체 없이 있는 개체는 "리프(leaf)"라고 합니다. 이렇게 연결 관계를 나타낸 것을 위상수학에서는 그래프(graph)라고 부릅니다. 우리가 흔히 보는 통계학의 그래프와는 다릅니다. 그래프에서 개체는 "정점(vertex 또는 node)", 정점을 잇는 선은 "간선(edge)"라고 합니다. 상하 관계에 놓인 두 정점을 놓고 보면 상위 정점은 "부모(parent)", 하위 정점은 "자식(child)"이라고 부릅니다.
 
  트리의 특징을 정리해보면 이렇습니다.

- 루트를 제외한 모든 정점은 유일한 부모를 갖는다.
- 두 정점 사이를 잇는 간선은 최대 하나만 존재한다.
- v개의 정점으로 트리를 구성하면 간선의 수 e는 v-1이다.

  트리를 사용하면 어떤 점이 좋을까요? 우리가 파일 디렉터리를 만드는 이유와 같습니다. 자료를 체계적으로 관리할 수 있고, 탐색 시간을 줄이는 효과가 있습니다. 10억개의 자료를 한 줄로 나열했을 때, 특정 자료를 찾으려면 최대 10억개의 자료를 모두 확인해봐야 합니다. 하지만 1개의 루트를 두고, 자식을 2개만 두어서 남은 자료를 반씩 나누어 저장해줘도 어떤 간선을 타고 가야하는지 알 수 있다면 5억개 이하의 자료만 확인해보면 됩니다. 이진트리로 관리한다면 어떤 정점이든 30번 이내로 탐색을 마칠 수 있습니다.
 
  트리는 어떻게 표현해야 좋을까요? 비선형 자료구조이지만 의외로 선형 자료구조인 "리스트"로 표현할 수 있습니다. 각 정점에 번호를 부여하고, 각 정점마다 연결되는 정점을 기록하는 방법이죠. 좀 더 구체화하면 하나의 부모 노드와 자식 노드 들을 저장하여 관리할 수 있습니다.

  이렇게 각 정점마다 번호를 부여하고 번호마다 자식 노드의 번호를 부여할 수 있습니다. 하지만 이런 방법은 루트가 0이라는 것이 정해졌을 때의 이야기이고 좀 더 확실하게 표현하려면 맨 앞에 부모 노드의 번호를 저장하는 식으로 관리할 수 있습니다. 루트인 0번 노드는 부모 노드 번호를 -1로 부여하기도 합니다.
 
#예제3) 백준 14244 트리 만들기
 
  트리 중에서 자식을 딱 둘씩만 갖도록 한 트리를 "이진 트리(binary tree)"라고 합니다. 이진 트리는 왼쪽으로 내려가느냐, 오른쪽으로 내려가느냐를 나누어 자료를 저장합니다. 어, 그런데 부모 노드에게 자식 노드를 많이 많이 넣어주면 트리 탐색에서 정점을 많이 거치지 않고도 원하는 자료를 찾을 수 있으니 더 좋지 않을까요? 왜 자식 노드를 둘만 넣어서 관리하는 걸까요? 다음 그림은 이진 트리의 모습을 나타냅니다.

  부모 노드와 자식 노드 사이의 어떤 규칙이 보이나요? 부모 노드의 번호가 i라면 자식 노드는 i*2(왼쪽)와 i*2+1(오른쪽)이 됩니다. 이렇게 되면 엄청난 장점이 하나 주어지는데 바로 정점 간의 연결 관계를 관리하지 않아도 된다는 것입니다. 어떤 정점을 골라도 반드시 자식 노드의 번호를 알 수 있으니까요. 
 
  그냥 트리의 특수한 경우이지만 오히려 이진 트리가 더 일반적으로 많이 쓰이고 있기 때문에 잘 알아두셔야 합니다. 아래 문제는 이진 트리의 더 특수한 경우인 "완전 이진 트리"를 다룹니다. 정점의 번호가 가진 규칙을 잘 생각해보며 해결해봅시다.
 
#예제4) 백준 11203 Numbers On a Tree
 
  트리에 관한 자세한 내용은 아래 한치 선생님의 글도 참고해보세요.

🐨자료구조]트리

 

4. 그래프(graph)

  트리를 설명하며 간단히 소개를 했습니다만, 정점 간의 연결 관계를 나타낸 것을 "그래프(graph)"라고 합니다. 위상수학의 그래프를 처음 접하는 분들은 조금 혼란스러울 수 있지만 이미 우리에게 꽤 익숙한 개념입니다. 한붓그리기, 도로, 인물 관계도, 먹이사슬 등이 우리 주변에서 흔하게 볼 수 있는 그래프입니다.

엄밀하게는 좀 애매한 그래프입니다.

 
  그래프는 연결 관계를 나타내는 모든 것을 넓게 이르는 말이기 때문에 트리도 그래프에 포함이 됩니다. 트리가 될 수 없었던 친구 관계 같은 것도 그래프가 됩니다. 그래프는 몇 가지 분류가 있습니다.

- 간선에 방향이 있으면 "방향 그래프", 없으면 "무향 그래프"
- 어떤 정점에서 출발해 간선을 중복 선택하지 않고 다시 돌아올 수 있으면 "순환 그래프", 아니면 "비순환 그래프"
- 두 정점을 잇는 간선이 여러 개면 "다중 그래프"
- 간선에 비용이 있다면 "가중 그래프", 간선에 제한이 있다면 "유량 그래프"
- 두 가지의 색으로 모든 정점을 이웃하는 정점과 다른 색으로 칠할 수 있다면 "이분 그래프"
- ...

  각각의 개념을 지금 당장 알 필요는 없습니다. 어쨌든 중요한 건, 정점 간의 관계를 선으로 이어 표현한 자료 형태가 그래프이며 역시 트리와 같이 리스트 등으로 연결되어있는 정점 번호를 관리하는 식으로 표현합니다. 제가 주로 사용하는 방법을 두 가지 소개하면 이렇습니다.
 

(1) 인접행렬로 표현하기

  그래프에서 서로 연결된 노드를 행렬의 형태로 표현하는 것을 인접행렬이라고 합니다. 정점의 수가 v라면 인접행렬 G는 v*v크기의 정사각행렬이 됩니다. 파이썬에서 이걸 표현하려면 2차원 배열을 활용합니다. 2차원 배열은 배열 안의 각 원소가 배열인 형태로, 1반부터 10반까지 있는 3학년이 각 반을 원소로 갖는 배열, 각 반이 20명씩 있다면 각 반이 20명의 원소를 갖는 배열이 되고 3학년은 2차원 배열의 형태가 되겠죠.

arr = [[0 for i in range(5)] for j in range(3)]
print(arr)
# [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

arr[0][2] = 2
arr[1][0] = 3
arr[2][3] = 5
print(arr)
# [[0, 0, 2, 0, 0], [3, 0, 0, 0, 0], [0, 0, 0, 5, 0]]

  이런 식으로 작동합니다. 처음 2차원 배열을 다루게 되면 두 개의 인덱스를 다루는 것에서 많이 혼란스러울 수 있습니다. 하지만 우리가 지금 알아보는 그래프는 무향 그래프이며, 무향 그래프는 인접행렬로 나타낼 경우 G[i][j]와 G[j][i]가 같습니다. 왜냐하면 i번 정점에서 j번 정점으로 이동할 수 있다면 j번 정점에서 i번 정점으로 이동하는 것 역시 가능하기 때문입니다. 해서 어떤 그래프 G에서 v번 정점에서 u번 정점으로 간선이 연결되어 있다면 G[u][v] = 1로, 연결되어 있지 않다면 G[u][v] = 0으로 표현합니다. 만약 간선에 비용이나 제한이 있는 가중 그래프 또는 유량 그래프라면 G[u][v]의 값을 가중치로 설정할 수 있습니다.

(2) 맵(dictionary)으로 표현하기

  인접행렬은 그래프를 구현할 수 있는 매우 편리한 방법입니다만 한 가지 단점이 있습니다. 바로 불필요한 메모리를 너무 많이 먹는다는 것입니다. 총 100개의 정점이 있고 이 정점을 모두 연결하는 최소의 간선인 99개의 간선이 연결 그래프를 완성했다고 해봅시다. 우리가 필요한 간선 정보는 99개 뿐이지만 인접행렬로 이 그래프를 표현하려면 100*100크기의 2차원 배열이 필요합니다. 10000개의 저장 공간에서 고작 99개의 간선만 저장됩니다. 무향 그래프라고 해줘도 198개 밖에 사용하지 않고 나머지 모두 사용하지 않게 됩니다. 이럴 때 맵을 활용하면 좋습니다.

graph = dict()
# 5개의 노드의 연결 정보를 빈 배열로 각각 graph에 저장
for i in range(5):
    graph[i] = []

# q개의 간선 정보를 u v 형태로 입력 받고 graph에 저장
q = int(input())
for i in range(q):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

  이 방법은 간선 정보를 맵과 배열을 적절히 섞어서 보관합니다. i번 정점과 j번 정점 사이의 간선을 graph[i]에 들어있는 배열에 추가(append)하는 방식입니다. 동시에 graph[j]에 들어있는 배열에도 역시 i를 추가합니다.

  이 그래프는 무향 그래프이고 5개의 정점, 7개의 간선을 갖고 있습니다. 만약 인접행렬로 표현했다면 5*5 크기의 2차원 배열을 썼을테니 간선 정보가 저장되는 14개를 제외한 11개의 공간은 텅 빈채로 남아있겠죠. 하지만 이 방법을 사용하면 딱 14개만큼의 저장 공간을 사용하고 있다는 것을 알 수 있습니다. (정확히는 5개의 정점으로는 차이가 없습니다. 한 1000개 쯤 되면 유의미한 메모리 차이가 발생합니다.)
 
#예제5) 백준 9255 The Friend of My Enemy is My Enemy
 
  트리를 포함한 그래프는 알고리즘 공부에서 매우 중요한 개념입니다. 많은 알고리즘들이 이 그래프를 기반으로 세워진 이론에서 나왔습니다. 하지만 그만큼 그래프 자체만을 다루는 문제는 잘 없습니다. 그래프를 구현하고 그 안에서 원하는 정보에 접근하는 방법은 다음 시간, 탐색에서 배워보도록 하겠습니다.