STUDY BITS STUDY BITS

컴퓨터/파이썬

• 파이썬 A* (A-star) 최단 경로 찾기 알고리즘

  컴퓨터/파이썬 2020. 7. 20. 16:02

  A* 길 찾기 알고리즘은 1968년에 Peter Hart, Nils Nilsson, Bertram Raphael에 의해 최초 공개됐다.우선 Node 클래스는 아래와 같이 구현될 것이며, 아래 클래스를 보고 글을 읽으면 좀 더 편할 것이다.class Node: def __init__(self, parent=None, position=None): self.parent = parent # 이전 노드 self.position = position # 현재 위치 self.f = 0 self.g = 0 self.h = 0ex) 노드의 현재 위치는 xy좌표계를 사용한다.start = (0, 0), end = (9,9)aSta..

  Read More
• 파이썬 Introspective Sort (내성 정렬) 알고리즘

  컴퓨터/파이썬 2020. 7. 17. 15:31

  Introspective Sort IntroSort (Introspective Sort) 인트로 정렬은, Quick Sort의 장점을 유지하면서, 최악 시나리오 O(n^2)를 해결하려 만들어진 (Quick Sort + Heap Sort + Insertion Sort) 하이브리드 알고리즘이다. (C++ 기본 정렬 알고리즘, std::sort) 모든 상황에서 시간 복잡도 : O(nlogn), 공간 복잡도는 O(logn)이며, inplace, not stable한 알고리즘이다. (in-place란, 보조 데이터 구조를 사용하지 않고, 작동하는 알고리즘) Quick Sort로 시작해서, Recursion max-depth (log(len(array)) 에 도달하면 Heap Sort로 정렬하고, 그리고, 파티션 ..

  Read More
• 파이썬 array.sort(), TimSort 알고리즘

  컴퓨터/파이썬 2020. 7. 16. 21:34

  Tim Sort 소개 (Insert + Merge) TimSort 는 파이썬, 자바, Swift, Rust stable에서 기본으로 탑재된 sort() 함수의 알고리즘이다. 최고 O(n) 시간 복잡도를 갖고, stable 하며, 다양한 데이터에 적합한 정렬 알고리즘이다. (시간 복잡도 : 최상(n), 평균(nlogn), 최악(nlogn), 공간 복잡도 : n) (이 글에서 구현된 timSort는 계산해보면 모든 케이스에서 nlogn이 나온다) (정렬 알고리즘에서 안정성(stability)란 값이 원래 순서(order)를 갖고 정렬을 할 수 있냐, 없냐이다.) TimSort 는 두 가지 정렬 알고리즘을 섞은 것인데, 바로 Insertion과 Merge이다. (Quick Sort는 unstable, Merg..

  Read More
• Python BFS(너비 탐색) 및 Iterative Deepening Depth-first Search

  컴퓨터/파이썬 2020. 7. 11. 20:50

  IDDFS 1. 소개 반복적 깊이 증가 (IDDFS)는 깊이 우선 탐색(DFS)처럼 메모리 필요량이 깊이 제한에 비례하면서도 최단 경로로 목표 노드를 찾는 것을 보장하는 방법이다. IDDFS 방법에서는 목표 노드가 찾아질 때까지 깊이 제한을 1 씩 증가시키면서 연속적인 깊이 우선 탐색을 수행한다. 아래 그래프를 반복적 깊이 증가 탐색을 해보면 다음과 같다. 깊이 제한 1 = A -> B -> C -> D 깊이 제한 2 = A -> B -> E -> F -> C -> D -> G -> H 깊이 제한 3 = A -> B -> E-> F -> I -> J -> C -> D -> G -> H -> K ... 2. Node class 우선 Node 클래스를 만들어 준다. class Node: def __init_..

  Read More
• Python Count Sort 카운트 정렬 알고리즘

  컴퓨터/파이썬 2020. 6. 28. 21:47

  Count Sort 말 그대로 통 안에 모든 값들을 넣어 카운트(+1) 한 다음에, bucket[최소 값 ~ 최대 값], 카운트된 만큼 계속 arr[index] 에 지정하는 방식 # Time Complexity : O(n) | Space Complexity : O(n) | stable def countSort(arr): """ Args: arr (list): Array to sort Returns: arr (list): Sorted input array """ minValue = min(arr) maxValue = max(arr) - minValue # 음수 케이스 처리 buckets = [0 for x in range(maxValue + 1)] for i in arr: buckets[i - minVal..

  Read More
• Python BST 바이너리 서치 트리 Traversal + Height

  컴퓨터/파이썬 2020. 6. 27. 12:50

  class BST: def __init__(self, value): self.value = value self.left = None self.right = None def traverse(tree, arr=[]): if tree is not None: #inOrder arr.append(tree.value) traverse(tree.left, arr) #preOrder arr.append(tree.value) traverse(tree.right, arr) #postOrder arr.append(tree.value) return arr EX) 아래 그래프는 # 그래프 생성 root = BST(10) root.left = BST(5) root.left.left = BST(2) root.left.left.le..

  Read More
• Python %, modulo operator 나머지 연산자 음수

  컴퓨터/파이썬 2020. 6. 24. 15:49

  C 에서 -1 % 10을 하면, $-1$이 나온다. #include int main() { int a = -1 % 10; printf("%d", a); } Python 에서는 $9$라는 결과가 나온다. print(-1 % 10) C 가 옳은지 Python 이 옳은지 문제가 아니라, 작동 방식이 다르다고 한다. (파이썬에서 사용되는 modulo 연산자가 수 이론에서 더 많이 사용된다고 한다.) C는 아래와 같이 작동하고, 1. A / B = A/B -> floor(A/B) = C (ex -> -1 / 10 = -0.1 => floor(-0.1) = -1) 2. A % B = (C * B - (C*B - A)) % B (ex -> -1 % 10 = (-1 * 10 + 9) % 10 = -1) 파이썬에서는 쉽..

  Read More
• Sublime Text 3 nose2 테스트 사용하기

  컴퓨터/파이썬 2020. 6. 21. 21:21

  결과물 pip install nose2 https://docs.nose2.io/en/latest/ Welcome to nose2 — nose2 0.6.0 documentation nose2 is the successor to nose. It’s unittest with plugins. nose2 is a new project and does not support all of the features of nose. See differences for a thorough rundown. nose2’s purpose is to extend unittest to make testing nicer and easier to under docs.nose2.io https://github.com/aprudent/Nos..

  Read More