알고리즘 2강

---

알고리즘의 개념

주어진 문제를 풀기위한 명령어들의 단계적 나열

• 입출력
  ✓ 0개 이상의 외부 입력 -> 1개 이상의 출력

• 명확성
  각 명령은 모호하지 않고 단순 명확해야 함

• 유한성
  한정된 수의 단계를 거친 후에는 반드시 종료

• 유효성
  모든 명령은 컴퓨터에서 수행 가능해야 함
  -> 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련 유한개의 명령들을
  순서적으로 개선

알고리즘 생성단계

해당 강의에서는 설계를 중점으로 다루고, 효율성 분석으로 다룬다.

이처럼, 일상적으로 표현되는 언어로 알고리즘을 설명할 수 있고, 일반적으로 사용되는 코드로도 설명할 수 있다.

플로우 차트로도 표현할 수 있다.

---

알고리즘 설계

에를 들어, 25 15 35 60 45 80 55 75라는 수열이 있을 때, 최대값을 찾는 알고리즘을 설계해보자.

1. 값들을 모두 하나씩 비교하여 찾는 방법이 있다.

2. 토너먼트 방식

1번과 2번 중 어떤 것이 더 효율적일까?

효율성을 따지기 위한 기본 조건은, 비교하는 횟수이다. (비교하는 횟수가 많을수록 시간이 오래 걸리기 때문이다.)

숫자 8개가 나열되어있는 수열을 1번과 2번 방법으로 비교해 보았을 때, 둘 모두 7개를 비교했다 (n-1개)

따라서, 1번과 2번은 같은 효율성을 가진다.

카드를 뒤집어 섞어두었다, 이 카드 중에서 K를 찾아보자.

순차탐색 알고리즘을 사용한다, 모든 카드를 다 뒤집어 본 후, 찾고자 하는 카드가 나오면 정답. 그게 아니라면 다음 카드를 뒤집는다.

이진 탐색 알고리즘을 사용한다. 가운데 7을 뒤집어놓고, 왼쪽과 오른쪽을 기준으로 나누어두었다.
이 카드는 순서대로 나열되어 있기 때문에, 왼쪽은 아예 탐색할 필요가 없다.

오른쪽 카드에 남은 3장 중 가운데 카드를 뒤집었더니, J가 나왔다. J는 10보다 크니 오른쪽 카드를 확인할 이유가 없다.

10 카드를 단 3번만에 찾았다.

이 때, 순차탐색과 이진탐색 중 어떤 것이 더 효율적일까? 카드를 3번만에 찾았으니 이진 탐색이 효율적일까?

당연히 아니다, 문제의 조건부터가 다르기 때문이다. 숫자가 순서대로 나열된 카드에서는 당연히 이진 탐색이 유리하다.
애초에 질문부터가 잘못된 문제!

알고리즘 설계 기법

알고리즘 문제들은 문제, 속성, 조건등이 매우 다양하므로, 모든 문제에 범용적으로 적용할 수 있는 기법은 존재하지 않는다.

그러나, 대표적인 알고리즘 기법등이 있는데

• 분할 정복 - 2강
• 동적 프로그래밍 - 3강
• 욕심쟁이(greedy) - 4강

에서 다루게 된다.

---

알고리즘의 분석

정확성 분석

• 유효한 입력 시간, 유한 시간 -> 정확한 결과 생성 여부?
  ✓ 다양한 수학적 기법을 사용해서 이론적인 증명이 필요하다.
  그러나, 교재와 강의에서 다루는 알고리즘은 모두 수학적 증명이 되어있기 때문에 증명이 필요하진 않다.

⭐️⭐️ 효율성 분석

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
  ✓ 메모리 양 - > 공간복잡도
  정적 공간 + 동적 공간
  수행시간 - > ⭐️ 시간 복잡도

대부분 공간 복잡도는 쉽게 계산이 되므로, 시간 복잡도를 주로 따진다.

즉, 효율적인 알고리즘이란 메모리를 적게 사용하고 시간도 가장 적게 걸리는 알고리즘이다.

시간 복잡도

구현한 알고리즘을 컴퓨터에서 실행시켜 실제 수행 시간을 측정하면 될까???

당연히 안 된다.

• 일반성 결여!
  ✓ 컴퓨터 속도, 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등에 의존성

시간복잡도는, 알고리즘의 단위 연산의 수행 횟수의 합이다.

단위 연산들이 몇 번 수행되는지 횟수를 계산하여 다 더해주는 것을 시간 복잡도라고 표현한다.

시간 복잡도에 영향을 끼치는 요인

• 입력 크기(보통 n) : 입력으로 제공되는 데이터 크기, 문제가 해결하려는 대상이 되는 개체
  예 : 행렬의 크기, 리스트 원소의 수, 그래프 정점의 수

입력크기 n이 증가하면, 수행 시간도 증가한다
따라서, 단순히 수행되는 단위 연산의 개수의 합으로 표현하는 것은 부적절하다.

시간복잡도는, 입력 크기(n)에 대한 함수 $f(n)$으로 표현된다.

입력된 데이터의 상태에 따라 종속적이다

• 평균 수행 시간
  당연히 가장 좋겠지만, 입력 데이터의 모든 경우의 수를 다 따질 수 없어 현실적으로 사용할 수 없다.

• 최선 수행 시간
  다른 어떤 경우의 수보다 가장 수행 시간이 짧고, 빠르다.

• 최악 수행 시간
  어떤 문제에 대해 이 알고리즘을 적용했더니, 가장 수행 시간이 길었다.

따라서, 우리는 <최악 수행 시간>을 시간 복잡도로 사용한다. 수행 시간이 어떻게 됐건 최악 수행 시간보단 나빠질 수 없기 때문에,
이를 기준으로 알고리즘의 시간 복잡도를 나타낸다.

이러한 경우가 있다면, 당연히 출근에 걸리는 시간을 74분을 잡고 출근해야 하는 원리이다.

시간 복잡도 구하기

---

점근성능

점근성능이란?

입력 크기 n이 무한대로 커짐에 따라 결정되는 성능

데이터 n이 특정 수 미만일 때는 이 함수가 더 성능이 좋았는데, 특정 수 이상의 값이 들어오면 다른 함수의 성능이 더 좋아진다.

입력 크기 n에 따라 결과에 가장 큰 영향을 미치는 <최고차항> (3번째 예시의 경우 $n^2$이다.)

점근성능의 결정 방법

• 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현한다.
  ✓ 수행 시간의 정확한 값이 아닌 어림값
  -> 수행시간의 증가 추세를 파악하는데에 용이
  -> 알고리즘의 우열 표현이 용이

예) $f(n)=2n^2+3n+200$ 의 경우, 최고차항 $n^2$

점근성능의 표기법

정의 1) 'Big-oh' 점근적 상한

함수 f와 g를 각각 양의 정수를 갖는 함수라 하자.

어떤 양의 상수 c와 $n_0$이 존재하며, 모든 $n>=n_0$에 대하여
$f(n)<c*g(n)$이면 $f(n)=O(g(n))$이다.

직관적으로 이해하기 : $g(n)$의 점근적 상한이(올라갈수록 안 좋은 것) $cg(n)$보다 올라갈 수는 없는 상태.
다시 얘기하면, 내가 구한 알고리즘이 아무리 나빠도 $cg(n)$보다는 나쁘지 않다.
즉, 알고리즘에 있어서 최악의 수행시간을 표현할 때 'Big-oh' 표기법을 사용한다.

정의 2) 'Big-omega' 점근적 하한

함수 $f(n)$ 이 $cg(n)$ 보다는 항상 위에 있다.

즉, 내가 구한 함수 $f(n)$은 아무리 좋아져도 $cg(n)$ 보다는 좋아질 수 없다.

이렇도록, 최선의 수행시간을 나타내는 것을 'Big-omega' 표기법이라고 한다.

정의 3) 'Big-theta' 점근적 상하한

예시에서, 최악의 수행시간 n을 뽑아내고 이를 $O(n)$으로 표기하면 된다.
즉, 최고차항을 뽑아내고 $O(n)$으로 표기하면 끝!

점근성능의 표기법 2

오른쪽으로 갈 수록 시간이 오래 걸린다는 뜻이다, 즉, O(1)이 $O(2^n)$ 보다 효율이 좋다는 것을 의미한다.

---

빅오 함수에 따른 연산 시간의 증가 추세

효율적인 알고리즘의 중요성

어떠한 알고리즘을 개발했는데, $f(n)=2^n$일 경우에는 사용하지 못한다.

이는, 효율적인 알고리즘인 $f(n)=log_n$의 경우 $10^9$ 만큼의 데이터가 들어와도 짧은 시간 안에 해결함을 의미한다.

알고리즘의 시간 복잡도를 구하려면

• 알고리즘의 수행시간 f(n)을 구한 후, f(n) = O(g(n)) 을 만족하는 최소 차수의 함수 g(n)을 찾는다.

실용적인 접근 방법

• 알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도를 취한다.

해당 예시에서, 상수 2를 더하는 부분은 시간에 거의 영향을 미치지 못하기 때문에 제외하고, 최고차항인 n만 고려했을 때

f(n) = 3n+2 = O(n)이 된다.

두 번째 예시에서, 몇 번 수행하느냐는 의미가 없이, 루프가 2번 반복되므로 이 함수의 시간 복잡도는 $O(n^2)$이다.

순환 알고리즘

알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태, 재귀이다. 피신에서 많이 했다.

그렇다면, 이러한 경우에서는 루프를 계속 도니까 시간 복잡도가 무한일까?

아니다. 예시에 나온대로 점화식을 세워 계산하게 된다.

예시에서는 찾고자 하는 값을 알기 위하여, 절반을 나누어 왼쪽 절반, 오른쪽 절반으로 나누어 계속해서 순환하여 찾도록 하였다.

즉, 절반으로 나뉘었으니 데이터의 절반을 모두 서치하는 시간 + 데이터 개수에 상관 없이 일정한 시간이 걸리는 상수 시간O(1)을 통하여 시간 복잡도를 구한다.

점화식의 폐쇄형 구하기

점화식이 나올 때마다 이렇게 푼다는 게 말이 안 되기 떄문에, 기본적으로 많이 사용되는 6개의 점화식이 있다.

이 6개의 식을 모두 기억해야 한다.

⭐️⭐️ (2), (3), (6)의 경우에는 무조건 필수로 기억해야 한다!

---

학습 내용 정리하기

1. 알고리즘의 개념
   1-1 명령의 단계적 나열(입출력, 명확성, 유한성, 유효성) + 효율성

2. 알고리즘의 설계
   2-1 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법

3. 알고리즘의 분석
   3-1 정확성 분석 + 효율성 분석(공간 복잡도, 시간 복잡도)
   3-2 시간 복잡도 = 알고리즘이 수행하는 단위 연산의 계수의 합

4. 점근성능
   4-1 O(계수없는 최고차항), 오메가, 세타

5. 순환알고리즘의 성능
   5-1 기본 점화식과 폐쇄형(이진 탐색, 퀵 정렬, 합병 정렬)