shine_hyun shine_hyun

스택(Stack) 큐(Queue) 튜플(Tuple) 집합(Set) 사전(dictionary) Collection 모듈 스택(Stack) -Last In Last Out 의 메모리 구조 -주로 리스트를 이용해서 스택을 구현함. a=[1,2,3,4,5] a.append(6) #stack에 push a.append(7) a.pop() #stack에서 pop 큐(Queue) - FIFO(First In First Out) 의 구조 - 리스트 또는 collection deque 모듈을 사용하여 구현 a=[1,2,3,4,5] a.append(6) #push a.pop(0) #제일 처음인 원소를 반환 from collections import deque a=deque() a.append(1) a.append(2) a..

Trie 구조 문자열을 쉽게 탐색하기 위한 tree형태의 구조 예를들어, 문자열 [Joe,John,Johnny,Jane,Jack]로 트라이 구조를 만들었을때이다. 이 트라이 구조는 최대 장점은 '검색'에 있다. [Joe,John,Johnny,Jane,Jack] 에서 'Joe'의 유무를 찾으려면 단순하게는 문자열 전체를 search해야한다. 찾으려는 문자 길이를 m, 문자열 길이를 n이라하자. 각 문자열에 character를 J,o,e와 하나씩 비교해야하고, 이것을 n번 반복하니 총 O(nm)의 복잡도가 발생한다. 반면 trie구조를 사용하면, 문자 길이 m인 O(m) 의 복잡도면 충분하다. Trie 구조는 내가 생각하기엔, 딱히 tree구조와 다른것은 없어보인다. 다만, 문자가 끝나는 것을 알려줘야하기 ..

문득 내가 즐겨쓰는 라이브러리들이 몇개 있는데, 걔네를 쓰지 말라하면, 어떻게 하나.. 고민하다 후다닥 구현 정리중.. min/max heap은 알고리즘에서는 '우선순위 큐'로 더 많이 이용되고 있다. 간단히 소개하자면, min heap이라면, 2진 트리 형태로, 무조건 parent노드가 child노드보다 더 작아야한다. 그래서, 최상의 root노드는 항상 최소의 값이 위치한다. 파이썬에서는 heapq로 사용하는데, life-of-h2i.tistory.com/17 [Python]Minheap 최소 경로를 구할때 많이 쓰이는Priority queue(Minheap) 정리 정렬된 상태로 원소 삽입, 삭제되는 자료구조 * Priority queue 구현 방법이 다양함 - Naiive 하게 배열로 정렬 - Li..