220919 TIL

✅주말을 이용해 파이썬 복습을 최대한 끝내보았다. 그리고 오늘부터 알고리즘 강의를 듣기 시작했는데, 역시 문제가 주어졌을 때 스스로 풀어나가는 연습은 더더더 많이 해야할것 같다!

 

✅ 알고리즘 1주차 ✅

📍알고리즘이란?

어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임

 

 

☑️ 최빈값 찾기

Q: 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오.

"hello my name is sparta"

🔑 각 알파벳의 빈도수를 alphabet_occurrence_list 라는 변수에 저장합니다. 그리고 각 문자열을 돌면서 해당 문자가 알파벳인지 확인하고, 알파벳을 인덱스 화 시켜 각 알파벳의 빈도수를 업데이트 합니다. 이후, 알파벳의 빈도수가 가장 높은 인덱스를 찾습니다.

 

🔑  여기까지 했으면, 가장 높은 빈도수의 인덱스를 알아냈습니다. 그러면 이 문제에서는 max_alphabet_index 가 0 입니다. 그러면, 이번에는 인덱스를 문자로 변경하려면 어떻게 할까요? 그 반대로, "아스키 코드 번호"를 "실제 문자"로 변환하려면 chr() 함수를 사용합니다.

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index
            
    return chr(max_alphabet_index + ord('a'))
    
    ```python
def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))

result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

👩🏻‍💻 최댓값,최솟값 찾는 알고리즘은 많이 나와서 자주 해봤는데, 최빈값 찾는 알고리즘은 생소했다...!

며칠전에 과제할 때 isdigit()이라는 함수가 필요해서 알게 되었는데 isalpha() 사용하는 게 나와서 다시한번 정리했다.

 - isalpha() : 문자인지 확인하는 함수. True 이면 문자! False 이면 문자가 아님!

 - isdigit() : 숫자인지 확인하는 함수. True 이면 숫자! False 이면 숫자가 아님!

 - ord() : 문자를 아스키 코드로 변환하는 함수.

 - chr() : 아스키 코드를 문자로 변환하는 함수.

---

☑️ 시간 복잡도

 - 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계.

📌 최댓값 찾기 문제 : 이 배열 내에서 가장 큰 수를 반환하시오. [3, 5, 6, 1, 2, 4]

 - 첫번째 방법

input = [3, 5, 6, 1, 2, 4]


def find_max_num(array):
    for num in array:               # array 의 길이만큼 아래 연산이 실행
    	for compare_num in array:  			# array 의 길이만큼 아래 연산이 실행
        	if num < compare_num:  			# 비교 연산 1번 실행
                break
        else:
            return num


result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

=> 각 줄이 실행되는 걸 1번의 연산이 된다 라고 간주.

  array의 길이 X array의 길이 X 비교 연산 1번     :      N X N  

 

 - 두번째 방법

def find_max_num(array):
    max_num = array[0]			# 연산 1번 실행        
	for num in array:           # array 의 길이만큼 아래 연산이 실행
        if num > max_num:       # 비교 연산 1번 실행
            max_num = num       # 대입 연산 1번 실행
    return max_num

result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

 

=> max_num 대입 연산 1번 -> array의 길이 X(비교 연산 1번 + 대입 연산 1번) : 2N + 1

 

👩🏻‍💻즉, 2N+1의 연산량이 나온 첫번째 풀이 방법은 N 만큼의 연산량이 필요하다. N^2 의 연산량이 나온 두번째 풀이 방법은 N^2 만큼의 연산량이 필요하다. 참고로, 만약 상수의 연산량이 필요하다면, 1 만큼의 연산량이 필요하다고 말하면 됨. 

---

☑️ 공간 복잡도

 

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말함. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것 -> 저장하는 데이터의 양이 1개의 공간을 사용한다고 간주하고 계산.

📌 대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않는다. 따라서 공간 복잡도보다는 시간 복잡도가 더 중요!!

---

☑️ 점근 표기법

 

알고리즘의 성능을 수학적으로 표기하는 방법. -> 효율성 평가. 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 

 - 빅오(Big-O)표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지.

 - 빅 오메가(Big-Ω) 표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지.

✔️알고리즘의 성능은 항상 동일한 게 아니라 입력값에 따라서 달라질 수 있다. 어떤 값을 가지고 있는지, 어떤 패턴을 이루는 데이터인지에 따라서 뭐가 좋은 알고리즘인지 달라질 수 있다는 의미!

❗️알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석한다. -> 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문.

---

☑️Q1. 소수 나열하기 : 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. 

 

🔑주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다. 이를 이용해서 i * i ≤ n 일 때까지만 비교!

input = 20


def find_prime_list_under_number(number):
    prime_list = []

    for n in range(2, number + 1):
        for i in prime_list:
            if n % i == 0 and i * i <= n:
                break
        else:
            prime_list.append(n)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

# [2, 3, 5, 7, 11, 13, 17, 19]