CS/알고리즘_개념 15

기본 정수론

정수론(Number theory) 정수의 성질을 연구하는 분야 정수(Integer) -90 -3 0 1 5 8 10 14 15 19 약수(Divisor) 특정 정수를 나누어 떨어지게 하는 수 20의 약수 -> 1, 2, 4, 5, 10, 20 #구현 1 2 3 4 5 6 7 8 9 10 11 12 import sys if __name__ == "__main__": input = sys.stdin.readline n = int(input()) for i in range(1, n+1): # 숫자 i가 n의 약수인지 판단 if n%i == 0: print(i, end=' ') cs 소수(Prime number) 약수가 1과 자기 자신뿐인 정수 7의 소수 -> 1, 7 #구현 1 2 3 4 5 6 7 8 9 1..

SCC-코사라주 알고리즘(Kosaraju's Algorithm)

방향 그래프(Directed Graph) 에서 SCC (Strongly Connected Component) 를 코사라주 알고리즘을 이용해 구하는 방법이다. ① 주어지는 방향 그래프있다. ② 주어지는 방향 그래프와 역방향을 가지는 역방향 그래프를 만든다. ③ 정점을 담을 스택을 만든다. 코사라주는 위상정렬을 이용하고, 방향그래프와 역방향그래프가 동일한 SCC를 구성하는 것을 이용한다. ①-③ 까지 방향그래프, 역방향그래프, 스택을 준비한다. 순서는 아래와 같다. ①② ③ 1) ①방향그래프에 임의의 정점부터 DFS를 수행한다. DFS가 끝나는 순서대로 ③스택에 삽입한다. 1-1) DFS를 수행한 후 아직 방문하지 않은 정점이 있는 경우, 해당 정점부터 다시 DFS를 수행한다. 1-2) 모든 정점을 방문하여..

최소신장트리(Spanning Tree) : 크루스칼 알고리즘

최소 신장 트리의 이해 1. 신장 트리 란? Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) 2. 최소 신장 트리 Minimum Spanning Tree, MST 라고 불리움 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 3. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루..

최단경로알고리즘-[다익스트라-Dijkstra's Algorithm)

- 하나의 정점에서 모든 정점까지 최단 거리를 구하는 알고리즘(간선의 가중치가 양수일 때만) https://people.ok.ubc.ca/ylucet/DS/Dijkstra.html Dijkstra Visualization people.ok.ubc.ca a와 b 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다. 탐색 알고리즘 그래프 시간복잡도 O(|E|+|V|log|V|)} 출처 : 위키백과 #코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..

그래프 깊이우선탐색(DFS), 너비우선탐색(BFS)

# 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 import sys # 그래프 # 1 ----- 2 ----- 6 # \ / \ / # \ / 4 - 5 # \ / / \ # 3 - 7 - 8 - 9 # 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> 6 -> 8 -> 9 # 9 12 (노드갯수, 간선정보) # 1 2 # 1 3 # 2 3 # 2 4 # 2 6 # 3 7 # 4 5 # 4 7 # 4 8 # 5 6 #..

그래프 개념

# 인접 행렬 구하기 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import sys # 5 6 (정점의 갯수, 간선의 갯수) # 1 2 (간선의 정보) # 1 3 # 1 4 # 2 4 # 4 5 # 3 5 # Q1. 정점 X와 Y가 연결이 되어 있는가? (Yes or No) # Q2. 정점 X와 연결이 되어 있는 모든 정점을 출력하시오. # myGraph에서 x와 y가 연결이 되어 있으면 True 아니면 False를 반환 def isConnected(myGraph, x, y): if myGraph[x][..

연속부분최대의합을 통한 문제풀이 접근법

문제 N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력 첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력 연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력 8 2 3 -5 8 -3 4 2 -9 예제 출력 11 예제 입력 5 -1 -2 3 -2 4 예제 출력 5 문제해결의 절차 1. 문제를 정확히 이해한다. 2. 문제를 해결하는 알고리즘을 개발한다.(설계) 3. 알고리즘이 문제를 해결한다는 것을 수학적으로 증명한다. 4. 알고리즘이 제한 시간내에 동작한다는 것을 보인다.(시간복잡도) ..

이진탐색(Binary Search), 순차탐색(Sequential Search) + Parametric Search

*이진탐색(Binary Search) 분할정복과 이진탐색 분할정복 알고리즘(Divide and Conquer) 문제를 하나 또는 둘 이상으로 나눈다. (Divide) 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.(conquer) 이진탐색 리스트를 두 개의 서브리스트로 나눈다. (Divide) (1) 검색할 숫자(search) > 중간 값 => 뒷 부분의 서브리스트에서 검색할 숫자를 찾는다. (2) 검색할 숫자(search) 앞 부분의 서브리스트에서 검색할 숫자를 찾는다. #코드1 : 재귀호출 사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import ..

병합정렬(merge sort)

- 재귀용법을 활용한 정렬 알고리즘 1) 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2) 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다. 3) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. ================================= index : 0 1 2 3 4 5 6 7 value : 49 97 53 5 33 65 62 51 ================================= pivot선택 : (index : 0, value : 49) p1 (1회) [left] - (index : 0, value : 49), (index : 1, value : 97), (index : 2, value : 53), (index : 3, value : ..

반응형