[스터디 노트] Week4_3일차 [unit31 ~ 47] - 알고리즘 문제 풀이

1. 알고리즘 문풀_1 ~ 2 [unit 31 ~ 38]

---

📍 [연습문제] 검색 알고리즘(1)

• 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자.

1. 검색 모듈은 선형 검색 알고리즘을 이용하자.
2. 리스트는 1부터 20까지의 정수 중에서 난수 10개를 이용하자.
3. 검색 과정을 로그로 출력하자.
4. 검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없다면 –1을 출력하자.

import random

num_r = random.sample(range(1, 21), 10)
user = int(input("찾으려는 숫자 입력: "))
print(f"Numbers: {num_r}")
result_idx = 0

for idx, value in enumerate(num_r):
    if user == value:
        print("Search SUCCESS!!")
        print(f"Search result INDEX: {idx}")
        result_idx += idx
        break
    
print(">"*3, "Search Results", "<"*3)
print(f"search result index: {result_idx}")
print(f"search result number: {user}")
>>>
찾으려는 숫자 입력: 7
Numbers: [10, 11, 7, 2, 19, 20, 8, 16, 17, 5]
Search SUCCESS!!
Search result INDEX: 2
>>> Search Results <<<
search result index: 2
search result number: 7

---

📍 [연습문제] 순위 알고리즘(1)

• 숫자로 이루어진 리스트에서 아이템의 순위를 출력하고, 순위에 따라 아이템을 정렬하는 모듈을 만들어보자.
• 리스트는 50부터 100까지의 난수 20개를 이용하자.

def rank_algorithm(ns):
    
    ranks = [0 for i in range(len(ns))]
    
    for idx, n1 in enumerate(ns):
        for n2 in ns:
            if n1 < n2:
                ranks[idx] += 1
                
    print(f"s_nums: {ns}")
    print(f"ranks: {ranks}")
    
    sort_nums = [0 for i in range(len(ns))]
    
    for idx, rank in enumerate(ranks):
        sort_nums[rank] = ns[idx]
    
    return sort_nums

import random

if __name__ == "__main__":
    num_r = random.sample(range(50, 101), 20)
    s_nums = rank_algorithm(num_r)
    print(f"s_nums: {s_nums}")
>>>
s_nums: [72, 73, 74, 87, 51, 100, 78, 96, 58, 66, 98, 95, 76, 53, 88, 86, 52, 85, 77, 68]
ranks: [13, 12, 11, 5, 19, 0, 8, 2, 16, 15, 1, 3, 10, 17, 4, 6, 18, 7, 9, 14]
s_nums: [100, 98, 96, 95, 88, 87, 86, 85, 78, 77, 76, 74, 73, 72, 68, 66, 58, 53, 52, 51]

---

📍 [연습문제] 버블정렬 알고리즘(1)

• 숫자로 이루어진 리스트를 버블정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자.
• (단 정렬하는 과정도 출력하도록 한다.)

import random
import copy 

def bubble_sort(lst1, lst2):
    n1 = len(lst1)
    n2 = len(lst2)
    
    for i in range(n1):
        for j in range(0, n1-i-1):
            if lst1[j] > lst1[j+1]:
                lst1[j], lst1[j+1] = lst1[j+1], lst1[j]
    for i in range(n2):
        for j in range(0, n2-i-1):
            if lst2[j] < lst2[j+1]:
                lst2[j], lst2[j+1] = lst2[j+1], lst2[j]
                
    return lst1, lst2

num_r1 = random.sample(range(1, 20), 10)
num_r2 = num_r1.copy()

print(f"not sorted nums: {num_r}")
ASC, DESC = bubble_sort(num_r1,num_r2)
print(f"sorted nums by ASC: {ASC}")
print(f"sorted nums by DESC: {DESC}")
>>>
not sorted nums: [2, 4, 6, 9, 11, 12, 13, 14, 16, 18]
sorted nums by ASC: [1, 2, 3, 6, 7, 8, 10, 15, 16, 17]
sorted nums by DESC: [17, 16, 15, 10, 8, 7, 6, 3, 2, 1]

---

2. 알고리즘 문풀_3 ~ 4 [unit 39 ~ 46]

---

📍 [연습문제] 최댓값 알고리즘(1)

• 최댓값 알고리즘을 이용해서 숫자로 이루어진 리스트에서 최댓값과 최댓값의 개수를 찾는 모듈을 만들어보자.
• (리스트는 1부터 50까지의 난수 30개를 이용하되, 중복이 허용되도록 한다.)

import random

def max_lst(lst):
    max_num = lst[0]
    
    for num in lst:
        if num > max_num:
            max_num = num
            
    return max_num
    
    
num_r = [random.randint(1, 50) for i in range(30)]
max_num = max_lst(num_r)
max_num_cnt = num_r.count(max_num)

print(f"nums: {num_r}")
print(f"max num: {max_num}")
print(f"max num cnt: {max_num_cnt}")
>>>
nums: [44, 3, 39, 19, 22, 10, 5, 25, 27, 10, 22, 48, 49, 29, 27, 3, 6, 7, 49, 29, 37, 49, 44, 2, 42, 38, 41, 25, 35, 33]
max num: 49
max num cnt: 3

---

📍 [연습문제] 최솟값 알고리즘(1)

• 최솟값 알고리즘을 이용해서 숫자로 이루어진 리스트에서 최솟값과 최솟값의 개수를 찾는 모듈을 만들어보자.
• (리스트는 1부터 50까지의 난수 30개를 이용하되, 중복이 허용되도록 한다.)

import random

def min_lst(lst):
    min_num = lst[0]
    
    for num in lst:
        if num < min_num:
            min_num = num
            
    return min_num
    
    
num_r = [random.randint(1, 50) for i in range(30)]
min_num = min_lst(num_r)
min_num_cnt = num_r.count(min_num)

print(f"nums: {num_r}")
print(f"min num: {min_num}")
print(f"min num cnt: {min_num_cnt}")
>>>
nums: [30, 33, 5, 46, 6, 1, 25, 24, 1, 50, 16, 3, 6, 38, 44, 50, 19, 42, 45, 22, 35, 49, 1, 41, 27, 43, 29, 45, 44, 22]
min num: 1
min num cnt: 3

---

📍 [연습문제] 재귀 알고리즘(1)

• 다음은 ‘A상사’의 2021년 월별 매출을 나타내는 표이다.
• 재귀 알고리즘을 이용해서 1월부터 12월까지 전월대비 매출 증감액을 나타내는 프로그램을 만들어보자.

def calculate_monthly_change(sales, month):
    if month == 0:  # 1월은 전월이 없으므로 0을 반환
        return 0
    else:
        return sales[month] - sales[month - 1]  # 현재 월의 매출에서 전월의 매출을 뺀다.

def print_monthly_change(sales, month=0):
    if month < len(sales):
        change = calculate_monthly_change(sales, month)
        print(f"{month+1}월 매출 증감액: {change}")
        print_monthly_change(sales, month + 1)  # 다음 월로 재귀 호출

sales = [12000, 13000, 12500, 11000, 10500, 98000, 91000, 91500, 10500, 11500, 12000, 12500]  # A상사의 2021년 월별 매출
print_monthly_change(sales)
>>>
1월 매출 증감액: 0
2월 매출 증감액: 1000
3월 매출 증감액: -500
4월 매출 증감액: -1500
5월 매출 증감액: -500
6월 매출 증감액: 87500
7월 매출 증감액: -7000
8월 매출 증감액: 500
9월 매출 증감액: -81000
10월 매출 증감액: 1000
11월 매출 증감액: 500
12월 매출 증감액: 500