computer algorithm_01(1)

Lect01. 알고리즘 : 효율성, 분석, 순서

 

prof.이도훈

school of computer science & engineering

pusan national university

개인의 학습 목적의 수업 내용의 정리입니다.

*** 이하는 개인적인 추가내용이므로 혹여, 잘못된 점이 있다면 댓글로 남겨주세요.

 

1. 알고리즘(1)

• 컴퓨터 프로그램 : 특정 작업 (예 : 정렬)을 해결하는 컴퓨터가 이해할 수있는 개별 모듈로 구성되어야합니다.
• 특정 작업을 수행하는 개별 모듈 디자인
• 문제는 우리가 답을 구하기 위한 질문
• 문제 해결 절차
• 세심하게 설계된 단계별 절차
• 입력값을 출력으로 변경하는 일련의 절차(솔루션)

2. 알고리즘(2)

• 문제에는 문장 안에 특정 값이 할당되지 않은 변수가 포함될 수 있습니다.
• 이러한 변수를 문제의 매개 변수라고 합니다.
• 문제는 매개 변수를 포함하므로, 매개 변수에 대한 각 값 할당마다, 하나씩 문제의 클래스를 나타냅니다.
• 매개 변수에 대한 각 특정 값의 할당을 문제의 인스턴스라고 합니다.

*** parameter : 변수의 한 종류. 함수 같은데 인풋값으로 들어가는 데이터를 지칭하기 위한 것. 함수의 정의에 지정되므로 호출 할 때 마다 바뀌지 않음.

*** argument : 전달인자. 실제로 함수 등에 전달 되는 값. 실체 함수가 호출될 때 마다 바뀜.

*** value : 값. 구체적 데이터 값.

*** class : oop에서 특정 객체의 생성을 위한 틀. 상태(멤버변수) + 메서드(함수)로 정의

*** instance : 메모리에 실제 값을 할당받은 클래스 형식을 가진 변수. 클래스를 통해 만들어진 객체.

 

3. 문제란?

• 정의 : 입력 집합과 출력 집합 사이의 매핑/관계
• 문제 사양(specification) :  입력값, 입력 인스턴스에서 출력해야 하는 항목을 구체적으로 지정
• 예시 : 정렬
• 입력 : N수 a1의 순서
• 출력 : 입력순서의 순열(재순열) a1 ≤ a2 ≤ … ≤ an 

 

4. 문제

• 문제 : 우리가 답을 찾고자하는 문제
• 파라미터 : 변수. 문제의 특정한 값이 할당 되지 않은 변수
• 문제의 인스턴스 : 문제에서 input에 해당. 파라미터에 구체적인 값이 할당된 것.
• 인스턴스의 솔루션 : output에 해당. 해당 인스턴스에서 문제에 의해 질문된 것에 대한 결과

 

5. 문제 예시( 탐색 )

• x 라는 숫자가 n개의 수를 가진 리스트 s에 있는지 결정. 있다면 yes, 없다면 not 출력.
• 파라미터 : s, n, x >> 문제에 따라서 바뀔 수 있음
• 인스턴스의 예시 : s = [10, 7, 11, 5, 3, 8], n = 6, x = 5 >> 문제가 구체화되며 정해짐. input
• 인스턴스의 솔루션 : yes >> output

 

6. 알고리즘의 표현

• 알고리즘 표현의 방식 
  • 프로그래밍 언어로 된 코드
  • 수도코드 >> 의사코드, 프로그램 언어 + 사람 말. 코드로 구현되기 전
  • 사람 언어, 말로 풀어 쓴 경우
• 명확하고 이해하기 쉬운 증명으로
• 반드시 구체적인 언어로 표현 할 필요는 없지만 알고리즘이나 증명을 명확히 알 수 있게 해야함.

 

7. 알고리즘에서 요구되는 속성

• 정확성 : 룰에 따른 정해진 입력 제시시 올바른 출력을 제공해야한다.
• 효율성 : 주어진 입력의 정확한 출력을 빠른 속도로 해야한다. >> 시간, 메모리 등 자원의 효율적인 사용 필요

 

8. 정확성

• 예시 : TSP(Traveling Salesperson Problem)
• input : 각 도시 사이의 거리가 d 인 일련의 도시들 n 개
• output : 도시 c1,...cn의 순서로 각 도시를 방문하고 돌아왔을 때, d 경로를 최소화 화는 순서.

• 둘 중 적합한 알고리즘은?
  • 1 ) greedy. 가장 가까운 도시부터. 도착한 도시에서 다시 가장가까운 도시로.
  • 2 ) 총 길이를 다 구해서 가장 적은 순서를 시도. 
  • >> 정확성의 경우 2

 

9. 효율성

• 예시 : 홀수 문제
• input : 임의의 숫자 a
• output : a가 홀수면 y, 짝수면 n
• 넷 중 적합한 알고리즘은?
  • 1 ) 1에서 a까지 홀, 짝을 번갈아 명명하여 결정
  • 2 ) 인수분해해서 숫자의 인수가 2개인지 확인
  • 3 ) 0부터 최대 정수 까지 모든 숫자의 룩업 테이블(1은 홀수, 2는 짝수 와 같은 표를 미리 작성 해 놓음)을 유지함
  • 4 ) 숫자의 마지막 수 혹은 비트를 확인

 

10. 순차(sequential) 검색 vs 이진(binary) 검색

>> 항상 최선의 방법은 없음. 원소의 개수가 작다면, 비교적 간단한 순차 검색이 더 효율적일 수 있다.

• 순차 검색은 원소 x를 n개의 원소를 가진 배열에서 x를 찾기 위해 맨 앞부터, 즉 n 번 비교를 한다. x가 배열에 없으면 비교는 n 보다 크지 않다. >> 복잡도 O(n)
• 이진 검색은 정렬된 목록에서 요소의 위치를 찾기 위한 알고리즘. 검사해야 하는 원소의 수가 매번 두 개씩 줄어듦. >> 오름차순으로 정렬이 선행 되어야 함. 배열의 가운데 값을 보고 찾아야 할 수와 비교, 찾고자 하는 x보다 작으면 찾고자 하는 값은 중간 값의 오른쪽에 있음. 왼쪽은 날려도 된다. 크다면 왼쪽에 있으니 오른쪽을 날리는 방식으로 줄어듦. 복잡도 O(logN)

 

11. 피보나치 수열

• 정의 : 첫째, 둘째 항은 1 그 뒤의 모든 항은 바로 앞 두항의 합인 수열. 

피보나치 수열의 기본정의

• 동적 계획법(dynamic programming)

Figure 1.2: The recursion tree corresponding to Algorithm 1.6 when computing the fifth Fibonacci term.

• 5번까지 가기 위해 3번과 4번을 찾아야하고 각 3번은 1과 2를 더하고, 2를 찾기위해 1과 0을 더해야한다. 이 알고리즘(재귀)에는 중복하여 등장하는 계산이 많다는 단점이 있다. 때문에 시간복잡도가 O(2^n/2)으로 가장 비효율적인 방법.

시간복잡도 계산

• T(n) = T(n-1) + T(n-2) + 1 에서 1은 각 이전 두 항으로 쪼개기 위한 상수. constant. T(n-1)은 T(n-2)보다 항상 크기 때문에 T(n-1) + T(n-2) > T(n-2) + T(n-2)가 된다. 이걸 2*T(n-2)로 두고, T(n-2)를 점화식으로 반복을 하면 T(n-3)>T(n-4) 이런식으로 내려가면 2가 총 n/2번 나오게 된다.

 

12. 알고리즘의 분석

• 주어진 input의 사이즈가 커질 때, 걸리는시간이 얼만큼 효율적으로 증가하는가를 측정.
• 중요한 리소스는 '실행시간'. 프로그램이 돌아가는데 필요한 공간(메모리) 같은 요소도 측정되어야함. >> 단, 요즘 공간복잡도는 크게 중요치않음, hw의 비약적인 발전 때문.
• 주어진 알고리즘에의해 사용되는 리소스의 양을 결정하는 '프로세스'
• 알고리즘의 비교에서 능력에 대한 정량적 평가를 원함.
• 알고리즘을 직접 실행해 보지 않고 평가하고자함.

 

13. 복잡도 분석

• 실행환경, 사용 언어, 개발자 등의 모든 세부사항과 별개의 척도.
• 알고리즘의 실행시간은 input의 사이즈에 따라 증가. 총 실행 시간은 수행된 횟수에 비례
• 입력값의 크기가 증가함에 따라 연산 횟수가 얼마나 증가하는지를 측정함이 효율성 분석. >> 시간 복잡도
• 알고리즘이 메모리를 얼마나 효율적으로 사용하는지 분석

 

14. 복잡도의 측정

• 함수를 알고리즘을 실행했을때 시간은 n크기의 입력을 해결하는데 필요한 단계의 수로 정의.
• 식의 차수를 중요하게 봄.