TIL 8. Python 알고리즘 배우기

오늘은 알고리즘에 대해 배웠다.
백엔드에서 많이 사용할 것 같은 느낌이지만, 알아두면 백엔드와 협업하기에도 좋지 않을까?
언어는 초보자도 쉽게 진행할 수 있는 파이썬으로 진했됐다.

---

알고리즘 맛보기

처음에는 알고리즘과 친해져야 한다며 최대값과 최빈값을 구하는 걸 배웠는데,
JS랑 비슷하면서도 다른 느낌을 지울 수 없었다.

• 최대값 구하기

array = [1, 3, 9, 7, 4, 5]

def f_m_num(array):
    m_num = array[0]
    for num in array:		# num = 1, num = 3, num = 9 ... num = 5
        if num > m_num:
            m_num = num
    return m_num

1. maxnum이라는 빈 배열을 만든다.
2. array의 값을 num에 담아서 하나씩 꺼낸다.
3. 만약 담아서 꺼낸 num이 maxnum보다 크다면, maxnum은 담아서 꺼낸 num이 된다.
   (ex. 1을 꺼냈으면, 처음 maxnum은 0이기 때문에 1이 더 크므로 maxnum은 1이 된다.)
4. 그리고 for문이 다시 돈다. (array의 길이만큼 반복하니까.)
5. 다시 3.을 실행한다.
   (이번엔 3을 꺼내고, 꺼낸 3과 maxnum인 1을 비교하는데,
   if문의 num(3)이 maxnum(1)보다 크니 maxnum은 3이 된다.)
6. 다시 for문이 돈다. 이렇게 계속 반복하면서 마지막까지 비교한다.

• 최빈값 구하기

string = "if my hand is not the one you're meant to hold"

def f_m_occu_alpha(string):
    alpha_arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                      "t", "u", "v", "x", "y", "z"]
    m_occu = 0
    m_alpha = alpha_arr[0]

    for alpha in alpha_arr:		# alpha = "a", alpha = "b", ... alpha = "z"
        occu = 0				
        for char in string:		# char = "i", char = "f", ... char = "d"
            if char == alpha:
                occu += 1

        if occu > m_occu:
            m_alpha = alpha
            m_occu = occu

    return m_alpha
    
print(f_m_occu_alpha(string)) // o

시간복잡도

'입력값'과 '문제를 해결하는 데 걸리는 시간'의 상관관계다.
한 줄의 실행되는 걸 1번 연산한다고 생각하면 된다.
for문을 돌리게 된다면, 입력값의 길이만큼 실행문이 실행된다. (ex. arr = [1, 2, 3, 4]는 4번 연산)
만약 for문 안에 또 다른 for문이 있다면, 총 실행 수는' 입력값의 길이 * 입력값의 길이'일 것이다.
if문 같은 비교 연산처럼 제곱으로 늘어나지 않는 연산의 수는 제외하는 편이다.

let arr = [1, 2, 3, 4]

for (i = 1; i < arr.length; i++) { 		// arr의 길이만큼인 4번 연산
  for (j = 1; j < arr.length; j++) {	// arr의 길이만큼인 4번 연산
   if (조건문) {						   // 비교 연산 1번
   		실행문
   	}
  }
}

arr길이 arr길이 if문 비교연산 1번.
근데, 비교연산 같은 실행은 제외하는 편이니 결국 arr길이^2 -> n^2
시간복잡도는 수식으로 표현해야하기 때문에 N^2와 같이 표현해야한다.

공간복잡도

공간복잡도는 '입력값'과 '입력값이 차지하는 공간'의 상관관계다.
변수, 리스트, 딕셔너리 등이 차지하는 공간당 1이라고 보면 된다.

const a = 100
const arr = [1, 2, 3, 4]
let sum = 0;

a변수 공간하나, arr배열의 공간 네 개, sum변수 공간 하나, 총 6개의 공간을 사용했다.

공간의 경우 입력값으로 인해 기하급수로 늘어나지 않는 편이기에,
적은 차이의 두 공간복잡도가 있을 경우,시간복잡도를 가지고 비교하게 된다.

점근표기법

점근 표기법의 종류에는
빅오(Big-O), 빅 오메가(Big-Ω)가 있다.

빅오 표기법은 최악의 성능이 나올 때의 연산량,
빅오메가 표기법은 최선의 성능이 나올 때의 연산량을 표기한다.

예를 들어
빅오 표기법으로 표시하면 $O(N)$, 빅 오메가 표기법으로 표시하면 $Ω(1)$의
시간복잡도를 가진 알고리즘이다라고 표기할 수 있다.