컴퓨팅에서 알고리즘의 역할

알고리즘

컴퓨팅에서 알고리즘의 역할

Ynghan 2023. 3. 27. 10:02

알고리즘이 뭐야?

문제 해결을 위한 잘 정의된 절차.

알고리즘

비공식적으로 알고리즘은 입력을 받아 출력을 생성하는 잘 정의된 계산 절차입니다.
- 입력을 출력으로 변환하는 일련의 계산 단계입니다.
잘 지정된 계산 문제를 해결하기 위한 도구
- 알고리즘은 입력/출력 관계를 달성하기 위한 특정 계산 절차를 설명합니다.

컴퓨팅 알고리즘

계산 문제를 해결하기 위한 잘 정의된 계산 절차 문제

계산 문제 예

1에서 n까지의 정수 합계 계산
S = 1 + 2 + ... + n

알고리즘의 정확성

알고리즘은 모든 입력 인스턴스에 대해 올바른 출력으로 중지되면 올바른 것이라고 합니다.

올바른 알고리즘은 주어진 문제를 해결한다.
잘못된 알고리즘은 전혀 중지되지 않거나 원하는 알고리즘이 아닌 다른 대답으로 중지될 수 있습니다.

어떻게 문제를 해결하나요?

데이터 구조

데이터 구조는 데이터를 저장하고 구성하는 방법입니다. 접근 및 수정을 용이하게 합니다.

효율적인 알고리즘

P - problems
- 다항 시간 내에 효율적으로 풀 수 있는 문제
NP - complete problems
- NP - complete 문제에 효율적인 알고리즘이 존재하는지 여부는 알려져 있지 않다.
- 만약 효율적인 알고리즘이 그들 중 하나에 존재한다면, 효율적인 알고리즘은 그들 모두에 존재한다.
- 몇몇 NP - complete 문제는 우리가 효율적인 알고리즘을 알고 있는 문제와 유사하다.

알고리즘 비교 및 성능

어떤게 더 좋나요?

초등학교 알고리즘
고등학교 알고리즘

알고리즘 성능

실행 시간
공간 소비

정렬에 대한 두 가지 알고리즘

삽입 정렬 필요 c$_1$n$^2$
병합 정렬 필요성 c$_2$n lg n
c1 < c2
100만 개 번호 정렬의 경우
- 1000mips의 고속 컴퓨터에서 최적화된 코드에 의한 삽입 정렬을 수행하려면 2 * 106 * 2 개의 계측기가 필요합니다. / 109 mips = 2000 초
- 10mips의 느린 컴퓨터에서 일반 코드에 의한 병합 정렬에는 50 * 106 lg 106 계측기가 필요합니다. / 107ips = 100초

추가 예제(1) - 탐색

문제 : n개 수로 된 리스트 S에 x라는 수가 있는지 알아내시오. x가 S에 있으면 "예", 없으면 "아니오"로 답하시오.

파라미터 : S, n, x
입력의 예 : S = [ 10, 7, 11, 5, 3, 8 ], n = 6, x = 5
출력의 예 : "예"

알고리즘 : 순차탐색 알고리즘 vs 이진탐색 알고리즘

순차탐색 알고리즘

문제 : 크기가 n인 배열 S에 x가 있는가?

입력(파라미터) : (1) 양수 n, (2) 배열 S[1..n], (3) 키 x
출력 : x가 S의 어디에 있는지의 위치. 만약 없으면 0

알고리즘(자연어) :

x와 같은 아이템을 찾을 때까지 S에 있는 모든 아이템을 차례로 검사.
만일 x와 같은 아이템을 찾으면 S에서 위치를 반환하고, S를 모두 검사하고도 찾지 못하면 0을 반환

알고리즘(슈도코드)

최악의 경우 N번 비교

이진탐색 알고리즘

문제 : 크기가 n인 정렬된 배열 S에 x가 있는가?

입력 : (1) 양수 n, (2) 배열 S[1..n], (3) 키 x
출력 : x가 S의 어디에 있는지의 위치. 만약 없으면 0.

알고리즘(슈도코드)

최악의 경우 log$_2$N + 1번 비교

순차탐색 vs 이진탐색

배열의 크기	순차탐색	이분탐색
n	n	lg n + 1
128	128	8
1,024	1,024	11
1,048,576	1,048,576	21
4,294,967,296	4,294,967,296	33

순차탐색 시간복잡도 분석

단위연산 : 배열의 아이템과 키 x와 비교 연산
- S[location] != x
입력크기 : 배열 안에 있는 아이템의 수 n
최악의 경우 분석
- x가 배열의 마지막 아이템이거나, x가 배열에 없는 경우
- 단위연산이 n번 수행.
- 따라서, WorstCaseTime(n) = n
평균의 경우 분석
- 배열의 아이템이 모두 다르다고 가정.
- 경우 1 : x가 배열 S안에 있는 경우만 고려
  - 1 ≤ k ≤ n 에 대해서 x가 배열의 k번째 있을 확률 = 1/n
  - x가 배열의 k번째에 있다면, 수행하는 단위연산의 횟수 = k
  - 따라서, AverageCaseTime(n) =

평균의 경우 분석
- 경우 2 : x가 배열 S안에 없는 경우도 고려
  - x가 배열 S안에 있을 확률을 p라고 하면,
    - x가 배열의 k번째 있을 확률 = p/n
    - x가 배열에 없을 확률 = 1 - p
  - 따라서, AverageCaseTime(n)

항상 목록에 있다면 p = 1 → A(n) = (n+1)/2,     1/2의 확률로 있다면 p = 1/2 → A(n) = 3n/4 + 1/4

최선의 경우 분석
- x가 S[1]일 때, 입력의 크기에 상관없이 단위연산이 1번만 수행된다.
- 따라서, BestCaseTime(n) = 1
생각해볼 것
- 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석이 가장 정확한가?
- 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석을 사용할 것인가?

피보나치수

피보나찌 수열의 정의

f$_0$ = 0, f$_1$ = 1
f$_n$ = f$_{n-1}$ + f$_{n-2}$ for n ≥ 2
예 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

문제 : N번째 피보나치수 구하기

입력 : 양수 n
출력 : n 번째 피보나치 수
알고리즘

피보나치수열 재귀 알고리즘 분석

피보나치 수 구하기 재귀 알고리즘은 수행속도가 매우 느림.
- 이유 : 같은 피보나찌 수를 중복 계산
  - 예 : fib(5) 계산에 fib(2) 3번 중복계산

T(n) = fib(n)을 계산하기 위하여 fib 함수를 호출하는 횟수
- 즉, 재귀 트리 상의 마디의 개수
- T(0)
- T(1)
- T(n) = T(n-1) + T(n-2) + 1 for n ≥ 2
  > 2 × T(n-2) 왜냐하면 T(n-1) > T(n-2)
  > 2$^2$ × T(n-4) ( == 2 × (2 × T(n-4)))
  > 2$^3$ × T(n-6)
  ...
  > 2$^{n/2}$ × T(0)
  = 2$^{n/2}

기본 데이터 구조

선형 데이터 구조

배열, 연결된 목록, 스택, 대기열
작업 : 검색, 삭제, 삽입
구현 : 정적, 동적

비선형 데이터 구조

그래프
트리 : 사이클 없이 연결된 그래프
- Binary trees : 이진 트리
- log$_2$n ≤ h ≤ n - 1 : n개의 노드가 있는 이진 트리의 높이 hd에 대해
- 그래프 표현 : 인접 목록, 인접 행렬 트리 표현 : 그래프로, 이진 노드

Sets, Bags, Dictionaries

Set : 구별되는 요소의 순서없는 집합
- 운영 : 멤버쉽, 유니온, 교차로
- 표현 : 비트 벡터; 선형 구조
Bag : 순서가 없는 컬렉션, 요소가 반복될 수 있습니다.
Dictionary : 작업 검색, 추가, 삭제가 포함된 Bag

알고리즘 분류

문제 유형별
설계 기법별 : 문제를 해결하기 위한 일반적인 접근법
- 부루트 포스
- 분할 및 정복
- 감소 및 정복
- 전환 및 정복
- 공간 및 시간 트레이드오프
- 동적 프로그래밍
- 탐욕스러운 기술

저작자표시 (새창열림)