파이썬 크롤링과 시각화 기본다지기(6)_알고리즘,자료구조 기초

 

이번 장에서는 알고리즘과 자료구조를 공부할 것이다.

-알고리즘(algorithm)
   문제 해결을 위한 일련의 과정
-자료구조(data structure)
    데이터와 그들의 관계를 조직화,구조화 한것 
    데이터를 효율적으로 조직,저장하는 방법
     (데이터를 어떻게 저장 혹은 어떻게 꺼내올까)

-단순형태 -변수(정수,실수.문자열)
-선형형태 -리스트,스택,큐
-비선형형태 -트리

-자료구조에 대한 적절한 지식이 있다면 보다 효율적인 알고리즘을 구현할 수 있다.(상호보안관계)

---

효율적인 알고리즘?
  1.실행시간이 짧다(시간복잡도가 적다)
  2.컴퓨터 메모리를 덜 사용한다(공간 복잡도 작다)
 

복잡도(complexity)
 알고리즘의 성능을 객관적으로 평가하는 기준

 시간복잡도 
    실행에 필요한 시간을 평가 
  공간복잡도
     실행에 필요한 공간을 평가

빅오표기법(Big-O)

   최악의 경우를 판단하여(가정하여) 시간복잡도를 계산하는 방법

 

알고리즘 내부에 사용된 연산자나 함수가 실행되는 시간도 고려하면 좋다.

---

선형탐색(linear search)
  앞에서부터 순서대로 찾는 방식 O(n)
이진탐색(binary search)
  로그실행시간을 보장한다 O(logn)
  단, 반드시key가 정렬되어있어야함.

#탐색알고리즘 구현
from time import time
 
 li=[i for i in range(10000000)]
 
 def ser(li, n):
	cnt=0
    for i in li:
    	cnt+=1
        if i ==n:
			print('찾음, 반복횟수: ',cnt)
     print('없음')
     
 #해당 구현에서는 이진탐색이 제일 효과적이다. 
 def binary_ser(li,key):
	cnt=0
    left=0
    right=len(li)-1
    while left<=right:
		cnt+=1
        mid = (left+right)//2
        if li[mid] == key:
         	print('찾기성공,  반복횟수: ',cnt)
            return
        elif li[mid] >key:
        	right = mid-1
        elif: left=mid+1
    print('실패')
    
    
def ser2(li,key):
	if key in li:
		print('찾음')
        return
    print('실패')
    
    
    
 ser(li,8100)
 binary_ser(li,8100)
 ser2(li,8100)​

#1~n까지의 총합을 구하는 함수

#시간복잡도O(n)
def sum(n):
	sum=0
    for i in range(1,n+1):
    	sum+=1
    return sum
    
#O(1)
def sum2(n):
	return int((1+n)*n/2)
    
import time
n=1000000

start = time.time()
print('-----sum()------')
print(n,'까지의 총합은',sum(n))
end=time.time()
print('실행시간: ',end-start)
start = time.time()
start = time.time()
print('-----sum2()-----')
print('1부터',n,'까지의 총합은',sum2(n))
end=time.time()
print('실행시간: ',end-start)

---

추상자료형(Abstract Data Type)
  isFull()    스택이 차있다면 True 아니면 False
  isEmpty()    스택이 비어있다면 True  아니면 False
  push()     데이터 삽입(맨마지막에 이어서 추가된다)
  pop()    데이터 삭제(위에서부터 차례로)
  peek()    가장 위에 있는 요소 엿보기
  clear()    모든 요소삭제

• 스택 자료구조(선입후출)

def isFull(stk, size):
  if len(stk) == size:
    return True
  return False

def isEmpty(stk):
  if len(stk) == 0:
    return True
  return False

def push(stk, element, size):
  if isFull(stk, size) == False:
    stk.append(element)

def pop(stk):
  if not isEmpty(stk):
    return stk.pop()

def peek(stk):
  if not isEmpty(stk):
    return stk[-1]

def clear(stk):
  for i in range(len(stk)):
    pop(stk)
    


# 스택자료구조 데이터를 저장할 list
stk = []
# 스택의 사이즈
size = 10
push(stk, 10, size)
push(stk, 20, size)
push(stk, 30, size)
push(stk, 40, size)
push(stk, 50, size)
print(stk)
print(pop(stk))
print(stk)
print(peek(stk))
print(stk)

결과>>

[10, 20, 30, 40, 50]

50

[10, 20, 30, 40]

40

[10, 20, 30, 40]

None

 

• 클래스로 구현한 스택

 

class Stack():
  def __init__(self,size):  #생성자에 리스트를 만들어준다.
    self.stk=[] 
    self.size=size         #self가 이미 size를 인스턴스 변수로 가지고 있으므로 밑의 함수에서 따로 호출 필요 없다.

  def isEmpty(self):
    # if len(self.stk) == 0:
    #   return True
    return len(self.stk) == 0
    
  def isFull(self):
    if len(self.stk) == self.size:
      return True
    
  def push(self):
    if len(self.stk) != True:
      return stk.push()
  def pop(self):
    if len(self.stk) != True:
      return stk.pop()
  def peek(self):
    return stk.peek()

self는 인스턴스 자신, 메소드의 임의의 인수
__init__는 self와 나란히 클래스 내에 등장한다. 반드시 첫번째 인수로 self를 지정해야한다. self에는 인스턴스 자체가 전달된다. 이로인해 다른 메소드 내에 인스턴스 변수를 작성하거나 참고하는 것이 가능하다. __init__메소드 이후 다음 메소드에 초기화 코드를 위와 같이 작성하면된다.