algo_lec1

 

 

알고리즘 개념 및 설계 원칙

알고리즘 정의

• 입력을 받아 출력으로 변환하는 일련의 연산 절차
• 조건:
  • Finiteness: 유한한 단계에서 종료
  • Effectiveness: 기본적이고 추적 가능한 연산으로 구성
  • Scalability: 큰 입력값도 처리 가능해야 함

알고리즘 문제 해결 과정

1. 문제 이해 (예제 및 엣지 케이스 고려)
2. 알고리즘 설계 전 고려 사항:
   • 연산 방식 (순차/병렬)
   • 정확해 vs 근사해
   • 자료구조 선정
   • 알고리즘 설계 기법: Divide-and-Conquer, Greedy, DP 등
3. 올바름 증명
   • 모든 입력에 대해 올바른 결과를 반환하는지 설명
4. 효율성 분석
   • 시간 및 공간 복잡도

---

알고리즘 예제

1. 탐색 알고리즘 Search Algorithm

• Linear Search
  • 전체 순차 탐색
  • 시간복잡도: O(n)

def linearsearch(target, pots): 
    for i in range(len(pots)):
        if target == pots[i]:
            return i
    return None

• Binary Search
  • 정렬된 배열에서 반씩 나눠 탐색
  • 시간복잡도: O(log₂n)

def binarysearch(target, pots): 
    start = 0
    end = len(pots) - 1
    while start <= end:
        mid = (start + end) // 2
        if target == pots[mid]:
            return mid
        elif target < pots[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return None

• 실행 시간 예시:
  • n = 1,000,000,000,000 → Linear: 1000초 / Binary: 약 40회 반복 (1초 미만

 

 

2. 피보나치 수열 Fibonacci Numbers

• 수열 정의:
  • F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂
  • F₁₀₀ ≈ 10²¹, 0.694n bits 필요
• Recursive Algorithm 재귀
  • 시간복잡도: O(2ⁿ)
• Iterative Algorithm 반
  • 시간복잡도: O(n)

#Recursive algorithm
def fib1(n):
    if n == 0 or n == 1:
        return n
    return fib1(n-1) + fib1(n-2)

#Iterative algorithm
def fib2(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

 

3. 최대공약수 (GCD-Greatest Common Divisor)

• Trivial algorithm
  
  • a, b 중 작은 수부터 1까지 나눠봄
  • 시간복잡도: O(min(a,b))
• Factorization (소인수 분해 방식)
  • 공통된 소인수의 최소 차수를 곱함
  • 시간복잡도: 매우 비효율적 (NP 문제)
• Euclid 알고리즘
  • 정의: gcd(a, b) = gcd(b, a % b)
  • 시간복잡도: O(log(min(a, b)))
  • 매 반복마다 최소 1비트씩 감소 (a mod b < a/2)

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

• Lemma 증명 요약:
  • b ≤ a/2이면 a mod b = a% b < b ≤ a/2
  • b > a/2이면 a mod b = a % b = a - b < a/2