유니온 파인드 파이썬 구현하기 / union - find by Phython

유니온 / 파인드는 현재 노드들이 같은 그룹에 속해 있는지 확인하고 같은 그룹으로 만드는 병합이 필요할 때 사용하는 알고리즘입니다.

find 알고리즘 구현

par = [ -1 for i in range(N + 1) ]  # 루트를 담을 배열

def find(x):    # 루트를 찾아주는 함수
    if par[x] < 0:  # 아직 루트가 없다면
        return x    # 자기 자신이 루트  => 아직 연결된 적이 없음
    par[x] = find(par[x])   # 자신의 부모를 부모->부모 를 재귀로 루트 부모를 찾음
    return par[x]   # 루트 부모를 리턴

par 이라는 배열에는 각 노드의 부모를 담아 놓습니다.

par 배열의 index는 각 노드의 번호이고 그 값은 부모 노드를 의미합니다.

처음 모든 노드의 값을 -1(아직 부모가 정해지지 않음)으로 초기화합니다. -> 모든 노드(index)는 아직 부모 노드가 없음(-1)

find 함수는 재귀적으로 자신의 부모의 부모를 탐색합니다. 최종적으로 부모가 없는 노드(값이 -1인 노드)를 발견한다면 최상위 노드(root)로 볼 수 있습니다.

최상위 노드를 찾았다면 해당 노드의 값을 리턴하고 그 이전의 노드들은 최상위 노드의 번호로 자신의 부모 노드를 갱신하게 됩니다.

union 알고리즘 구현

def union(a, b):    # union 두 집합을 연결해주는 함수
    a, b = find(a), find(b) 
    if a == b:  # 루트 부모가 같다면 같은 집합 => 이미 연결 관계
        return False
    par[b] = a  # 부모 노드를 통일시켜 하나의 집합으로 병합
    return True

union 혹은 merge 알고리즘은 두 노드를 인자로 받아서 해당 노드들이 같은 그룹인지 확인하는 알고리즘입니다.

find 함수를 통해서 해당 노드의 부모 노드를 확인합니다.

위 함수에서는 인자로 받은 a, b변수에 부모의 노드의 값을 대입해 주었습니다. (인자로 받은 값은 지역변수 이므로 원본 a, b 가 변하지는 않습니다.)

만약 부모의 값이 같다면 같은 이미 같은 그룹이기에 'False'를 리턴하여 함수를 종료합니다.

그렇지 않다면, 다른 노드이므로 병합을 위해서 한쪽의 부모 노드를 다른 노드의 부모 노드로 갱신합니다. (어느 것이든 상관없습니다.)

갱신 후 같은 갱신을 하였다는 의미로 'True'를 리턴합니다.

union 함수의 목적은 두 부모 노드를 동일하게 만들어 하나의 그룹임을 확인할 수 있는 상태로 만드는 것에 있습니다. 따라서 return 값의 경우 필요에 따라서 수정할 수 있습니다.

순열이란, N개의 원소에서 원하는 개수를 뽑을 때, 순서까지 고려하는 것을 말합니다.

예시)

[1, 2, 3] 배열에서 2개의 원소를 선택할 경우

=> (1, 2), (1, 3), (2, 3), (2, 1), (2, 3), (3, 1), (3, 2)

위와 같은 결과처럼 (1, 2), (2, 1)의 경우는 서로 다른 것으로 판단합니다.

🥸 재귀를 통한 코드 구현

test = [1, 2, 3]
test_len = len(test)

N = 2   # 뽑을 순열의 개수
visit = [0] * test_len # 해당 index의 값을 사용했는지 여부
arr = [0] * N   # 현재 순열을 담을 배열
arr_list = []   # 모든 순열을 담을 배열

def permutaion(level):
    if level >= N:	# 레벨이 N과 같은 경우(이미 N개의 원소를 선택한 경우)
        arr_list.append(arr[:]) # 얕은 복사를 통해서 현재 순열을 추가한다.
        return
    else:
        for i in range(test_len):
            if visit[i]: continue   # 이미 순열로 선택되었다면 통과
            visit[i] = 1	# 아직 선택되지 않은 경우이므로 선택처리
            arr[level] = test[i]    # 순열을 선택
            permutaion(level + 1)   # 재귀를 통해 반복
            visit[i] = 0    # 다음 트리로 내려가기 위해서 이전의 방문처리를 롤백

permutaion(0)	# 0개의 원소를 선택한 경우부터 시작
print(arr_list)

# 실행결과
>>> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

파이썬의 경우 내장함수를 통해서 더 쉽게 구현할 수 있습니다.

🥸 파이썬 내장함수 itertools.permutation을 통한 구현

import itertools

test = [1, 2, 3]
new_per = list(itertools.permutations(test, 2))	# test 배열에서 2개의 원소를 뽑아서 수열 생성 후 리스트로 변환
print(new_per)

# 실행결과
>>> [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

🚩 플로이드 와샬 알고리즘 파이썬 구현

플로이드 와샬은 다익스트라 알고리즘과 같이 최단거리 혹은 최소비용을 구하는 알고리즘입니다.

플로이드 와샬은 다익스트라 알고리즘과는 달리 모든 노드에서 다른 모든 노드들까지의 최소 거리(혹은 최소비용)을 구하기 때문에 "어딘가를 경유한다."라는 조건이 주어질 때, 사용을 고려하기 좋은 알고리즘 입니다.

다만, 출발점(s), 도착지점(e), 경유지(p)에 모든 노드를 고려해야하므로 시간 복잡도는 O(N^3)으로 큰 편 입니다.

즉, 문제에서 주어진 노드(N)의 최댓값을 고려해 미리 계산해 사용할 가치가 있는 알고리즘인지 고려해봐야합니다.

✏️ 플로이드 와샬 알고리즘

위 그림의 경우는 출발지점이 1번 노드, 도착지점이 4번 노드인 경우 입니다.

1 -> 4로 가는게 경유지 없이 간다면 비용은 4가 들게됩니다.

만약 경유지를 선택하게 될 때, 2번을 경유지로 선택한다면 총 비용은 3(2 + 1)이고 3을 경유지로 선택한다면 비용은 2(1 + 1)이 됩니다.

따라서 위 그림의 최소 비용(혹은 최단 거리)는 1 -> 3 -> 4를 선택한 2가 됩니다.

이제부터 1 -> 4로 이동할 때 발생하는 최소비용은 2라는 것을 알 수 있습니다.

플로이드 와샬은 이처럼 모든 노드를 방문해서 다른 노드까지의 최소비용을 계속 갱신해주면서 모든 노드에서 모든 노드까지(몇 번을 경우하는지 상관없이) 최소 비용을 알아낼 수 있습니다.

✏️ 플로이드 와샬 알고리즘 코드(파이썬)

cost = [[INF] * n for _ in range(n)]    # INF로 구성된 n x n 행렬, 노드끼리의 최소 비용을 담을 배열

for i in range(n):  # 자기자신 -> 자기자신의 비용은 0이므로 초기화 해준다.
	cost[i][i] = 0

# 플로이드 와샬
    for k in range(n):  # 경유지
        for j in range(n):  # 도착지
            for i in range(n):  # 출발지
                # 현재 i -> j까지드는 비용이 i -> k -> j의 비용보다 비싸다면 더 저렴한 비용으로 갱신
                if cost[i][j] > cost[i][k] + cost[k][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

여기서 INF는 중간 값으로 주어진 나올 수 있는 값보다 큰 값으로 세팅합니다.

cost 배열은 출발지점 -> 도착지점 까지의 비용을 담아 놓을 2차원 배열 입니다.

출발점, 도착점, 경유지를 모두 탐색하는 3차원 for문을 돌면서 현재의 비용(i -> j)보다 k를 경우하는 (i -> k -> j) 비용이 더 저렴하다면 갱신해 주면 플로이드 와샬 구현이 완료 됩니다.

이때, 경유지를 기준으로 모든 경우(출발, 도착)을 확이해야하므로 최상단 for문에는 경유지(k)가 와야합니다.

그렇지 않을 경우, 모든 경우에서 제대로 갱신되지 않을 수 있습니다.

✏️ 플로이드 와샬 알고리즘 문제 풀어보기(2021년 카카오 신입 채용 코딩 테스트)

https://programmers.co.kr/learn/courses/30/lessons/72413

플로이드 와샬 알고리즘을 구현해야하는 문제인 2021년 카카오 신입 채용 코딩테스트 문제를 가져왔습니다.

📝 전체 코드

# 합승 택시
# 플로이드 마샬
def solution(n, s, a, b, fares):
    INF = 200 * 100000 + 1  # 최대 비용
    cost = [[INF] * n for _ in range(n)]    # INF로 구성된 n x n 행렬, 노드끼리의 최소 비용을 담을 배열

    for i in range(n):  # 자기자신 -> 자기자신의 비용은 0이므로 초기화 해준다.
        cost[i][i] = 0

    for f in fares:
        start_node = f[0] - 1   # 노드의 번호가 1부터 주어지므로 index를 맞추기 위해서 1을 빼준다.
        end_node = f[1] - 1
        price = f[2]
        # 입력으로 주어진 출발점 <-> 도착점의 비용들을 대입해준다.
        cost[start_node][end_node] = price
        cost[end_node][start_node] = price

    # 플로이드 와샬
    for k in range(n):  # 경유지
        for i in range(n):  # 출발점
            for j in range(n):  # 도착점
                # 현재 i -> j까지드는 비용이 i -> k -> j의 비용보다 비싸다면 더 저렴한 비용으로 갱신
                if cost[i][j] > cost[i][k] + cost[k][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

    answer = INF
    # 모든 경유지를 탐색하며 최소 요금을 갱신
    for k in range(n):
        answer = min(answer, cost[s - 1][k] + cost[k][a - 1] + cost[k][b - 1])

    return answer

GCD(Greatest Common Divisor) 최대 공약수 구하기

유클리드 호제법 사용

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

a = b x q + r 이라고 했을 때, GCD(a, b) = GCD(b, r)를 만족한다.

간단 증명:

수학적으로 증명하는 방법이 있지만 이해를 위해서 간단히 설명하자면 아래와 같이 표현할 수 있다.

b = r x m + n으로 표현할 때, n이 0이라면 b = rm으로 표현된다. 즉, b와 r의 최대 공약수 GCD(b, r) = m이 된다.

a = bq + r = rmq + r = r(mq + 1) 이므로 GCD(a, b) = r 이다.

=> GCD(a, b) = GCD(b, r) = GCD(r, 0) = r

LCM(Lowest Common Multiple) 최대 공약수 구하기

def lcm(a, b):
    return a // gcd(a, b) * b

a와 b의 최대 공약수 GCD(a, b) = m이라고 했을 때,

a = Am, b = Bm으로 표현 할 수 있다.

이때, 최대 공약수(M) = ABm 이다.

따라서 a % m * b = Am % m * Bm = ABm이 된다.

프로그래밍에 처음 흥미를 느껴본 것이 학부시절 자동화 프로그램을 경험한 후였다.

파이썬 자체가 편리한 라이브러리로 빠르고 간단한 자동화 프로그램을 만들기에 참 좋은 것 같다.

약간의 계기가 생겨서 간단하면서 재밌는 프로그램을 만들고 싶어서 "재택근무 도우미"라는 프로그램을 만들어봤다.

▶ 무슨 프로그램일까?

사실 거창한 이름에 비해서 상당히 허저..ㅂ? 간단한 프로그램이다.

특별한 기능은 없고 프로그램을 실행하면 마우스를 자동으로 움직여서 화면 꺼짐을 방지해준다.

▶ 왜 만들었을까?

별로 쓸모없어 보이는 이 프로그램을 만든 계기가 있는데 코로나로 인해서 친누나가 재택근무를 하는 시간이 상대적으로 많아졌다.

사내의 원격 프로그램을 이용하는데 이 프로그램이 일정 시간 동안 사용자 입력(키보드, 마우스 사용)이 없으면 자동으로 프로그램을 종료해버린다고 한다. 이 시간 간격이 매우 짧다고 한다.

업무 특성상 클라이언트와의 통화나 서적을 찾아봐야 하는 일이 많은데 자꾸만 마우스를 한 번씩 흔들어줘야 해서 불편하다는 것이다. 주변 동료들도 불편해 한다고..

얘기를 듣고 "그냥 마우스가 자동으로 움직이면 되는 거네? 만들 수 있겠는데"라는 생각으로 바로 작업에 들어갔다.

구글에 치면 필요한 라이브러리는 다나와..

▶ 어떻게 만들었을까?

일단 간략히 사용자 입장에서 요구사항을 만들어보고 나름대로 설계 로직을 짜 봤다..

- 요구사항

1. 실행파일로 실행한다.

2. 키보드나 마우스로 간단히 실행한다.

3. 언제든지 종료가 가능해야 한다.

- 설계

1. 사용성을 위해 ktinter 라이브러리를 이용한  UI를 만든다.

2. 매크로 기능으로 pyautogui 라이브리를 이용한다.

3. 최대한 심플하게 만든다.

   - 상단에 실행 방법 text

   - 하단에 종료 방법 text

   - 중간에 "실행 버튼" / "종료 버튼 "생성, 키보드로 실행과 종료 가능한 trigger를 만든다.

짠 완성!

보이는 것처럼 기능은 실행 버튼을 클릭하거나 키보드 F9번을 누르면 작동된다.

종료 버튼도 마찬가지로 종료 버튼을 누르거나 키보드 ESC를 누르면 종료한다. 사실 종료 버튼은 마우스가 계속 움직여서 ESC 키로만 끄게 된다... 

▶ 제작 과정에서의 문제점

워낙 간단한 프로그램이다 보니 큰 문제는 없었는데 여기서도 문제가 생기긴 했다.

마우스 움직임 자체가 상대적인 위치에서 계속 움직이는데 이를 while문으로 짜 놨다.

중간에 종료 키보드 입력 값 'ESC'가 들어오면 멈추게 해 놨는데 이게 잘 먹히질 않았다.

정확히는 종료 기능 자체가 불가능하다기보다는 반응하기까지 시간이 걸렸다.

마우스가 움직이는 동작을 하는 동안 종료 버튼을 3초 이상 꾸욱 누르고 있어야 반응을 했다.

처음 로직은 이러했다. 마우스는 처음 위치에 마지막 위치까지 움직이라는 명령을 받은 후 그 사이에 종료 버튼이 들어오면 루프를 탈출하게 해 놨다.

종료 버튼은 작동은 하지만, 꾹 누르고 있어야지만 작동하는 것으로 봐서는 마우스가 움직이는 동작이 너무 빨라서 trigger가 반응하지 못하는 이유라고 생각했다.

▶ 문제 해결 과정

어떻게 해결할까 생각을 했는데 예전에 html을 이용해서 벽돌깨기 게임을 만들었던 게 생각이 났다.

MDN 사이트에 예제로 있던 프로그램이었는데 하단 패드를 방향키로 조정해 공을 튕겨 벽돌을 깨는 게임이다.

웹 화면을 계속해서 업데이트해주는데 이때, 하단 패들이 속도를 가지고 키보드 방향의 입력이 들어오는 동안 x 방향의 속도만큼 움직이는 소스이다. (방향키 입력이 꺼지는 순간 속도 0)

이와 같은 방법으로 마우스의 움직임을 실행(F9) 이벤트가 들어오면 x방향 속도만큼 이동하고 종료(ESC)가 들어오면 속도가 0이 되게 했다.

정확히는

백돌깨기의 방향키 입력(누름) -> 제작 프로그램의 실행(F9) 버튼

벽돌깨기의 방향키 입력 종료(뗌) -> 루프 탈출

로 구성했다.

속도 개념을 가져와서 중간중간 계속해서 종료 입력을 확인해 언제든지 종료할 수 있게 한 것이다.

수정 후에는 처음 계획했던 대로 정상적으로 기능을 수행하기 시작했다.

▶ 생각해봐야 할 것

1. CPU 점유율

작은 프로그램이지만 리팩터링 후에 마우스가 짧은 거리를 연속해서 이동하고 그 사이사이 사용자에게 "종료"를 확인하게 되는데 이게 컴퓨터 과부하를 일으키지 않을까 확인해봐야 했다.

프로그램이 워낙 작아서 그런지 다행히 CPU 사용률이나 메모리 점유율에 차이는 없었다. 오히려 더 작아보이는 것은 실시간으로 점유율이 바뀌기 때문인다.

확인할 수는 없지만, 나중에 확장된 프로그램을 제작할 때는 전혀 다른 결과가 나올 수 있으니 조금 더 효율적인 코드를 생각해봐야겠다.

2. while문

사실 꼭 while문을 사용해야 했을까 의문이 들긴 한다. 하지만, 아직 내 지식으로는 while문 없이 반복적인 루프를 만들 수 있는 방법이 떠오르지는 않는다.

계속 기억해놨다가 새로운 지식을 계속 적용해봐야 할 것 같다.

▶ 배포 및 후기

간편한 사용을 위해서  단일 exe 파일로 빌드했다. 처음에는 좀 더 작고 빠르게 만들고자 분할 파일로 빌드했는데 다른 컴퓨터로 실행하면 잘 작동하지 않는 오류가 있었다.

파일이 나눠져 제대로 받지 못했거나 잘못 빌드해서 파이썬이 깔려있지 않으면 실행되지 않는 이유일 텐데 후자일 가능성이 높다고 생각했다.

원 파일로 빌드해서 배포하니 윈도즈를 사용하는 컴퓨에서는 모두 정상 작동한다. 맥에서는 확인하지 않았는데 이론상으로는 빌드 방식만 바꾸면 되는 일이니 기회가 되면 시도해봐야겠다.

일단 누나는 잘 사용하고 있고 회사 동료 몇 분들에게도 공유해서 너무 잘 사용하고 있다는 후기를 남겨주셨다...

이렇게 농땡2가 아닌 재택근무의 효율성을 높이는 프로그램을 만들어봤었다.

거창하지 않아도 이런 작은 프로젝트를 진행하는 게 상당히 재미있다. 의외로 은근히 생각할게 많이 생긴다...

아주 많이 부족한 프로그램이지만 삶의 질을 1g이라도 향상 시킬 수 있는 프로그램을 내가 직접 만들 수 있다는게 프로그래밍의 가장 큰 매력이 아닐까싶다. 개발자가 되기로 마음먹은 이후 가장 뿌듯했던 경험이 되지 않을까 싶다.

또 주변에 재밌는 문젯거리 없나 찾으러 다녀야겠다.