1.1 알고리즘 개요

1. 알고리즘(Algorithm)의 정의

- 주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한집합

 

2. 자료구조

- 알고리즘의 객체

- 구조화되고 조직화된 자료의 저장/추출/관리 방법

- 추상데이터타입 (Abstracted Data Type)

- 배열, 스택, 큐, 트리 etc...

 

3. 알고리즘의 선택

- 하나의 문제에 대해 여러 알고리즘이 존재

- 절대적인 최상의 알고리즘은 없음

- 주어진 문제와 환경을 먼저 숙지하기

- 속도와 자원(resource)의 상관관계

    -> 속도가 빠를수록 자원을 더 많이 소모한다.(속도와 자원은 비례관계)

    ** 자원 : 메모리, 하드디스크 같은 것을 의미

- 단순한 알고리즘이 best

    -> 지나친 속도 결벽증은 금물(오류 발생 확률 상승)

    -> 알고리즘의 사용 빈도에 따른 선택

 

4. 알고리즘의 예 : 두 정수의 곱셈

- 전통적인 곱셈의 기본연산

    -> 임의의 정수 * 한자리 정수

    -> 두 정수의 더하기

- 기본 연산이라고 하기에는 너무 복잡하다.

    -> 사람에게는 적합하지만, 컴퓨터에게는 어려움

 

4.1 알고리즘의 예 : a la russe

1. 두 정수를 첫번째, 두번째에 쓴다.

2. 첫번째 수가 홀수이면 두번째수를 세번째칸에 기록한다.

3. 첫번째 수를 2로 나누고(나머지 버림), 두번째 수에 2를 곱한다.

4. 첫번째 수가 0보다 크면 2로 돌아간다.

5. 세번째 칸의 수를 모두 더한다.

 

-> 기본 연산

    - 정수를 2로 나눈다.

    - 정수에 2를 곱한다.

    - 두 정수를 더한다.