<jupyter_start><jupyter_text>사람들이 정렬, 재귀, 탐색 가장 어려워함  정렬 다음을 정렬하시오<jupyter_code>arr =  [ 7, 3, 2, 9]

## arr.sort()하면 안 됨!

## 버블 정렬
### 일단 함수를 만든다. 우리의 아웃풋이 어떻게 되야 될지 생각
### 결과는 배열형태

def bubbleSort(arr):
    
#     first = arr[0]
#     second = arr[1]
#     print(first == second) ## 이런씩으로 print 찍어보고 출력한
#                             # 한 다음에 확인하는 습관 가지기
    

    ## 자리 바꾸기
    ### 변수명으로 해도 됨, 하지만 변수 사용 최소화 해야
    ### 유틸함수도 최소화해야
    ### 리스트를 쓰면 공격당하기 쒸움
    ### 따라서 어레이만 쓰는 게 좋음
#     result = []
#     if first < second :
#         result.append(second)
#         result.append(first)
        
    ## Solution
    
    ## For를 이용해서 반복문으로 하자
    
    for frontIndex in range(0,2+1):
        for backIndex in range(1, 3 + 1):
            if arr[frontIndex] > arr[backIndex]:
                temp = arr[frontIndex]
                arr[frontIndex] = arr[backIndex]
                arr[backIndex] = temp

            print(backIndex, arr)
        
    return arr
        


## 버블 sort
## 1 round
## 0과 1 비교 [7, 3, 2, 9]
## 0과 2 비교 [3, 7, 2, 9]
## 0과 3 비교 [2, 7, 3, 9]
#### 가장 작은 게 맨 앞에 옴

## 2 round
## [2, 7, 3, 9] 1, 2 비교
## [2, 3, 7, 9] 1, 3 비교
## [2, 3, 7, 9]




### 유틸 변수는 
 
def bubbleSort_ny(arr):
    ## Mine
    length = len(arr)
    cnt = 1   
    while cnt :
        cnt = 0   
        for i in range(len(arr)-1):
            if arr[i] > arr[i+1]:
                temp = arr[i]
                arr[i] = arr[i+1]
                arr[i+1] = temp 
                cnt += 1
    return arr

## 계속 옆에만 비교하는게 아니라 한번 비교할 때 끝까지 뒤로 가게 못하나?

bubbleSort_ny(arr)

def bubbleSort(arr):
    
#     first = arr[0]
#     second = arr[1]
#     print(first == second) ## 이런씩으로 print 찍어보고 출력한
#                             # 한 다음에 확인하는 습관 가지기
    

    ## 자리 바꾸기
    ### 변수명으로 해도 됨, 하지만 변수 사용 최소화 해야
    ### 유틸함수도 최소화해야
    ### 리스트를 쓰면 공격당하기 쒸움
    ### 따라서 어레이만 쓰는 게 좋음
#     result = []
#     if first < second :
#         result.append(second)
#         result.append(first)
        
    ## Solution
    
    ## For를 이용해서 반복문으로 하자
    
    for frontIndex in range(0,len(arr) - 1):
        for backIndex in range(frontIndex + 1, len(arr)):
            if arr[frontIndex] > arr[backIndex]:
                temp = arr[frontIndex]
                arr[frontIndex] = arr[backIndex]
                arr[backIndex] = temp

            print(frontIndex,backIndex, arr)
        
    return arr
        


bubbleSort(arr)<jupyter_output>0 1 [2, 7, 3, 9]
0 2 [2, 7, 3, 9]
0 3 [2, 7, 3, 9]
1 2 [2, 3, 7, 9]
1 3 [2, 3, 7, 9]
2 3 [2, 3, 7, 9]<jupyter_text>재귀 Recursive 알고리즘 문제 단골자기 자신을 호출함<jupyter_code>## 이게 재귀함수
## 무한 루프를 돈다
## 자기 자신을 리턴해서

arr = [1, 2, 3, 4]

def sum(arr):
    #계산하는 로직
    result =  0
    for number in arr:
        result += number
        
    return result

## 이거를 For 문 없이 쓰는 게 문제!
## 재귀로 짜보자!
arr = [1, 2, 3, 4]

def sum(arr, accu):
    ## 재귀는 리턴 앞에 꼭 반복문이!!
    ## 특징 1. 무한히 돈다 따라서 탈출하는 로직이 꼭 필요!
    ## 특징 2. 결과는 파라미터에 있다 accu를 리턴해주는 것
    ## 특징 3. return 할 때 앞에서 쓴 변수의 일부가 다시 들어감

    if not arr:
            return accu
        
    accu += arr.pop()
    print(arr,accu)

    return sum(arr, accu)

print("result =>",sum(arr,0))
if(len(arr)):
    print('123')
## 1 ~ 100까지 루프 안쓰고 출력
## 재귀를 사용하자!

arr = list(range(1,101))
arr = arr[::-1]
def print_100(arr):
    if not arr:
        return "end"
    print(arr.pop())
    return print_100(arr)



def print_100(start):
    
    if start + 1 > 99:
        return print(100)
    
    print(start+1)
    
    return print_100(start+1)

def printNumber(num):
    if num > 100 : exit()
    print(num)
    printNumber(num + 1)    
printNumber(0)
# Factorail를 짜보세요. 10!의 결과가 나오는
# Loop 쓰지 말고

## 내 답
def factorial(num, result):
    
    if num == 0:
        return result
    
    result *= num
    return factorial(num-1, result)


## Solution

def factorial_sol(num):
    
    if num <=  1 :
        return 1
    
    ## Return  할 때 앞에 num이 들어간다
    ## 따라서 변수를 따로 선언할 필요가 없다!
    return num * factorial_sol(num-1)<jupyter_output><empty_output><jupyter_text>이진 탐색<jupyter_code># 3이 몇번째에 있는지 인젝스를 리턴하는 함수를 짜세요
# 없으면 -1 리턴
arr = [1 ,2 ,3,  4, 5, 6,7]

# 단순 탐색
# 속도는 O(n)
# def simSearch(arr, num):
#     for item in range(0, len(arr)):
#         if arr[index] == num:
#         return index
#     return -1

# 이진 탐색 핵심로직
# 1. 중간 값을 구해야됨
# 2. Array는 정렬이 되어 있어야됨

def binSearch(arr, num):
    
    # 중간값 찾기
    start = 0
    end = len(arr) - 1
    while(start <= end):

        midIndex = (start + end) // 2
        midValue = arr[midIndex]

        print("mi", midIndex, "mv" ,midValue)
        if midValue == num :
            return midIndex
        
        elif midValue < num :
            # 0-----------------4--------5------------6
            ### 어레이는 안 짜르고 사이즈 변화를 안 주는게 공간 복잡도가 낮다
            start = midIndex + 1
        elif midValue > num :

            end = midIndex - 1

    return - 1


## 공간 복잡도를 줄이고 싶으면
## midValue를 안 쓰면 됨 arr[midindex]로 바꾸기
## 하지만 현재 배열에 없는 값을 넣으면 에러가 나옴

print(binSearch(arr, 5))<jupyter_output>mi 3 mv 4
mi 5 mv 6
mi 4 mv 5
4
{'fraction_non_alphanumeric': 0.13322696449940166, 'fraction_numerical': 0.03669724770642202, 'mean_word_length': 1.6933404940923737, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '123537', 'license': 'MIT', 'n_tokens_mistral': 2672, 'n_tokens_neox': 2878, 'n_words': 622, 'path': 'algorithm_study.ipynb', 'repo_name': 'nakyilkim/Algorithm_Study', 'size': '5014'}