집합

집합이란?

• 개념: 순서와 중복이 없는 원소들을 갖는 자료구조
• 종류: 유한 집합, 무한 집합 등, 중요한 것은 상호배타적 집합
  • 상호배타적 집합: 교집합이 없는 집합 관계
    • 이를 활용하여 이미지 분할, 최소 신장트리 알고리즘 구현, 클러스터링 작업 등이 가능하다.

상호배타적이다.

 

집합의 연산

 

배열을 활용한 트리로 표현

• 대표 원소: 집합을 대표하는 원소 -> 루트 노드를 생각하자
• 하나의 배열로 상호 배타적 관계를 가지는 집합을 모두 표현한다. 집합을 트리로 변경 시 "배열의 값=인덱스의 부모노드"
• ex) set[9] = 3 -> 9의 부모는 3

 

유니온-파인드 알고리즘

• 집합 알고리즘에 주로 쓰이는 연산: 합치기&탐색 = Union&Find -> 찾고나서 합치자

 

Find 연산

• 특정 노드의 루트 노드 탐색
• A,B 두 노드의 루트 노드가 같다? -> 같은 집합

1. 현재노드의 부모노드 확인
2. 부모노드가 루트노드이면 종료
3. 찾기 연산이 종료될 때까지 반복

• 재귀함수로 구현한다. 
• 하지만 최악일 때 시간 복잡도가 O(N) -> 경로 압축으로 해결

 

Find 연산 비용문제 -> 경로 압축

• 집합 형태를 유지하며 트리 높이를 줄인다.

 

Union 연산

• 두 집합을 하나로 합침 = 두 집합의 루트노드를 같게 한다.

1. 두 집합에서 찾기 연산을 통해 루트노드를 찾는다.
2. 찾은 두 루트 노드를 비교한다
3. 두 집합의 루트노드를 같게하여 합친다. 루트노드는 어떤 루트노드해도 상관없다.

 

Union 연산 비용문제 -> 랭크

• 현재 노드 기준으로 가장 깊은 노드까지의 경로 길이

1. 두 노드의 루트노드 구하기
2. 각 루트노드의 랭크 비교
   1. 랭크값이 다르면 큰 노드 기준 -> 랭크가 큰 루트노드를 랭크가 작은 루토느드의 부모노드로 변경
   2. 랭크값이 같으면 아무거나 선택

 

상호배타적 집합 표현위해서 필요한 연산

• find(parents,x): x가 속한 집합의 대표원소 찾기
  • x의 부모가 자기자신이면, 즉 x가 루트노드이면 루트노드는 x이고
  • 그렇지 않다면, 부모의 루트노드가 나올 때까지 재귀
•  union(parents,x,y): x,y가 속한 두 집합을 합친다.
  • x가 속한 집합의 루트노드와 y가 속한 루트노드 찾기
  • y가 속한 집합을 x가 속한 집합에 합친다.

 

문제

폰켓몬

https://school.programmers.co.kr/learn/courses/30/lessons/1845

def solution(nums):
    answer = 0
    k= len(nums)//2
    return min(len(set(nums)),k)

 

영어 끝말잇기

https://school.programmers.co.kr/learn/courses/30/lessons/12981

def solution(n, words):
    answer = []
    '''
    탈락기준
    1) 글자의 맨앞과 다음 글자의 맨뒤를 비교해서 다르면 탈락
    2) 이전에 등장했으면 탈락 -> 집합을 만들고, 말하는 단어가 집합에 있는지를 구별하면 됨
    '''
    lens=len(words)
    acc=words[0][0]
    sets=set()
    for i,word in enumerate(words):
        if word[0]!=acc or word  in sets:
            return [(i%n)+1,(i//n)+1]
        acc=word[-1]
        sets.add(word)

    return [0,0]

 

전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

def solution(phone_book):
    answer = True
    '''
    1. 오름차순으로 정렬
    2. 접두사 = startswit로 자기 기준 바로 뒤만 비교
    '''
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return True