알고리즘/알고리즘 학습 검색 결과
22 개의 검색 결과가 있습니다.
알고리즘/알고리즘 학습

[알고리즘] 플로이드 와샬 알고리즘 파이썬(Python)

츄르사려고 코딩하는 코집사입니다. 1. 플로이드 와샬 알고리즘 파이썬(Python) - 모든 노드에서 모든 노드까지 최단 경로를 계산하는 알고리즘 - 다이나믹 프로그래밍과 비슷한 알고리즘 - 시간 복잡도는 O(N^3) #경유지 for k in range(N): #출발지 if k == i continue for i in range(N): #도착지 for j in range(N): if (i==j) or (j==k): continue if adj[i][j]>adj[i][k] + adj[k][j] : adj[i][j] = adj[i][k] + adj[k][j]

2021. 5. 10.
알고리즘/알고리즘 학습

페르마 소정리 알고리즘

츄르사려고 코딩하는 코집사입니다. 1. 페르마 소정리 - a^p = a 에서 p는 소수이고, a는 정수일 때 a^p와 a는 서로 합동. - 페르마 소정리에서는 a^p-1 = 1이 된다. - 어떤 수 b * a^(p-2) = b / a와 같다.

2021. 4. 19.
알고리즘/알고리즘 학습

알고리즘에서 문제를 틀리는 이유

츄르사려고 코딩하는 코집사입니다. 1. 출력 문제 - 문제에서 제시하는 출력 기준에 맞게 값을 출력하고 있는지 확인한다. - 예를 들어, 1 2 3 으로 출력해야 하는데, 123 으로 출력하는 경우 - YES 라고 출력해야 하는데 Yes라고 출력하는 경우 등 2. 시간초과 - for문은 O(n)의 시간복잡도이다. 그래서, 반복횟수가 커질 경우 시간초과가 날 수 있다. - 그래서 자바(Java)에서는 Java String의 length()를 사용하면 시간복잡도는 O(1)이다. - 중복계산을 하는 경우 - 자바(Java)에서 String의 += 연산의 시간복잡도는 O(N+알파)이다. 알파는 추가하려는 수의 개수. - C++에서는 += 연산의 시간복잡도는 O(K), + 연산은 O(N+알파) - 자바는 Stri..

2021. 3. 30.
알고리즘/알고리즘 학습

최소 신장트리(MST, Minimum Spanning Tree) - KRUSKAL 알고리즘, PRIM 알고리즘

츄르사려고 코딩하는 코집사입니다. 1. 최소 신장트리(MST, Minimum Spanning Tree) - KRUSKAL 알고리즘 1) 그래프에서 최소 비용 문제 - 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 - 두 정점 사이의 최소 비용의 경로 찾기 2) 신장트리 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 3) 최소 신장 트리(MST, Minimum Spanning Tree) - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 2. KRUSKAL 알고리즘 - 간선을 하나씩 선택에서 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 1) 최초, 모든 간선을 가중치에 ..

2021. 3. 18.
알고리즘/알고리즘 학습

서로소 집합(Disjoint-set) - Union-Find 알고리즘

츄르사려고 코딩하는 코집사입니다. 1. 서로소 집합(Disjoint-set) - Union-Find 알고리즘 1) 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들 - 겹치지 않는 집합 2) 교집합이 없음 3) 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분 -> 대표자 - 예를 들어, A = {1,3,5}, B = {2,4,6)이 있을 때, A 집합에서는 1, B 집합에서는 2를 식별자로 둔다. 즉, 식별자는 대표자가 된다. 4) 서로소 집합을 표현하는 방법 - 연결 리스트 - 트리 5) 서로소 집합 연산 - Make-Set(x) : 다 쪼개어진 단위 집합을 만드는 연산 (최초 1번만 수행) - Find-Set(x) : x가 속한 집합을 찾는 연산 - Union(x,y) : x..

2021. 3. 18.
알고리즘/알고리즘 학습

순차탐색(Sequence Search) 알고리즘

1. 순차탐색(Sequence Search) 알고리즘 리스트 내에서 원하는 숫자 찾기 A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] x = 30 for i in range(len(A)) : if x == A[i] : print(i+1)

2020. 8. 11.