[Algorithm] c로 배우는 알고리즘/이재규/그래프/집합의 표현/작성중

공부해보면서 python으로 테스트 해봅니다.

19년 6월에 c로 한번 구현 해봤지만, 역시 반복이 중요

출처 : C로 배우는 알고리즘/활용 알고리즘편/이재규 지음/도서출판 세화

1. 집합

집합 개론

>> 명확히 구별 가능한 원소들의 집단  

>> 특징 : 구별 가능함, 무순서
>> 구별 가능함 : 어떤 집합이 있을 때, 임의의 원소가 그 집합에 포함되는 것인지 아닌지 명확히 구분할 수 있음  
>> 무순서 : 집합을 구성하는 원소들 사이에는 순서가 없다.

집합을 다루는 문제는 두 가지로 압축 가능

>> 1. 검색(find) 문제 : 어떤 원소가 어떤 집합에 포함되는지 아닌지를 알아내는 문제
>> 2. 결합(Union) 문제  : 두 개의 서로 다른 집합을 하나의 집합으로 합치는 문제 

집합을 표현하는 방법

>> 배열 표현
>> 그냥 선형적으로 저장하는 것이지
>> 정렬 여부에 따라 성능과 작동이 달라지는 특징 
    >> 노 정렬, 검색의 시간 소요량은 O(N)
    >> 노 정렬, 두 집합 합치기 시간 소요량은 O(M), M은 복사할 배열의 크기 

>> 그래프 표현
>> 하나의 연결 요소에 속하는 정점들은 모두 같은 집합으로 볼 수 있다. 
>> 깊이 우선 탐색을 이용해서 원소간의 연결 여부를 파악하는 방식이 있겠지 
>> 두 집합 합치기 문제의 경우, 일괄적인 방식으로 합집합을 만들어 내기 어렵다는 뉘앙스

>> 균형잡는 나무구조를 사용하면 효율성을 높일 수 있다고 합니다.
>> 한번 들어봅시다.

집합을 표현하는 방법 : 상향식 나무 구조

>> 하나의 나무는 하나의 집합에 대응
>> 나무의 root는 그 집합의 Representation
>> 한 나무를 표현할 때는 parent라는 배열을 사용한다.
    >> 인덱스가 i인 노드의 부모를 parent[i]에 기록

함수로 구현해보자

parent = [-1, 3, 0, 0, 0, -1, 5, 5, 6] 
FIND = 0
UNION  = 1
FLAG = FIND

def union_set(e1,e2):
    parent[e1]=e2 

def find_set(e1, e2, flag=FIND):
    ## e1, e2가 같은 집합에 속하는 지 확인해주는 함수
    ## 모드가 UNION이고 소속 집합이 다르다면 합치는 함수가 실행되도록 구현됨 
    i = e1
    j = e2
    while parent[i] >= 0 :
        i = parent[i]
    while parent[j] >= 0:
        j = parent[j]
    if flag == UNION and i != j:
        union_set(i,j)
    if i==j :
        return True
    else : 
        return False

>> 위 코드 설명

>> def find_set(e1,e2,flag)
    >> e1과 e2가 같은 집합에 속하면 True 반환, 아니면 False를 반환하는 함수
    >> flag 가 UNION, 그리고 e1,e2가 서로 다른 집합에 소속되어 있으면 두 집합을 하나로 합침

>> def union_set(e1,e2)
    >> 루트1, 루트2 모두 -1을 가리키는 것이었는데
    >> 루트1이 루트2를 가리키기 만든다. 이것으로 합치기는 끝난다!!!