1장 algorithm efficiency

알고리즘 중간범위

---

알고리즘의 정의, 수학적 귀납법, 알고리즘 효율성의 점근적 분석법 등을 배운다.

그 후 분할정복 divide and conquer, 동적 계획법 dynamic programming, 그리디 방법 greedy approach, 퇴각검색 backtracking, 분지한정 branch and bound 등의 알고리즘 설계 기법을 공부한다.

강의 후반에는 효율적인 알고리즘이 존재하지 않는 문제가 있다는 사실을 배우고 이를 다뤄본다.

---

chap1. algorithm efficiency

algorithm = step by step procedure for solving problem

알고리즘은 input을 받아 output을 내보낸다. - 문제에 따라 형태는 다르다.

왜 알고리즘을 공부하냐?

• practical point of view
  1. 실제 컴퓨터 프로그램은 좋은 자료구조와 알고리즘의 조합이 필요하다.
  2. 새로운 알고리즘으로 새로운 문제 해결 가능
• theoreitical point of view
  1. 분석적 스킬을 기르고 다른 것들을 이해하기 쉽게 도와줌.

알고리즘 공부법 2가지

1.problem based approach - 문제 하나를 두고 알고리즘 공부

장점- 겪어본 같은 문제에 대한 효율적인 알고리즘 선택에 유리

단점- 문제 유형 위주가 되는 단점

2.design based approach - 디자인 패턴 기반으로 공부

장점 - 새로운 알고리즘 문제를 디자인 할 수 있는 역량 증가

ex1) GCD구하기- Euclid알고리즘 (m, n)-> (n, m mod n )→,,,→(x,0) = x - divide and conquer방식

알고리즘은 -수도코드 형식으로 표현될 수 있고 보통 그렇게 표현한 후 구현함.

알고리즘 문제 풀이의 방법(핵심)

1. 문제이해

해당문제가 알고있는 존재하는 문제라면 어느 방식을 적용할지에 대한 고민

새로운 문제라면 새로 디자인해야 함.

1. 결정
   • computational means -instruction이 어느 형태로 실행되냐에 따라서 절차형으로 할 거냐 병렬 알고리즘으로 할거냐 - 컴퓨터 성능은 신경 쓰지 않고 디자인할 것(independent성), 하지만 실용적 애플리케이션을 디자인한다면 속도와 메모리 측면에 신경 써야 함.
   • approximation 방식이냐 정확한 답을 구하는 exact방식이냐
   • approximate 알고리즘은 정확한 답을 내릴 수 없는 문제에 유용하고, exact로 풀기엔 시간이 너무 오래 걸리는 경우에 사용
   • 자료구조는 뭐로 할 거냐 ex) array, stack..
   • 알고리즘 디자인 패턴은 뭐로 하냐 ex) divide and conquer, DP 등
2. 디자인 패턴에 따라 디자인하기
3. 새로운 알고리즘의 정확성 증명
   • 복잡도 분석-efficiency(time complexity), simplicity(분명하고 이해하기 쉽게 구현할 것), generality(같은 유형의 문제에 대해 항상 적용될 수 있어야 함), optimality(다른 알고리즘보다 항상 더 좋아야 함.)
4. 프로그래밍 언어로 작성

기본 자료구조

1. primitive = int, char, boolean…
2. linear data structure배열, 링크드리스트, 스택(프링글스), 큐(줄 서기)
3. non linear data structure 그래프, 트리

알고리즘 efficiency

알고리즘 고려사항 -

1. input output이 sorted냐 아니냐
2. 알고리즘의 속도 time complexity
3. device 스펙에 따라 프로그램 수행 속도가 다르다는 점 주의. - 알고리즘의 시간복잡도를 위한 다른 측정법이 필요하다
   • time efficiency (time complexity) = 알고리즘 수행속도가 얼마냐 빠르냐
   • space efficiency(space complexity) = in, ouput에 대해 메모리를 얼마나 필요로 하느냐

running 시간 분석을 위한 unit(단위)

1. practical or Empirical 알고리즘 분석
   • s, ms단위를 이용하여 프로그램 동작시간을 측정
   • 각각 컴퓨터의 성능에 따라 다르며, 알고리즘 구현정도, 머신코드를 생산하는 컴파일러 성능에 따라 동작시간이 변한다. = 단점
2. Theoritical analysis 알고리즘 분석

• 가장 많이 사용된 연산인 basic operation의 횟수기반
• 컴퓨팅 환경과 독립적인 분석기법
• 문제와 알고리즘 그 자체에 기반.
• basic operation 외의 operation은 배제하는 방식이라 approximate 한 방식임.
• n이 충분히 클 때 효과가 있음. 그렇기에 항상 특정 알고리즘이 더 빠르다는 말은 틀릴 경우가 많은 말임. ex) 100n vs n^2

직관적인(intuitive) complexity 개념 𝛉사용

-상수에 대한 것은 삭제하여

점근 표기법을 사용한 complexity function 비교

1. big oh = less than equal to realation = upper bound방식 ex)

2. big omega= greater than or to relation

3. big theta = equal to realtion

• 이러한 점근 표기법들은 알고리즘끼리의 복잡도 비교를 위해 사용된다. 그래서 간단한 게 최고임.
• 그리고 문제 물어볼 때 c가 뭐고, n(0)이 뭐일 때 성립한다 안 한다로 표기할 것.

점근적 방식이 아니라 lim 방식으로 두 알고리즘의 complexity 비교 가능.

lim f(x)/g(x) 0보다 크냐 상수냐 x값이 있냐에 따라 누가 더 큰지 구분가능.

iterative 알고리즘 수학적 분석 bottom →top형태임. 순차적 실행.

1. n 이 input size임을 명확히 말하고
2. basic operation을 찾은 후
3. input에 따른 worst, average, best case에 대한 complexity계산
4. 막일로 더해가며 basic operation 실행 횟수 계산
   • 4번을 계산하여 simplify

recursive 알고리즘 수학적 분석 top→bottom형태로 실행되고 bottom부터 계산

1. n 이 input size임을 명확히 말하고
2. basic operation을 찾은 후
3. 기본 작업이 실행되는 횟수가 동일한 크기의 입력에 따라 달라질 수 있는지 확인합니다. 가능한 경우 최악의 경우, 평균 및 최상의 경우를 별도로 조사해야 합니다.
4. 기본동작의 실행 횟수를 나타내는 적절한 초기조건으로 반복관계를 설정한다
5. 반복 관계를 해결하라: 함축적 함수를 명시적 함수로 변경한다.
6. simplify =명시적 함수를 단순화하여 복잡도 함수의 클래스를 n으로 구한다.