📝 적어서 머릿속으로

유니온 파인드 파이썬 구현하기 / union - find by Phython 유니온 / 파인드는 현재 노드들이 같은 그룹에 속해 있는지 확인하고 같은 그룹으로 만드는 병합이 필요할 때 사용하는 알고리즘입니다. find 알고리즘 구현 par = [ -1 for i in range(N + 1) ] # 루트를 담을 배열 def find(x): # 루트를 찾아주는 함수 if par[x] 아직 연결된 적이 없음 par[x] = find(par[x]) # 자신의 부모를 부모->부모 를 재귀로 루트 부모를 찾음 return par[x] # 루트 부모를 리턴 par 이라는 배열에는 각 노드의 부모를 담아 놓습니다. par 배열의 index는 각..

순열이란, 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 >=..

🚩 플로이드 와샬 알고리즘 파이썬 구현 플로이드 와샬은 다익스트라 알고리즘과 같이 최단거리 혹은 최소비용을 구하는 알고리즘입니다. 플로이드 와샬은 다익스트라 알고리즘과는 달리 모든 노드에서 다른 모든 노드들까지의 최소 거리(혹은 최소비용)을 구하기 때문에 "어딘가를 경유한다."라는 조건이 주어질 때, 사용을 고려하기 좋은 알고리즘 입니다. 다만, 출발점(s), 도착지점(e), 경유지(p)에 모든 노드를 고려해야하므로 시간 복잡도는 O(N^3)으로 큰 편 입니다. 즉, 문제에서 주어진 노드(N)의 최댓값을 고려해 미리 계산해 사용할 가치가 있는 알고리즘인지 고려해봐야합니다. ✏️ 플로이드 와샬 알고리즘 위 그림의 경우는 출발지점이 1번 노드, 도착지점이 4번 노드인 경우 입니다. 1 -> 4로 가는게 경유..

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(Lo..

프로그래밍에 처음 흥미를 느껴본 것이 학부시절 자동화 프로그램을 경험한 후였다. 파이썬 자체가 편리한 라이브러리로 빠르고 간단한 자동화 프로그램을 만들기에 참 좋은 것 같다. 약간의 계기가 생겨서 간단하면서 재밌는 프로그램을 만들고 싶어서 "재택근무 도우미"라는 프로그램을 만들어봤다. ▶ 무슨 프로그램일까? 사실 거창한 이름에 비해서 상당히 허저..ㅂ? 간단한 프로그램이다. 특별한 기능은 없고 프로그램을 실행하면 마우스를 자동으로 움직여서 화면 꺼짐을 방지해준다. ▶ 왜 만들었을까? 별로 쓸모없어 보이는 이 프로그램을 만든 계기가 있는데 코로나로 인해서 친누나가 재택근무를 하는 시간이 상대적으로 많아졌다. 사내의 원격 프로그램을 이용하는데 이 프로그램이 일정 시간 동안 사용자 입력(키보드, 마우스 사용)..