Algorithm Summary
-
알고리즘 : PriorityQueue (우선순위 큐)Algorithm Summary 2021. 3. 2. 23:39
요약 데이터를 추가한 순서대로 제거하는 Queue (큐) 와는 달리 추가한 순서는 상관없이 제거될때 가장 작은 값을 우선순위로 제거 간단히 나오는 순서를 정해준 형태 아래와 같이 queue 모듈의 PriorityQueue 클래스는 내부적으로 Heap 구조를 사용하여 복잡도는 O(logn) 구현은 아래와 같다. # queue 에서 Priority Queue 호출 from queue import PriorityQueue pq = PriorityQueue() # 숫자를 임의로 집어넣어도 작은 순서대로 호출 pq.put(2) pq.put(3) pq.put(1) # 호출시 가장 작은 값이 호출 pq.get() 특정 값을 순서대로 정렬하고 싶을때에는 튜플형식을 활용하여 사용할 수 있다. # 특정 값의 순서를 맞춰주..
-
알고리즘 : 자료구조 Stack (스택)Algorithm Summary 2021. 2. 24. 23:08
요약 LILO(LastIn Lastout) == 선입 후출 => 나중에 넣은 데이터가 먼저 나온다라고 생각 => 가방에 짐을 집어넣으면 제일 마지막에 넣은 짐이 가방을 열면 제일먼저 나오게 되는 것을 연상 - list 로 구현한 코드 # list로구현 stack = [] stack.append(1) stack.append(2) stack.append(3) print(stack) # 마지막에 넣은 데이터 호출 print(stack.pop()) # 마지막에 넣은 데이터는 위 pop() 시 호출 후 제거 stack
-
알고리즘 : 자료구조 QUEUE (큐)Algorithm Summary 2021. 2. 23. 23:33
요약 FIFO(First In, First Out) == 선입선출 => 먼저 넣은 데이터가 먼저 나온다라고 생각 => 식당에 먼저 들어간사람이 먼저 밥먹는다라고 이해 주로 운영체제 등에서 순차적인 프로세스를 구현하려고 할때 사용 코드 구현은 다양한 방법이 있는데 아래와 같다. 1. collections 이용 # 구현 방법 1 from collections import deque q = deque() q.append(1) q.append(2) q.append(3) # 데이터 호출 q.popleft() 2. queue 이용 # 구현 방법 2 import queue q = queue.Queue() q.put(1) q.put(2) q.put(3) # 데이터 크기 print(q.qsize()) # 데이터 호출 q..
-
알고리즘 : 시간 복잡도 계산 빅오 표기법(BIG-O notation)Algorithm Summary 2021. 2. 22. 20:44
요약 Big-O 표기법은 시간 복잡도(=시간 효율성) 와 공간 복잡도(=메모리 효율성) 을 나타낼 때 사용 데이터가 증가함에 따른 처리되는 시간의 증가율을 예측하기 위해 사용 => 따라서 상수 무시, 가장 큰 영향력이 있는 항만 사용 => ex) O(2n) 또는 O(n+1) 을 O(n) 으로 표시 실행시간 순서 빠른 ~ 느린 순서 => O(1) 데이터가 증가(x축)에 따라 가파르게 상승(y축)할 수록 복잡도 증가 각 Big-O 표기별 설명 - O(1) => 단순 한번 입력에 결과 도출 def f(n) : return n+1 f(5) - O(logn) => 한번 검색할때마다 절반씩 검색할께 사..