알고리즘 문제 풀이(재귀호출(하노이의 탑), 순차 탐색, 선택 정렬, 삽입정렬)

재귀호출 (하노이의 탑)

# 6번 문제 (하노이의 탑)
def hanoi(n, from_pos, to_pos, aux_pos):
    if n == 1:
        print(from_pos, "->", to_pos)
        return
    
    hanoi(n-1, from_pos, aux_pos, to_pos)
    
    print(from_pos, "->", to_pos)
    
    hanoi(n-1, aux_pos, to_pos, from_pos)

 

print('n = 1')
hanoi(1, 1, 3, 2)
print('n = 2')
hanoi(2, 1, 3, 2)
print('n = 3')
hanoi(3, 1, 3, 2)

---

순차 탐색

# 7번 문제 (순차 탐색)
def search_list(a, x):
    n = len(a)
    
    for i in range(0, n):
        if x == a[i]:
            return i
        
    return -1
            
v = [17, 92, 18, 33, 58, 7, 33, 42]

 

search_list(v, 33)

 

# 7-1번 문제 (순차 탐색 - 모든 위치 리스트로 돌려주기)
def search_list_all_index(a, x):
    n = len(a)
    result_list = []
    for i in range(0, n):
        if x == a[i]:
            result_list.append(i)
        
    return result_list
            
v = [17, 92, 18, 33, 58, 7, 33, 42]

# 7-2번 문제 계산복잡도 -> O(n)

 

search_list_all_index(v, 33)

 

# 7-3번 문제
def stu_match(input_num):
    stu_no = [39, 14, 67, 105]
    stu_name = ['Justin', 'John', 'Mike', 'Summer']
    
    for i in range(0, len(stu_no)):
        if stu_no[i] == input_num:
            index_num = i
    
    return stu_name[index_num]

 

stu_match(39)

---

선택 정렬 알고리즘

# 8번 문제 - 선택 정렬 알고리즘 (O**2)
def sel_sort(a):
    n = len(a)
    for i in range(0, n-1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]: # 8-2번 문제 바꾸는 부분 -> 'a[j] < a[min_idx]' : 작은 수에서 큰 수, 'a[j] > a[min_idx]' : 큰 수에서 작은 수
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

 

list = [2, 4, 5, 1, 3]
sel_sort(list)
print(list)

---

삽입 정렬 알고리즘

# 9번 문제 - 삽입 정렬 알고리즘
def ins_sort(a):
    n = len(a)

    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key: # 9-2번 문제 바꾸는 부분 -> 'a[j] > key' : 작은 수에서 큰 수, 'a[j] < key' : 큰 수에서 작은 수
            a[j + 1] = a[j]
            j -= 1

        a[j + 1] = key

 

d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)