exp_blog

1.이진 탐색 (Binary Search)

• 탐색할 자료 둘로 나누어 해당 데이터가 있을만한 곳 탐색
• 순차탐색과 비교해보면 이진탐색이 훨씬 더 효율적인 것을 알 수 있다

[저작자] by penjee.com

2. 분할정복 VS 이진 탐색

• 분할 정복 알고리즘(Divide and Conquer)
  • 분할 : 문제를 하나 또는 둘 이상으로 나눔
  • 정복 : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결 , 그렇지 않다면 다시 나눔
• 이진 탐색
  • 이진 : 리스트를 2개의 서브 리스트로 나눔
  • 탐색
    • 검색할 숫자(search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자 찾는다
    • 검색할 숫자(search) < 중간값 이면, 앞 부분 서브 리스트에서 검색할 숫자 찾는다

3. 코드 생성

-> 이미 정렬되어 있는 상태에서 진행해야 함

• [2,3,8,12,20] 일 때,
  • b_search(data_list , find_data) 함수 생성
    • find_data  : 찾는 숫자
    • data_list : 데이터 리스트
    • data_list의 중간값을 find_data와 비교
      • find_data < data_list[mid] 이면
        • 맨 앞부터  data_list[mid] 에서 다시 find_data 찾기
      • find_data > data_list[mid] 이면
        • data_list[mid] 부터 맨 끝까지 다시 find_data 찾기
      • 그렇지 않으면, data_list[mid] = find_data 이므로 
        • return data_list[mid]

4. 알고리즘 구현

def b_search(data, search):
	print(data)
    if len(data) == 1 and search == data[0]:
    	return True
    if len(data) == 1 and search != data[0]:
    	return False
    if len(data) == 0:
    	return False
    
    
    mid = len(data)//2
    
    if search == data[mid]:
    	return True
    else: 
    	if search > data[mid]:
        	return b_search(data[mid+1:], search)
        else:
        	return b_search(data[:mid], search)


import random
data_list = random.sample(range(100), 10)
>>>data_list.sort()
>>>[2, 5, 19, 21, 42, 47, 67, 72, 92, 98]

>>>b_search(data_list, 67)
>>>[2, 5, 19, 21, 42, 47, 67, 72, 92, 98]
>>>[67, 72, 92, 98]
>>>[67, 72]
>>>[67]
>>>True

5. 알고리즘 분석

-> n 개의 리스트를 매번 2로 나누어 1이 될 때까지 비교 연산 k회 진행하기 때문에

     k + 1 

1. 순차 탐색 이란?

• 데이터가 담겨있는 리스트를 앞에서 부터 하나씩 비교해서 원하는 데이터 찾는 방법

2. 연습

• data_list에 렌덤으로 10 개가 들어있을 때, 원하는 데이터의 위치를 리턴하는 순차탐색 알고리즘 작성
  • 원하는 데이터가 리스트에 없으면 -1 리턴

from random import *

data_list = list()
for num in range(10):
	data_list.append(randint(1,100))
    
>>>data_list
>>>[100, 87, 79, 14, 35, 84, 77, 88, 37, 61]

def sequencial(data_list, search_data):
	for index in rnage(len(data_list)):
    	if data_list[index] == search_data:
        	return index
    return -1


>>> sequencial(data_list, 77)
>>> 6

3. 알고리즘 분석

최악의 경우 리스트 길이가 n일 때, n번 비교해야 함

• O(n)

1. 퀵 정렬 (quick sort) 이란?

• 기준점(pivot 이라고 부름) 정해
  기준점보다 작은 데이터는 왼쪽(left)
  큰 데이터는 오른쪽(right) 으로 모으는 함수
• 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 리턴

 2. 구현

• quicksort 함수 만들기
  • 만약 리스트 갯수가 한개이면 해당 리스트 리턴
  • 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 놓기
  • left, right 리스트 변수를 만들고,
  • 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교(pivot)
    • 기준점보다 작으면 left.append(해당 데이터)
    • 기준점보다 크면 right.append(해당 데이터)
  • return quicksort(left) + pivot + quicksort(right) 로 재귀 호출

def qsort(data):
	if len(data) <= 1:
    	return data
    
    left, right = list(), list()
    pivot = data[0]
    
    for index in range(1, len(data)):
    	if pivot > data[index]:
        	left.append(data[index])
        else:
        	right.append(data[index])
    return qsort(left) + [pivot] + qsort(right)

#list comprehension 사용해서 깔끔하게

def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]

    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    
    return qsort(left) + [pivot] + qsort(right)

import random

data_list = random.sample(range(100), 10)

qsort(data_list)

>>>[7, 17, 19, 24, 34, 55, 60, 85, 86, 88]

 3. 분석

시간복잡도는 O(n log n)

• 단, 최악의 경우
  • 맨 처음 pivot이 가장 크거나, 가장 작으면
  • 모든 데이터를 비교하는 상황이 나옴
  • O(𝑛2n2)

1. 병합 정렬(merge sort)

-> 재귀용법을 활용한 정렬 알고리즘

• 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다

2. 알고리즘 이해

• data_list = [1,9,3,2]
  • [1,9]       [3,2]
  • [1] [9]
  • 다시 정렬해서 합침   [1, 9]
  • [3] [2]
  • 다시 정렬해서 합침   [2, 3]
  • [1, 9]    [2, 3] 합침
    • [1] 
    • [9] > [2]   =>  [1 , 2] 
    • [9] > [3]    => [1, 2, 3]
    • [1, 2, 3, 9]

3. 구현

<mergesplit 함수 만들기>

• 리스트 개수가 1개 -> 해당 값 리턴
• 아니면                      -> 리스트 앞, 뒤 2개로 나누기
• left = mergesplit(앞)
• right = mergesplit(뒤)
• merge(left, right)

def mergesplit(data):
	if len(data) <= 1:
    	return data
    m = int(len(data) / 2)
    left = mergesplit(data[:m])
    right = mergesplit(data[m:])
    return merge(left, right)

<merge 함수 만들기>

• 목표: left 와 right 의 리스트 데이터를 정렬해서 sorted_list 라는 이름으로 return 하기
• left와 right는 이미 정렬된 상태 또는 데이터가 하나임

• 리스트 변수 하나 만들기 -> sorted
• left_idx , rigth_idx = 0
• while left_idx < len(left)   or  right_idx < len(right):
  • 만약, left_idx 나 right_idx 가 이미  left 또는 right 리스트를 다 순회했다면, 
    그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가
  • if left[left_idx] < right[right_idx]:
         sorted.append(left[left_idx])
         left_idx += 1
  • else:
         sorted.append(right[right_idx])
         rigth_idx += 1

def merge(left, right):
	merged = list()
    left_p , right_p = 0, 0
    
    #left/right 둘 다 존재
    while len(left) > left_p and len(right) > right_p:
    	if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    #left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    #right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

최종 코드

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    #left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    #left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    #right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged


def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

import random

data_list = random.sample(range(100), 10)
mergesplit(data_list)

>>>[13, 17, 28, 30, 36, 45, 48, 65, 70, 73]

4. 알고리즘 분석

• 따라서, 각 단계는 항상 O(n) 
• 단계는 항상 𝑙𝑜𝑔2𝑛개 만큼 만들어짐, 시간 복잡도는 결국 O(log n), 2는 역시 상수이므로 삭제
• 따라서, 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)

1. 정의

• 동적계획법 (DP 라고 많이 부름)
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
  • Memoization 기법을 사용함
    • Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
  • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
    • 예: 피보나치 수열
• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현
  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
    • 예: 병합 정렬, 퀵 정렬 등

2. 공통점과 차이점

• 공통점
  • 문제를 잘게 쪼개서, 가장 작은 단위로 분할
• 차이점
  • 동적 계획법
    • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
    • Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
  • 분할 정복
    • 부분 문제는 서로 중복되지 않음
    • Memoization 기법 사용 안함

3. 동적 계획법 알고리즘

피보나치 수열: n 을 입력받아서 다음과 같이 계산됨
n 을 입력받았을 때 피보나치 수열로 결과값을 출력하세요

def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]
    
    
>>>fibo(10)
55

1. 재귀 용법 (recursive call, 재귀 호출)

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용되므로, 익숙해져야 함

2. 예제

- 팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기

분석

• 간단한 경우부터 생각해보기
  • 2! = 1 X 2
  • 3! = 1 X 2 X 3
  • 4! = 1 X 2 X 3 X 4 = 4 X 3!
• 규칙이 보임: n! = n X (n - 1)!
  1. 함수를 하나 만든다.
  2. 함수(n) 은 n > 1 이면 return n X 함수(n - 1)
  3. 함수(n) 은 n = 1 이면 return n
• 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함)
  • 먼저 4! 부터
    • 함수(4) 이면, 4 > 1 이므로 4 X 함수(3)
    • 함수(3) 은 결국 2번에 의해 3 X 2 X 1 = 6
    • 4 X 함수(3) = 4 X 6 = 24 !!

코드

def factorial(n):
	if n > 1:
    	return n * factorial(n - 1)
    else:
    	return n

for n in range(10):
	print(factorial(n))

>>>
0
1
2
6
24
120
720
5040
40320
362880

시간, 공간 복잡도

• factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함

  • 일종의 n-1번 반복문을 호출한 것과 동일
  • factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨

• 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)

3.재귀 호출 일반적인 형태 

#일반적인 형태 1
def function(입력):
	if 입력 > 입력값: #입력이 일정 값 이상이면
    	return function(입력 -1) #입력 보다 작은 값
    else:
    	return 일정값, 입력값, 또는 특정값 #재귀 호출 종료

#일반적인 형태2
def function(입력):
	if 입력 <= 일정값: #입력이 일정값보다 작으면 
    	return 일정값, 입력값 또는 특정 값 #재귀호출 종료
    function(입력보다 작은 값)
    return 결과값

def factorial(num):
	if num <= 1:
    	return num
    return num * factorial(num - 1)
 

for num in range(10):
	print(factorial(num))
>>>
0
1
2
6
24
120
720
5040
40320
362880

함수는 내부적으로 스택처럼 관리

4. 알고리즘 

1) 1부터 num 까지 곱이 출력되게 생성

>>>def multiple(num):
	if num <= 1:
    	return num
    return num * multiple(num -1)
    
>>>multiple(20)
2432902008176640000

2)  숫자가 들어있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수로 만듬 

##임의 값으로 리스트 생성하는 방법

import random

data = random.sample(range(100), 10)
data

[15, 18, 57, 89, 17, 28, 23, 73, 75, 60]

<알고리즘>

def sum(data):
	if len(data) <= 1:
    	return data[0]
    return data[0] + sum(data[1:])
    
>>>sum(data)
455

3)  회문 판별할 수 있는 함수를 재귀함수로 생성

##회문(palindrome)이란? : 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장 의미 / 리스트를 슬라이싱 활용하여 만듬

def palidrome(string):
	if len(strung) <= 1:
    	return True
    
    if string[0] == string[-1]:
    	return palindrome(string[1:-1])
    else:
    	return False

4) 정수 n 이 홀수면 3*n +1 , 짝수이면 n/2 => n이 결국 1이 될 때까지 계속 반복하여 1이 되는 모든 과정 출력

ex) 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

def func(n):
	print(n)
    if n == 1:
    	return n
    
    if n % 2 == 1:
    	return (func((3*n) +1))
    else:
    	return (func(inf(n/2)))
        
>>>func(3)
3
10
5
16
8
4
2
1

- 배열의 인덱스를 특정 데이터 값으로 여기는 정렬 방법

- 배열 크기는 데이터의 범위를 포함할 수 있도록 설정

- 데이터가 등장한 횟수를 셈

예시 데이터 

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

=> 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 

데이터를 숫자 순대로 인덱스에 넣고 , 그 인덱스 크기 자체를 비교하고 for문을 통해 반복하면 오름차순, 내림차순으로 정렬가능

# 유의사항  : 데이터 개수가 많을 때 파이썬에는 sys.stdin.readLine() 을 사용하여야 한다.

1. 삽입 정렬?

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

2. 패턴 찾기

• 처음은 항상 인덱스(0)+1 에서 시작
• data_list = [9, 3, 2, 5]
  • 1회 : key 값 (9) , 인덱스(0) -1 보다 작으므로 => [9,3,2,5]
  • 2회 : key 값 (3) , key -1 값(9) 이 3보다 작으므로 => [3,9,2,5]
  • 3회 : key 값(2) , key -1 값(9) 보다 작고 -> key -2 값(2) 이 더 작으므로 => [2,3,9,5]
  • 4회 : key 값(5), 9보다 작고, 3보다 크므로 => [2,3,5,9]

1. for stand in range(len(data_list)) 로 반복
2. key = data_list[stand]
3. for num in range(stand, 0, -1) 반복
    - 내부 반복문 안에서 data_list[stand] < data_list[num - 1] 이면,
    - data_list[num - 1], data_list[num] = data_list[num], data_list[num - 1]

3. 알고리즘

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

import random

data_list = random.sample(range(20), 10)
print (insertion_sort(data_list))

>>[0, 3, 4, 5, 11, 12, 14, 17, 18, 19]

rand_data_list = [3, 5, 1, 2]

def insertion_sort(data_list):
    for stand in range(len(data_list)):
        key = data_list[stand]
        for num in range(stand, 0, -1):
            if key < data_list[num - 1]:
                data_list[num - 1], data_list[num] = data_list[num], data_list[num - 1]
            else:
                break
    return data_list

print (insertion_sort(rand_data_list))

4. 알고리즘 분석

• 반복문이 두 개 O(𝑛2)
  • 최악의 경우, 𝑛∗(𝑛−1)2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)