240110 WED 알고리즘 특강 3/3 알고리즘

 

 

1️⃣ 그리디 (Greedy)

매순간 가장 좋아보이는 것을 선택하여 문제를 풀어가는 방법

 

백준 > 5585 거스름돈

5585번: 거스름돈

 

 

 

2️⃣ 완전 탐색 (Brute Force)

모든 경우의 수에 대해서 탐색

단순하지만, 시간복잡도 높아질 가능성 ⬆️

 

 

 

3️⃣ 이진 탐색 (Binary Search)

탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

O(logN)의 시간복잡도

 

 

 

 

4️⃣ 재귀 (Recursive)

문제의 범위보다 약간 좁은 하위 문제를 해결 - 반복하는 방법 like 팩토리얼

 

 

# 팩토리얼 - 반복문 사용
def factorial(n):
    num = 1
    for i in range(1, n + 1):
        num = num * i
    return num


#팩토리얼 - 재귀
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n - 1)

실행 결과

 

 

 

5️⃣ 참고 자료

Chan-Su Shin

 

[글또] 네? 데분 멘토링왔는데 알고리즘 2달 알려주라고요?

 

 

 

6️⃣ 관련 포스트

240108 MON 알고리즘 특강 1/3 자료구조 (1)

240109 TUE 알고리즘 특강 2/3 자료구조 (2)

241010 WED 알고리즘 특강 3/3 알고리즘