TIL] 알고리즘 공부

최댓값 구하기

시간 복잡도 ↑ (N제곱)

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


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


result = find_max_num(input)
print(result)

# 프로그램 동작 정리..
# num = 3 < compare_num = 5 break
# num = 5 < compare_num = 6 break
# num = 6

 

시간 복잡도 ↓ (1 + 2N)

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


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(result)

# num = 3 > max_num= 3 // False
# num = 5 > max_num= 3 // True -> max_num = 5
# num = 6 > max_num = 5 // True -> max_num = 6
# num = 1 > max_num = 6 // False
# num = 2 > max_num = 6 // False
# num = 4 > max_num = 6 // False
# max_num = 6

---

소수 구하기

input = 20


def find_prime_list_under_number(number):
    prime_list = []  # 빈 리스트를 만들어 준다.(소수 담을 용도)
    for n in range(2, number + 1):  # 2~20까지 n에 넣어주는 반복문!
        for i in prime_list:
            if n % i == 0 and i * i <= n:  # n 나누기 i 를 했을 때 0이거나 i의 제곱근이 n보다 크거나 같을 때 소수이기 때문에
                break  # 반복문을 멈춰주고
        else:
            prime_list.append(n)  # 빈 리스트에(소수)를 담습니다.
    return prime_list


result = find_prime_list_under_number(input)
print(result)


# 어떻게 프로그램이 작동하는지
# n     i       prime_list              if문
# 2    null        []         빈 리스트이기 때문에 for 문이 실행이 되지않아 2를 리스트에 담습니다!
# 3     [2]        [2]        3 % 2 != 0 // 4 <= 3 -> 4가 3보다 크기 때문에 리스트(3)담습니다!
# 4    [2,3]      [2,3]       4 % 2 == 0 // 4 <= 4 -> if 조건 성립!!
# 5    [2,3]      [2,3]       5 % 2 != 0 // 5 % 3 != 0 -> 5를 리스트(5)담습니다!
# .... 이런식으로 동작합니다....!

---

알고리즘은 코드 블록에 동작 방식을 넣어 놓으면 설명을 하는 것보다 눈에 잘 들어올 것 같아서

코드 블록에 기입했습니다! 이런 방식은 처음이라... 무성의해 보일까 봐 걱정이네요!

우선 오늘 알고리즘에 대해 공부를 하는데 알고리즘은 정말 어려웠습니다.

마지막 소수구하는 문제는 몇 시간을 혼자 생각해보고

(끙끙 앓는건 좋지 않지만 문제를 단지 풀고 넘어가는 게 아닌 이해를 해보고 싶었기에 최대한 생각해보았습니다!)

구글링을 시작하다가 답안을 보고도 이해가 되지않아 몇 시간을 해석했습니다..

제가 정말 많이 부족하다는 것을 알았고 한줄 한 줄 코드를 해석하고 그 후에 이게 어떻게 작동하는지에 대해

알고 싶어 정말 손으로 일일이..ㅜㅜ n과 i의 값을 대입해가며 이해했습니다!

확실히 안되는건 없었습니다. 처음에 문제를 보자마자 이걸 어떻게 풀지 했던 문제를

비록 제가 해결하진 못했지만 답안을 보고도 이해를 못했던 것을 한 줄 한 줄 해석하고

프로그램이 어떻게 작동하는지 손으로 일일히 대입을 해보니 이해가 되었습니다...

오늘은 정말 불가능은 없다는 것을 느꼈습니다.

앞으로도 열심히 알고리즘을 공부해서 좋은 코드를 설계하는 개발자가 되고 싶습니다!!

파이팅👍👍👍✍️✍️✍️