"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 10장의 써머리입니다."

10. 집합

1) 집합과 상호 배타적 집합의 개념

집합의 개념

집합 : 순서와 중복이 없는 원소들을 갖는 자료구조(순서X)

집합의 종류

• 특성에 따라 부르는 말이 다양함

유한 집합 : 원소 개수가 유한한 집합

무한 집합 : 원소 개수가 무한한 집합

상호 배타적 집합이란?

상호 배타적 집합 : 교집합이 없는 집합 관계를 의미

A = {1, 2, 3}이고 B = {4, 5, 6, 7}일 때 서로 겹치는 원소가 없으면 교집합이 없다고 할 수 있고, 이를 상호 배타적 집합이라고 함

상호 배타적이지 않은 집합 → 원소 5가 집합 A와 집합 B에 존재하기 때문

상호 배타적 집합의 특성을 활용하는 분야

• 이미지 분할 : 이미지를 서로 다른 부분으로 나누는 데 사용
• 도로 네트워크 구성 : 도로를 구축할 때 각 도로를 서로 교차하지 않도록 설계하는 데 사용
• 최소 신장 트리 알고리즘 구현 : 최소 신장 트리 알고리즘을 구현에서 간선을 추가할 때마다 사이클을 형성하는지 여부 체크
• 게임 개발 : 캐릭터의 동작을 자연스럽게 구현 가능
• 클러스터링 작업 : 각 작업이 서로 겹치지 않도록 구성 가능
  
  

2) 집합의 연산

배열을 활용한 트리로 집합 표현하기

집합은 배열을 활용한 트리로 구현, 각 집합에는 대표 원소가 필요

대표 원소란?

집합의 원소 중 집합을 대표하는 역할

배열로 집합을 표현한 것이란?

하나의 배열로 상호 배타적 관계를 가지는 집합을 모두 표현한다는 것을 의미

집합 → 트리 형태로 표현 시 배열의 인덱스는 자신을, 배열 값은 부모 노드를 의미

eg) disjoint_set[3] = 9일 때, 부모 노드 = 3

즉, 루트 노드는 값 자체가 배열의 인덱스와 동일

→ 그림에서 값이 가장 큰 원소가 9이므로 배열의 크기는 10으로 잡기

집합 표현 완벽 정리하기

집합을 배열로 구현하기

01 단계) 집합을 배열로 표현 시 초기 상태

초기 각 노드는 자신을 루트 노드로 하였고, 집합에 없는 인덱스는 -1로 처리

02 단계) 집합이 완성되었을 때, 집합 A는 {1, 2, 3, 5, 9}이고, 집합 B는 {4, 8}. 루트 노드는 음영 처리, 점선으로 노드 9의 루트 노드를 찾는 과정 표시(9 → 3 → 2 → 1)

유니온-파인드 알고리즘

집합 알고리즘에 주로 쓰이는 연산은 합치기(Union)와 탐색(Find)이다.

파인드 연산

특정 노드의 루트 노드가 무엇인지 탐색하는 방법

보통 특정 노드가 같은 집합에 있는지 확인 시 사용(찾기 연산)

1) 현재 노드의 부모 노드 확인. 부모 노드 확인 시 부모 노드 = 루트 노드이면 찾기 연산 종료

2) 1에서 찾기 연산이 종료되지 않으면 1을 반복(현재 노드 $\neq$ 부모 노드)

탐색 연산은 재귀 함수로 구현 - 루트 노드를 현재 노드와 부모 노드가 같을 때까지 재귀 실행

파인드 연산의 연산 비용 문제, 경로 압축으로 해결하자

좀 더 효율적으로 파인드 연산을 하기 위해 집합 형태를 유지하면서도 트리 높이를 줄이면 됨

트리의 높이를 줄이는 게 부모 노드를 거치는 과정을 줄일 수 있음

합치기(유니온) 연산

두 집합을 하나로 합치는 연산 = 두 집합의 루트 노드를 같게 하는 것

1) 두 집합에서 찾기 연산을 통해 루트 노드 찾기

2) 찾은 두 루트 노드의 값 비교

3) 두 집합 합침. 두 집합의 루트 노드를 같게 하는 것

합치기 연산의 연산 비용 문제, 랭크로 해결하자

트리의 깊이가 깊어지면 깊어질수록 연산 비용 ↑ ⇒ 개선하기 위해 랭크 필요

* 랭크 개념 도입 목적 : ‘트리의 균형을 유지하기 위함’

랭크란?

현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 의미

랭크 기반으로 합치기 연산하기

1) 두 노드의 루트 노드 구하기

2) 1에서 구한 루트 노드의 랭크 비교

2-1) 랭크값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼기

2-2) 랭크값이 같으면 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더함

3) 몸 풀기 문제

문제 33) 간단한 유니온-파인드 알고리즘 구현하기

초기의 노드는 부모 노드를 자신의 값으로 설정했다고 가정하며, 여기서는 각 집합의 루트 노드를 기준으로 루트 노드가 작은 노드를 더 큰 노드의 자식으로 연결하는 방법 사용. operations에 있는 연산을 모두 수행한 후 집합의 개수를 반환하는 solution() 함수 구현

def union(nodes, x, y):
  
  node1 = find(nodes, x)
  node2 = find(nodes, y)
  
  nodes[node2] = node1

def find(nodes, x):
  
  if nodes[x] == x:
    return x
  else:
    nodes[x] = find(nodes, nodes[x])
    return nodes[x]

def solution(k, operations):
  nodes = list(range(k))
  
  for op in operations:
    if op[0] == 'u':
      union(nodes, op[1], op[2])
    elif op[0] == 'f':
      find(nodes, op[1])
      
  n = len(set(find(nodes, i) for i in range(k)))
  print("n : ", n)
  
  return n

k = 3
operations = [['u', 0, 1], ['u', 1, 2], ['f', 2]] # result = 1
solution(k, operations)

k = 4
operations = [['u', 0, 1], ['u', 2, 3], ['f', 0]] # result = 2
solution(k, operations)

4) 합격자가 되는 모의 테스트

문제 36) 전화번호 목록

전화번호부에 적힌 전화번호 중 한 번호가 다른 번호의 접두어인 경우가 있는지 확인. 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution() 함수의 매개변수로 주어질 때 어떤 번호가 다른 번호의 접두어이면 False, 그렇지 않으면 True를 반환하는 함수 작성

def solution(phone_book):
	phone_book.sort()

    for i in range(len(phone_book) - 1):
        if phone_book[i+1].startswith(phone_book[i]): 
            return False

    return True