# [알고리즘] 알고리즘에 대하여 01

2024.12.17 07:57

---

📌 본 포스팅은 파이썬으로 알고리즘을 구현하는 내용을 다룹니다.

1. 점근 표기법.

• 5050 을 구하는데 101 번계산, 50번계산 후자가 더 좋은 알고리즘이다.
• 빅오(Big-O) : 최악의 경우 연산량.
• ex) 배열 내에 특정 숫자가 존재 여부 ->True False 반환

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

def is_number_exit(num,arr):
    return True  if num  in arr else False

is_number_exit(3,arr) # True
is_number_exit(120,arr) # False

☞ 가장 좋을 때는 1번, 가장 나쁠때는 n 번 계산 O(1), O(n)

2.시공간 복잡도

• 알고리즘을 평가하는 법. 걸리는 시간, 설치시 용량이 적을 수록 빠름.
• 시간복잡도 낮음 = 빠름, 공간복잡도 낮음 = 저용량, 현대는 시간복잡도가 더 중요함.
• n^2 인지 n 인지 중요함. n 인지 2n 인지 n+3 인지는 중요하지 않다.

[문제1.] 숫자목록 최빈값과 빈도수 출력

def most_freq(numbers,method = 'O(n^2)'):
    most_freq_num = 0
    max_freq = 0
    if method=='O(n^2)':
        for first_num in numbers:
            freq =0
            for num in numbers:
                if first_num ==num:
                    freq +=1
            if freq >= max_freq:
                max_freq = freq  
                most_freq_num = num     

    else : #O(n)
        num = {}
        for i in numbers:
            # print(i,end=' ')
            if i not in num.keys():
                num[i] = 0
            num[i]+=(1 if  i in num.keys() else 0 )
        print(num)
        max_freq = 0
        for key,item in num.items():
            if item >=max_freq:
                max_freq = item
                most_freq_num =key
    return most_freq_num, max_freq
most_freq([1, 2, 3, 2, 1, 3, 1, 4, 2, 1], method='1')

[문제2.] 문자열 팰린드롬(거꾸로해도 박도박)

def