이진탐색, 재귀, 복잡도계산

 

 

 

In [35]:

#1강 왜 자료구조가 필요한가?
import time

while True:
    n=int(input("Number of elements: "))
    haystack=[k for k in range(n)]
    if n==-1:
        break
    print("______________")

    ts=time.time()
    maximum=max(haystack)
    elapsed=time.time()-ts
    print(f"최대값 ={maximum}, 소요시간 ={elapsed}")

 

 

Number of elements: 1000
______________
최대값 =999, 소요시간 =0.0
Number of elements: 10000
______________
최대값 =9999, 소요시간 =0.0
Number of elements: 100000
______________
최대값 =99999, 소요시간 =0.0010006427764892578
Number of elements: -1

 

In [ ]:

'''해석 : 개수에 비례해 시간이 늘어나는걸 볼수 있다.

만약 단순 리스트 탐색이 아닌 다른 효율적인 것을 이용한다면?
문제의 상황에 맞는 적절한 자료구조를 선택하면 실행시간 단축

알고리즘 설계 : 어떤 자료구조, 어떤 연산을 선택할지 결정'''

 

In [ ]:

#2강 선형배열
'''배열: 원소들을 (어떤)순서대로 늘어놓은 것(인덱스는 0부터)
(1)원소 덧붙이기
    l.append(‘NEW’)

(2)끝에서 하나 빼기
    l.pop() : 리스트에서 NEW 빠지고, NEW 리턴 
    -> 둘다 리스트 길이에 무관하게 바로 할수있음 , O(1) : 빅오 상수시간

(3)리스트 중간에 넣기
    l.insert(3,65) : 3번 인덱스에 65 넣기 ,오른쪽 숫자들 한칸씩 밀음
    -> 추가 시간: 한칸씩 미는 시간

(4)리스트 중간에 삭제
    del(L[2]) : 인덱스 2번 삭제,오른쪽 숫자들 한칸씩 당기기
    -> 추가 시간: 한칸씩 딩기는 시간

해석 : 리스트의 길이가 길면 원소 삽입, 삭제는 길이에 비례해 시간이 (선형)
증가하게됨 O(n) '''

 

In [ ]:

2강 실습: (2) 리스트에서 원소 찾아내기
def solution(L, x):
    answer = []
    tem=0
    start=0
    while len(L)>start:
        try:
            #인덱스 메서드에서 시작지점도 넣어줄수 있음
            tem=L.index(x,start)
        except:
            break
        answer.append(tem)
        start=tem+1
    if len(answer)==0:
        answer.append(-1)
    return answer

 

In [3]:

#3강 정렬(sort), 탐색(search)
l=[3,8,2,7,6,10,9]
l2=sorted(l)
l2

 

Out[3]:

[2, 3, 6, 7, 8, 9, 10]

 

In [4]:

l
#l의 순서는 바뀌지 않음 

 

Out[4]:

[3, 8, 2, 7, 6, 10, 9]

 

In [5]:

l.sort()
l
#l의 순서가 바뀜 

 

Out[5]:

[2, 3, 6, 7, 8, 9, 10]

 

In [6]:

#정렬의 순서 반대 reverse=True
l2=sorted(l,reverse=True)
l2

 

Out[6]:

[10, 9, 8, 7, 6, 3, 2]

 

In [7]:

l.sort(reverse=True)
l

 

Out[7]:

[10, 9, 8, 7, 6, 3, 2]

 

In [8]:

#문자열 리스트의 정렬 :알파벳 순서를 따름, 대문자가 소문자보다 우선

#문자열 길이로 정렬하려면?
l=['abcd','xyz','spam']
sorted(l,key=lambda x:len(x))

 

Out[8]:

['xyz', 'abcd', 'spam']

 

In [9]:

l=['spam','xyz','abcd']
#key : 정렬에 기준이 되는 키
sorted(l,key=lambda x:len(x))
#처음부터 순서가 다르면 같은 길이 글자 순서는 달라질수 있음

 

Out[9]:

['xyz', 'spam', 'abcd']

 

In [12]:

l=[{'name':'john','score':83},{'name':'paul','score':92}]
l.sort(key=lambda x:x['score'],reverse=True)
l
#score가 높은 내림차순으로 정렬됨

 

Out[12]:

[{'name': 'paul', 'score': 92}, {'name': 'john', 'score': 83}]

 

In [14]:

#선형탐색-탐색 알고리즘(1)
'''리스트에서 순차적으로 진행하며 특정값을 찾음
O(n) : 리스트의 길이에 비례하는 시간소요'''

def linear_search(L,x):
    i=0
#리스트 범위 벗어날때 [i<len(L)] 탈출 and 같은 값 나오면[L[i]!=x] 탈출
    while i<len(L) and L[i]!=x:
        i+=1
    if i<len(L):
        return i
    else:
        return -1
s=[3,8,2,7,6,10,9]
linear_search(s,6)

 

Out[14]:

4

 

In [15]:

linear_search(s,1)

 

Out[15]:

-1

 

In [ ]:

#이진탐색-탐색 알고리즘(1)
'''탐색하려는 리스트가 이미 크기순으로 정렬되어 있는 경우 적용
중간값보다 큰지 작은지를 보고, 계속 반복해 제거해 나감

O(log n) : 한 번 비교가 일어날 때마다 리스트 반씩 줄임(divide & conquer)'''

 

In [17]:

#3강 실습: 이진 탐색 구현해보기(x와 일치하는 인덱스를 리턴)
def solution(L, x):
    answer = -1
    left=0
    right=len(L)-1
    while right>=left:
        idx=(right+left)//2
        if L[idx]>x:
            right=idx-1
        elif L[idx]<x:
            left=idx+1
        else:
            answer=idx
            break
    return answer

solution([2, 3, 5, 6, 9, 11, 15], 3)

 

Out[17]:

1

 

In [22]:

#4강 :재귀 알고리즘 기초
'''자신을 다시 호출하는 알고리즘
예) 2진트리 
   12
 9    17
5 10 15 23
10을 찾으시오 : 12보다 작아 왼쪽, 9보다 커 오른쪽

자연수의 합:1부터 n까지 모든 자연수의 합'''
def sum(n):
    #이 부분이 없다면 n이 -무한대로 수렴해 실행이 안됨
    #재귀알고리즘 작성시 주의할점 : 종결조건을 잘 생각해볼것
    if n<=1:
        return n
    else:
        return n+sum(n-1)
a=int(input())
print(sum(a))

 

 

10
55

 

In [ ]:

'''해석
속도 : O(n)으로 일반적 방식과 비슷하지만, 함수를 호출하고 리턴하는데
부가적 작업이 있어 효율성이 부족함.

추가예제
def fac(n):
    if n<=1:
        return 1
    else:
        return n*fac(n-1)
펙토리알 계산 : 직관성 측면에서 재귀 알고리즘이 우월'''

 

In [ ]:

#4강 실습: 피보나치 순열 구현하기
def solution(x):
    answer = 0
    if x==0:
        answer=0
    elif x==1:
        answer=1
    else:
        answer=solution(x-1)+solution(x-2)
    return answer

 

In [31]:

#5강 재귀 알고리즘 응용
'''예) 조합의 수 계산
재귀 안쓰는 방법
from math import factorial
def combi(n,m):
    return factorial(n)/(factorial(m)*factorial(n-m))
    
재귀 쓰는 방법 : n-1 C m + n-1 C m-1
n-1 C m : 특정 원소를 포함하는경우
n-1 C m-1 : 그렇지 않은경우
def combi(n,m):
    #trivial case(기본적이거나 쉽게 해결 가능한 상황) 
    if n==m:
        return 1
    elif m==0:
        return 1
    else:
        return combi(n-1,m)+combi(n-1,m-1)

해석 : 중복 계산이 있을수 있어 재귀 사용이 더효율적이진 않다. 
그러나 사람이 생각하는 직관적 방식으로 코드를 짤수 있음. 
예를 들면 하노이의 탑,피보나치 같은경우.'''
#효율성 비교(피보나치 2가지 방식으로)
def rec(n):
    if n<=1:
        return n
    else:
        return rec(n-1)+rec(n-2)
    
def iter(n):
    if n<=1:
        return n
    else:
        i=2
        t0=0
        t1=1
        while i<=n:
            t0,t1=t1,t0+t1
            i+=1
        return t1
while True:
    nbr=int(input())
    if nbr==-1:
        break
    ts=time.time()
    iter1=iter(nbr)
    ts=time.time()-ts
    print(f'iter 버전 : {iter1} ({ts})')
    ts=time.time()
    rec1=rec(nbr)
    ts=time.time()-ts
    print(f'rec 버전 : {rec1} ({ts})')

 

 

10
iter 버전 : 55 (0.0)
rec 버전 : 55 (0.0)
30
iter 버전 : 832040 (0.0)
rec 버전 : 832040 (0.363081693649292)
40
iter 버전 : 102334155 (0.0)
rec 버전 : 102334155 (44.27177095413208)
-1

 

In [ ]:

#해석 : 재귀적 방법이 회수가 많을수록 시간이 급격히 늘어남

 

In [32]:

#5강 실습: 재귀적 이진 탐색 구현하기
def sol(L,x,l,u):
#if x not in L: 이 조건으로 했다가 시간이 초과했다.
#x not in L는 시간복잡도 + O(n) , l>u는 시간복잡도 +O(1)
    if l>u:
        return -1
    mid=(l+u)//2
    if x==L[mid]:
        return mid
    elif x<L[mid]:
        return sol(L,x,l,mid)
    else:
        return sol(L,x,mid,u)

 

In [ ]:

#6강 알고리즘의 복잡도
'''시간복잡도 : 문제의 크기와 해결에 걸리는 시간 사이의 관계
공간복잡도 : 문제의 크기와 해결에 필요한 메모리 공간사이 관계

평균시간 복잡도: 임의의 입력 패턴에서 평균적인 시간
최악 시간 복잡도 : 가장 긴 시간을 소요할때의 시간

Big-O Notation(점근표기법)
어떤 합수의 증가 양상을 다른 함수와 비교(알고리즘 복잡도에 쓰임)
O(log n),O(n),O(n^2),O(2^n)

입력에 크기가 n일때
O(log n) - (입력 크기의)로그에 비례하는 시간 이진 검색 
알고리즘은 O(log n)의 시간 복잡도를 갖습니다. 검색 범위를 
반으로 나누어 찾고자 하는 요소를 빠르게 찾는데 사용됩니다.
예)이진 탐색 알고리즘

O(n) - (입력 크기에)비례하는 선형 시간 알고리즘
리스트에서 특정 요소를 찾는 선형 검색 알고리즘은 O(n)의 시간 
복잡도를 갖습니다. 모든 요소를 한 번 씩 검색해야 합니다.
예)검색 알고리즘 : average case[O(n)], worst case[O(n)]

O(nlog n) - 정렬 문제에서 가장 효율적인 병합정렬
정렬한 데이터를 반씩 나누다가(O(log n)), 1개씩 남으면,
반대로 작은 값부터 순서대로 합쳐준다(O(n))
예)시험지를 조금씩 나눠서 분류하고, 한꺼번에 합체

O(n^2) - (입력 크기에)제곱 비례하는 시간 복잡도
이차원 배열을 순회하며 모든 요소의 조합을 검사하는 
이중 반복문은 O(n^2)의 시간 복잡도를 갖습니다.
예)삽입정렬 알고리즘: best case[O(n)] : 만약 이미 정렬됐을때
,worst case[O(n^2)] : 역순으로 돼있을때

O(2^n) - 지수 시간 복잡도:
부분 집합을 생성하거나 모든 가능한 경우의 수를 검사할 때
발생하는 경우가 O(2^n)의 시간 복잡도를 갖습니다. 
예를 들어, 완전탐색 알고리즘(조합,순열,부분집합, 체스 등).'''