[스터디 노트] Week4_1일차 [unit1 ~ 18] - 알고리즘

1. 알고리즘_1 ~ 2 [unit 1 ~ 9]

---

📍 선형 검색

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.

[출처: zero-base]

• 검색 성공 or 검색 실패

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]

print(f"datas: {datas}")
print(f"data length: {len(datas)}")

user_n = int(input("찾으려는 숫자 입력: "))
search_result_idx = -1

n = 0
while True:
    
    if n == len(datas):
        search_result_idx = -1
        break
    elif datas[n] == user_n:
        search_result_idx = n
        break
    
    n += 1
    
print(f"search result idx: [{search_result_idx}]")
>>>
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
data length: 10
찾으려는 숫자 입력: 5
search result idx: [2]

# 리스트에서 숫자 ‘7’을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하자.
# nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
user = int(input("찾을 숫자 입력: "))
search_idx = 0
for i in range(len(nums)):

    if nums[i] == user:
        search_idx = i + 1
        print(f"{user}의 인덱스 위치는: {search_idx}")

user_cnt = nums.count(user)
print("="*30)
print(f"{user}의 검색 개수는: {user_cnt}")
>>>
찾을 숫자 입력: 7
7의 인덱스 위치는: 2
7의 인덱스 위치는: 6
7의 인덱스 위치는: 9
==============================
7의 검색 개수는: 3

---

📍 보초법

• 마직막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.

[출처: zero-base]

• 검색 성공: 마지막 이전에 ‘9’가 검색된 경우
• 검색 실패: 마지막에 ‘9’가 검색된 경우

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]

print(f"datas: {datas}")
print(f"data length: {len(datas)}")

user_n = int(input("찾으려는 숫자 입력: "))
search_result_idx = -1

datas.append(user_n)

n = 0
while True:
    
    if datas[n] == user_n:
        if n != lent(datas) - 1:
            search_result_idx = n
        break
    
    n += 1
    
print(f"datas: {datas}")
print(f"data length: {len(datas)}")
print(f"search result idx: [{search_result_idx}]")
>>>
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
data length: 10
찾으려는 숫자 입력: 7
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 7]
data length: 11
search result idx: [3]

---

📍 이진 검색

• 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.

# 리스트를 오름차순으로 정렬한 후 ‘7’을 검색하고 위치(인덱스)를 출력하자.
# nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]\\

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums.sort()

user = int(input("검색할 숫자 입력: "))
search_idx = 0

for i in range(len(nums)//2):
    
    if nums[i] == user:
        search_idx = i + 1
        break
print(f"오름차순: {nums}")
print(f"{user}의 인덱스 위치는: {search_idx}")
>>>
검색할 숫자 입력: 7
오름차순: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
7의 인덱스 위치는: 4

---

📍 순위

• 수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다

nums = [98, 67, 99, 52, 89, 78, 57, 65, 50, 74, 58, 71, 68, 96, 86, 85, 93, 94, 66, 97]
sorted_nums = sorted(nums, reverse = True)

rank = {}

for idx, value in enumerate(sorted_nums):
    rank[value] = idx + 1

for num in nums:
    print(f"score: {num}\\t rank: {rank[num]}")
>>>
score: 98	 rank: 2
score: 67	 rank: 14
score: 99	 rank: 1
score: 52	 rank: 19
score: 89	 rank: 7
score: 78	 rank: 10
score: 57	 rank: 18
score: 65	 rank: 16
score: 50	 rank: 20
score: 74	 rank: 11
score: 58	 rank: 17
score: 71	 rank: 12
score: 68	 rank: 13
score: 96	 rank: 4
score: 86	 rank: 8
score: 85	 rank: 9
score: 93	 rank: 6
score: 94	 rank: 5
score: 66	 rank: 15
score: 97	 rank: 3

---

2. 알고리즘_3 ~ 4 [unit 10 ~ 18]

---

📍 버블 정렬

• 가장 기본적인 정렬 알고리즘 중 하나로, 이름에서 알 수 있듯이 '버블'과 같이 큰 값이 배열의 맨 끝으로 이동해가는 모습을 보입니다.
  1. 리스트의 맨 처음부터 시작해서, 인접한 두 개의 요소를 비교합니다.
  2. 이때, 왼쪽 요소가 오른쪽 요소보다 크다면, 두 요소의 위치를 바꿉니다 (오름차순 정렬의 경우).
  3. 위의 과정을 리스트의 끝까지 반복합니다. 이 한 번의 통과를 거치면, 가장 큰 요소가 리스트의 끝으로 이동하게 됩니다.
  4. 이러한 과정을 리스트의 길이만큼 반복하게 되면, 전체 리스트가 정렬됩니다.

# 새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로
# 줄 세워 보자. 학생들의 키는 random 모듈을 이용해서 170 ~ 185사이로 생성한다.

import random

def bubble_sort(lst):
    n = len(lst)
    
    # 마지막 i 요소들은 이미 정렬된 상태이므로 확인하지 않아도 된다.
    for i in range(n):
        for j in range(0, n-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

stu_tall = random.sample(range(170, 186), 15)

print(f"lst: {stu_tall}")
print(f"bubble_sort_lst: {bubble_sort(stu_tall)}")
>>>
lst: [184, 174, 173, 177, 170, 176, 183, 181, 172, 171, 180, 182, 175, 178, 185]
bubble_sort_lst: [170, 171, 172, 173, 174, 175, 176, 177, 178, 180, 181, 182, 183, 184, 185]

---

⚡️ 메모  ' range(0, n-j-1) '

•  range(0, n-i-1) : 이 부분은 j가 반복을 수행할 값의 범위를 설정합니다. n은 리스트의 길이(요소의 개수)이며, i는 바깥쪽 루프의 현재 반복 횟수입니다.
•  n-i-1  을 사용하는 이유는 매 반복마다 마지막 요소가 정렬되기 때문에, 이미 정렬된 부분은 다시 검사할 필요가 없기 때문이다.
• 즉, 첫 번째 반복에서 가장 큰 값이 맨 뒤로 이동하므로 두 번째 반복부터는 마지막 요소를 확인할 필요가 없습니다

---

📍 삽입 정렬

• 각 숫자를 적절한 위치에 '삽입'함으로써 리스트를 정렬하는 알고리즘입니다.
• 삽입 정렬은 작은 리스트에 대해 효율적이며, 이미 어느 정도 정렬된 리스트에 대해서는 매우 빠릅니다.
  1. 리스트의 두 번째 요소부터 시작하여, 현재 요소가 첫 번째 요소부터 그 자신의 앞에 있는 모든 요소와 비교합니다.
  2. 만약 현재 요소가 비교하는 요소보다 작으면, 비교하는 요소를 오른쪽으로 한 칸 이동시키고, 현재 요소를 비교하는 요소의 왼쪽에 삽입합니다.
  3. 이 과정을 리스트의 마지막 요소까지 반복합니다

# 1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.
# 요구 사항1) 생성된 난수들을 오름 차순 또는 내림 차순으로 정렬하는 알고리즘 구현 
# 요구 사항2) 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현
import random

num_r = random.sample(range(1, 1000), 10)

def insertion_list(lst):
    
    for i in range(1, len(lst)):
        # key는 현재 비교 중인 요소를 나타냅니다.
        key = lst[i]
        # j는 key 바로 앞의 요소를 가리키는 인덱스입니다.
        j = i - 1
        
        # lst[j]는 그 이후의 위치로 이동되고, j는 감소합니다. 
        # 이렇게 함으로써, key가 적절한 위치에 들어갈 수 있는 공간이 만들어집니다.
        while j >= 0 and key < lst[j]:
            lst[j+1] = lst[j]
            j -= 1
        
        # key를 그보다 작은 요소 바로 뒤에 삽입합니다.
        lst[j+1] = key
    return lst

print(f"삽입 정렬: {insertion_list(num_r)}")
print(f"최솟값: {min(insertion_list(num_r))}")
print(f"최값: {max(insertion_list(num_r))}")
>>>
삽입 정렬: [15, 158, 184, 292, 474, 490, 653, 785, 853, 957]
최솟값: 15
최값: 957

---

📍 선택 정렬

• 선택 정렬(selection sort)은 정렬 알고리즘 중 하나로, 이름에서 알 수 있듯이 가장 작거나 큰 요소를 선택해서 원하는 위치로 이동시키는 방법을 사용합니다.
• 일반적으로 가장 간단한 정렬 알고리즘 중 하나로 소개되며, 이해하기 쉽고 코드로 구현하기도 간단합니다.
  1. 리스트에서 가장 작은 값을 찾습니다. 첫 번째 요소부터 시작하여 전체 리스트를 훑어 가장 작은 값을 찾습니다.
  2. 이 가장 작은 값을 리스트의 맨 앞에 있는 값과 교환(swap)합니다. 이로써, 리스트의 첫 번째 위치에는 가장 작은 값이 위치하게 됩니다.
  3. 이제, 리스트의 첫 번째 요소를 제외하고, 나머지 부분을 동일한 방법으로 정렬합니다. 즉, 두 번째 요소부터 시작하여 리스트의 끝까지 가장 작은 값을 찾고, 이를 두 번째 위치의 요소와 교환합니다.
  4. 이 과정을 리스트의 끝에 도달할 때까지 반복합니다.

# 선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로
# 정렬하는 모듈을 만들어보자. 시험 점수는 50부터 100까지로 한다.

import random

score_r = random.sample(range(50, 101), 20)

def selection_lst(lst):
    
    for i in range(len(lst)):
        # min_idx는 i부터 리스트의 끝까지의 요소 중에서 가장 작은 요소의 인덱스를 저장하는 변수
        min_idx = i
        
        # 인덱스 j는 i+1부터 리스트의 끝까지 순회하며, 
        # 이 반복문에서는 i 이후의 요소 중에서 가장 작은 요소를 찾는다.
        for j in range(i+1, len(lst)):
            
            # 만약 j번째 요소가 현재까지 찾은 가장 작은 요소(min_idx)보다 작다면, 
            # min_idx를 j로 업데이트합니다
            if lst[min_idx] > lst[j]:
                min_idx = j
        
        # i번째 요소와 min_idx번째 요소를 교환(swap)합니다
        lst[i], lst[min_idx] = lst[min_idx], lst[i]
        
    return lst

print(f"선택정렬: {selection_lst(score_r)}")
>>>
선택정렬: [50, 53, 54, 55, 56, 60, 61, 64, 66, 72, 73, 74, 76, 77, 83, 84, 85, 95, 96, 100]

---

📍 최댓값

• 원하는 집합을 처음부터 끝까지 훑으며 그 중에서 가장 큰 값을 찾습니다.
• 최댓값을 찾는 내장 함수 max()가 존재합니다. 이를 사용하면 위의 리스트에서 최댓값을 쉽게 찾을 수 있습니다

import random

num_r = random.sample(range(20, 50), 10)

# 함수 정의
def max_lst(lst):
    # 초기 값을 설정합니다.
    max_num = lst[0]
    
    # 더 큰 값이 나타나면 그 값으로 최댓값을 갱신합니다.
    for num in lst:
        if num > max_num:
            max_num = num
            
    return max_num

print(f"list: {num_r}")
print(f"최댓값: {max_lst(num_r)}")
>>>
list: [27, 33, 20, 32, 47, 46, 43, 29, 44, 22]
최댓값: 47

# 리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘을 만들어보자.

class Max_algorithm:
    
    def __init__(self, cs):
        self.chars = cs
        self.max_char = 0
        
    def get_max_char(self):
        
        self.max_char = self.chars[0]
        
        for c in self.chars:
            if ord(self.max_char) < ord(c):
                self.max_char = c
        
        return self.max_char
    
chars = ["c", "x", "Q", "A", "e", "P", "p"]
mc = Max_algorithm(chars)
max_char = mc.get_max_char()
print(f"가장 큰 값은: {max_char}")
>>>
가장 큰 값은: x

---

📍 최솟값

• 원하는 집합을 처음부터 끝까지 훑으며 그 중에서 가장 작은 값을 찾습니다.
• 최솟값을 찾는 내장 함수 min()이 존재합니다. 이를 사용하면 위의 리스트에서 최솟값을 쉽게 찾을 수 있습니다

import random

num_r = random.sample(range(20, 50), 10)

# 함수 정의
def min_lst(lst):
    # 초기 값을 설정합니다.
    min_num = lst[0]
    
    # 더 작은 값이 나타나면 그 값으로 최솟값을 갱신합니다.
    for num in lst:
        if num < min_num:
            min_num = num
            
    return min_num

print(f"list: {num_r}")
print(f"최솟값: {min_lst(num_r)}")
>>>
list: [36, 28, 25, 20, 35, 24, 49, 37, 29, 30]
최솟값: 20

class Min_chars:
    
    def __init__(self, cs):
        self.chars = cs
        self.min_char = 0
     
    def get_min_char(self):
        
        self.min_char = self.chars[0]
        
        for c in self.chars:
            if ord(self.min_char) > ord(c):
                self.min_char = c
                
        return self.min_char
    
chars = ["c", "x", "Q", "A", "e", "P", "p"]
mc = Min_chars(chars)
min_char = mc.get_min_char()
print(f"가장 작은 값은: {min_char}")
>>>
가장 작은 값은: A

---

📍 최빈값

• 최빈값(mode)은 통계학에서 사용하는 용어로, 주어진 데이터 셋에서 가장 자주 등장하는 값을 의미합니다.
  1. 각 값의 등장 횟수를 세어서 기록합니다, 파이썬에서는 이를 위해 dictionary를 사용할 수 있습니다.
  2. 가장 많이 등장한 값, 즉 가장 높은 빈도수를 가진 값을 찾습니다

  def find_mode(lst):
      # 각 요소의 빈도수를 저장할 dic 정의
      count_dict = {}
      
      for num in lst:
          if num in count_dict:
              count_dict[num] += 1
          else:
              count_dict[num] = 1
              
      # max() 함수는 딕셔너리에서 가장 높은 값을 가진 키를 반환합니다. 
      # key=count_dict.get는 max() 함수가 count_dict의 값을 기준으로 최댓값을 찾게끔 설정합니다.
      mode = max(count_dict, key=count_dict.get)
      return mode
  
  numbers = [1, 2, 2, 3, 4]
  print(find_mode(numbers))
  >>>
  2

  # 최빈값 알고리즘을 이용해서 학생 100명의 점수 분포를 다음과 같이 나타내 보자.
  
  scores = [80, 90, 75, 95, 80, 90, 95, 95, 80, 
            95, 80, 75, 80, 90, 95, 80, 95, 95, 
            95, 90, 90, 80, 95, 80, 70, 95, 75, 
            75, 70, 90, 90, 70, 70, 90, 95, 95, 
            80, 75, 100, 95, 85, 80, 75, 90, 70, 
            80, 80, 80, 90, 80, 90, 95, 95, 85, 
            70, 90, 85, 95, 75, 70, 80, 75, 80, 
            80, 90, 85, 95, 90, 90, 75, 80, 70, 
            95, 85, 90, 80, 100, 90, 80, 80, 75, 
            80, 85, 80, 90, 95, 95, 70, 75, 95, 
            80, 80, 75, 95, 80, 70, 100, 75, 80, 80]
  
  freq_dict = {}
  for score in scores:
      if score in freq_dict:
          freq_dict[score] += 1
      else:
          freq_dict[score] = 1
  
  sorted_scores = sorted(freq_dict.items(), key=lambda x: x[1], reverse=True)
  
  for i, item in enumerate(sorted_scores):
      score, freq = item
      print(f"{i+1}. {score}빈도수: {freq} {'+' * freq}")
  >>>
  1. 80빈도수: 28 ++++++++++++++++++++++++++++
  2. 95빈도수: 22 ++++++++++++++++++++++
  3. 90빈도수: 18 ++++++++++++++++++
  4. 75빈도수: 13 +++++++++++++
  5. 70빈도수: 10 ++++++++++
  6. 85빈도수: 6 ++++++
  7. 100빈도수: 3 +++