단순탐색, 이진탐색, 빅오표기법, 선택정렬, 재귀

100개의 아이템이 있는데 이것들 중 어떤 1개를 찾으려고 한다.

1. 단순탐색이란?

100개의 아이템이 있다면  > 100번의 추측을 통해  아이템을 찾을 수 있다.

추측해야할 최대횟수가 리스트길이와 같으면 선형시간(linear time)이다.

40억개의 아이템 > 40억번 추측

2. 이진탐색이란?

100개의 아이템이 있다면 > 7번의 추측을 통해 아이템을 찾을 수 있다.

40억개의 아이템 > 32번 추측

이진탐색은 로그시간(logarithmic time)이다.

ex 1) 종이를 접어 16개의 네모칸을 만들려고 한다.

한번의 하나의 네모칸 그리면 16번 그려야하지만

종이를 반으로 접고 접은 것에 다시 접고 또 접고 4번의 연산으로 16개의 네모칸을 만들었다.

ex 2) 정렬되지 않은 이름노트에 sanghyun 이라는 이름을 찾는다고 해보자.

sanghyun 이라는 이름을 찾는다면 맨앞에 나올수 있고 맨 뒤에 나올수 있다.

맨앞에 나오면 O(1) 로 바로 끝나지만 최악인 경우 모든 이름을 다 확인해 맨뒤에서 찾을 경우 O(n)이 걸린다.

3. 빅오표기법이란?

빅오O를 붙이고 수행시간에 대해 명시한것이다.

빅오표기법은 최악의 경우에 대한 것이다. 최악의 경우보다 느려지지 않는다는 보장하는 것을 말한다.

빅오실행시간의 예

O(log n) 로그시간 : ex) 이진탐색

O(n) 선형시간 : ex) 단순 탐색

O(n*log n) : ex) 퀵 정렬(빠름)

O(n^2) : ex) 선택정렬(느림)

O(n!) : ex) 외판원 문제(정말 느림)

빠름 <<<                                      >>>느림

O(log n) > O(n) > O(n*log n) > O(n^2) > O(n!)

3.1 외판원 문제

미국 중국 한국 캐나다 일본을 여행한다고 한다.

가장 짧은 거리를 통해 다섯개 국가의 수도를 모두 방문하고 싶다.

이 국가들의 수도를 방문하려면 총 몇가지가  있을까?

도시를 방문하는 모든 경로를 살펴봐야한다.

그 다음 전체 거리를 더해서 가장 짧은 경로를 택하면 된다.

도시가 5개이면 120가지 경우가 있다.

5! = 5*4*3*2*1 = 120

6개일 경우

6! = 6*5*4*3*2*1 = 720

7개일 경우 5040개이다.

알고리즘의 속도는 시간이 아니라 연산횟수가 어떻게 증가하는지로 측정한다.

4. 배열과 리스트

메모리에 무언가를 저장할때 마다 컴퓨터에게 공간을 요청한다.

여러개의 원소를 저장해야 한다면 배열과 리스트 중 하나를 사용한다.

배열과 리스트는 장단점이 있다.

극장에서 2명이 영화를 보러갔는데 친구 1명이 추가되어 3명이 되었다. 

2명 자리 옆에는 다른사람이 앉아 있어서 추가된 친구 1명과 같이 나란히 3명이 앉을수 없다.

이런경우 컴퓨터에게 3개의 자리가 있는 다른 메모리공간을 요청한다. 그리고 3명의 자리로 옮겨야 한다.

만약 또다른 친구가 오게 되면 4명이 되고 자리가 모자라 전원이 같이 다른자리로 이동해야 한다.

공간이 모잘라서 매번 모든 원소를 메모리의 새로운 위치로 옮긴다면 배열에 원소를 추가하는 작업이 느려진다

이것을 고칠수 있는 방법은 좌석을 미리 예약하는 것이다.

4.1 배열의 단점

1. 그래서 원래는 친구 2명이서 영화를 본다고 했지만 앞으로 친구를 만날 가능성이 있으니 

컴퓨터에게 10개의 자리를 요청한다.

그러면 전체 배열을 옮기지 않아도 10개까지는 추가할수 있다.

2. 하지만 추가할일이 생기지 않는 다면 메모리를 쓸데없이 낭비하게 된다.(다른사람도 자리를 이용못하고 예약한 사람도 사용안하기 떄문)

목록의 크기가 10개보다 커진다면 자리를 옮겨야 한다.

이러한 문제점으로 연결리스트를 사용한다.

4.2 연결리스트의 장점

1. 원소를 추가할때 생기는 문제를 해결할수 있다.

연결리스트를 사용하면 원소를 메모리 어느곳에나 둘수 있다.

각 원소에는 목록의 다음원소에 대한 주소가 저장되어 있다.

2. 여러가지 임의의 메모리 주소들이 하나의 목록으로 연결되어 있는 것이다.

연결리스트를 사용하면 원소를 추가하는 일이 쉽다.

3. 그냥 메모리 아무곳에나 원소를 넣고 그 주소를 바로 앞의 원소에 저장해 놓으면 된다.

연결리스트를 사용하면 원소를 옮길 일이 없다.

4. 영화를 보러 5명이 갔는데 붙어서 볼수 있는 자리 5자리가 없다.

배열 10000개 중 10000개 공간에 있기는 하지만 모두 이어진 10000개 자리는 없을수도 있다.

그러면 배열을 만들수 없다.

하지만 연결리스트를 사용한다면 일단 흩어져서 영화를 보자 배열을 만들 공간은 없어도 

연결리스트를 만들 공간은 있는 것입니다.

원소를 추가하기에는 연결리스트가 좋다면

배열이 연결리스트보다 나은점은 읽기이다.

	배열	리스트
읽기	O(1)	O(n)
삽입	O(n)	O(1)
삭제	O(n)	O(1)

4.3 리스트에 가운데에 삽입하기

원소를 배열이나 리스트의 중앙에 삽입한다면 배열과 리스트 중 어느 것이 나을까?

배열은 다음에 오는 모든 원소의 위치를 바꿔야함.

공간이 부족하면 모든 원소를 새로운 장소로 복사해야 한다.

중간에 원소 삽입은 리스트가 나음.

4.4 삭제하기

이전 원소가 가르키는 위치만 바꾸면 되기 때문에 리스트가 낫다

배열에서는 원소하나만 삭제하고 싶을때도 모든 것을 다 옮겨야 한다.

4.5 배열과 리스트 중 어떤것을 많이 사용하나?

임의의 원소에 접근하는 것이 가능하기 때문에 배열을 쓰는 경우가 많다.

연결리스트는 순차접근(sequential access) 밖에 할수 없다.

연결리스트에 있는 10번째 원소를 읽으려면 그 앞에 9개 원소를 모두 읽어서 10번째 원소로 가는 링크를 찾아내야 한다.

임의접근은 10번째 원소로 바로 건너뛸수 있다.

5. 선택정렬

컴퓨터 음악이 가장 많이 들은것부터 정렬하고 싶다.

1. 리스트의 모든항목을 살펴보고 가장 많이 연주된 가수를 찾아 새로운 리스트에 기록

2. 그다음으로 많이 들은 가수를 찾아 반복한다.(계속 반복하면 정렬된 목록 얻을수 있다)

단순검색 가수목록에서 가수를 한명씩 찾아 봄 O(n)

연주횟수가 가장 많은 가수를 찾기 위해서는 목록의 모든항목을 점검 O(n)

O(n) * O(n) = O(n^2)

선택정렬 알고리즘은 전화번호부의 이름, 여행날짜, 이메일(최신받은 이메일부터) 이 있다.

이 정렬을 사용해서 작은 정수부터 큰 정수까지 정렬하는 선택정렬 코드를 작성해보자.

코드는 파이썬으로 작성하였다.

1. 선택정렬 코드

def findSmallest(arr):          # [5,3,6,2,10]
    smallest = arr[0]           # 5
    smallest_index = 0          # 0
    for i in range(1,len(arr)): # [5,3,6,2,10]
        if arr[i] < smallest:   # 3 < 5 true
            smallest = arr[i]   # smallest = 3
            smallest_index = i  # smallest_index = 1
    return smallest_index
 
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):               # 1 <= 5
        smallest = findSmallest(arr)        # [5,3,6,2,10]
        newArr.append(arr.pop(smallest))    # smallest_index = 3이므로 2 pop
        print("newArr값 ",newArr)
    return newArr
 
print (selectionSort([5, 3, 6, 2, 10]))

2. 파이썬의 range 함수 예제

# range 함수는 초기 값을 받은 range 값을 변경해도 반복문에 영향이 있지 않다.
# 5번 for문 실행한다.
 
def function1(index, num):
    for i in range(index, num):
        index = index+1
        num = num-4
        print("i값:",i)
    return i
 
print (function1(0,5))

6. 재귀

1. 재귀 함수의 기본적인 호출

def countDown(i):
    print (i)
    if i <= 1:
        return print("함수종료")
    else:
        countDown(i-1)
 
countDown(5)
 
#5, 4, 3, 2, 1
#함수종료

2. 재귀 함수의 스택 팝 과정 보기

def hello(name):
    print ("hello, " + name + "!")
    greet(name)
    print ("getting ready to say bye ... ")
    bye()
 
def greet(name):
    print ("how are you, " + name + "?")
    thanks(name)
    
def thanks(name):
    print ("thank you, " + name)
 
def bye():
    print ("ok bye!")
 
hello("sanghyun")
 
#hello, sanghyun!
#how are you, sanghyun?
#thank you, sanghyun
#getting ready to say bye ... 
#ok bye!

함수안의 함수를 호출하면 컴퓨터는 메모리상자 stack을 사용해 쌓아간다.

함수가 반환되면 pop연산으로 없어진다.

3. 재귀 함수 활용하여 팩토리얼 사용하기

def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x-1)
 
print(fact(5))
 
#120

자기 자신인 fact 함수를 계속 부르며 스택을 쌓고 난뒤

값을 반환(pop)하며 값을 구하고 있다.

fact(1) =1

x*fact(1) = 1

x*fact(2) = 2*1 = 2

x*fact(3) = 3*2 = 6

x*fact(4) = 4*6 = 24

x*fact(5) = 5*24 = 120

소스와 작업파일

recursionFunction1.py

selectionSort.py

callStack.pptx