본문 바로가기

파이썬

(5)

[Algorithm] Union - Find (Python 구현) 유니온 파인드 파이썬 구현하기 / 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는 각..

[Algorithm] 재귀를 통한 순열(permutation) 구현(+ python 내장 함수 이용) 순열이란, 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 >=..

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

[Algoritm] 행렬 회전 (Python 구현) 프로그래머스에서 제공하는 카카오 2020년 신입 개발자 블라인드 코딩 테스트 1차 문제 3번을 풀어 보았다. https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 해당 문제는 어떤 알고리즘을 사용할 것인가를 알아내는 것보다 구현력이 필요한 문제였다고 생각한다. 해당 문제의 경우 제한 사항의 크기가 작기 때문에 모든 경우를 확인하는 완전 탐색으로 풀이가 가능한데, 행렬의 회전과 범위를 설정하는 것이 중요했다. 문제를 해결하기 위해서는 2차원 행렬의 회전을 구현해야 ..

[Algorithm] 최대 공약수, 최소 공배수 구하기 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..

이전 1 다음

728x90

티스토리툴바