[Algorithms/알고리즘] 알고리즘이란?

An algorithm is

Any well-defined computational procedure that 

- takes some value, or set of values, as input

- procedures some value, or set of values, as output

 

A tool for solving a well-specified computational problem

- Problem statement specifies the desired input/output relation

- Algorithm describes a procedure for achieving such a relation

 

 

Data structures

- Choice of appropriate data structure is a crucial issue.

- Important to know strengths and limitations of a variety of data structures.

 

 

How to develop an algorithm

(1) Understanding the problem

- Precisely define the problem

- Precisely specify the input and output

- Construct the simplest possbile representative example for the problem

- Consider all cases

 

(2) Come up with a simple plan to solve the problem at hand

- The plan is language independent

- The precise problem specification influences the plan

 

(3) Turn the plan into an implementation

- The problem representation (data structure) influences the implementation

 

 

Pseudo Code

- Similar in many respects to C, Jave, Python

- Provides means to convey the essence of an algorithm in a concise fashion

- No fixed format for pseudocode. OK as long as it is unambiguous and breaks down the problem to relevant basic steps.

 

 

Example of Algorithm

- Input: sequence of numbers A=[a1, a2, ... an] and value v

- Output: index i such that v==A[i] or NIL if v does not appear in A

- Algorithm

LinSearch1(A,v)
	p = NIL;
	for i=1 to n do
		if A[i]==v then p=i;
	return p;
    
LinSearch2(A,v)
	i=1;
	while i<=n && A[i]<>v do i++;
		if i<=n
			then return i;
		else return NIL;

 

생각할 문제

1. 첫 번째는 일치하는 요소 중 가장 마지막 값을, 두 번째는 가장 첫 번째 값을 결과값으로 가진다. 이는 ambiguous problem statement 때문. first or last index?

2. 일반적으로 LinSearch2가 LinSearch1보다 더 효율적이다. 후자는 항상 전체를 스캔하기 때문이다.

3. There is always more than one solution to a given problem.

 

 

연습문제

Write a program that determines all prime numbers between 0 and n.

Hint) Implement the sieve of Eratosthenes.

에라토스테네스의 체
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2는 소수이므로 결과값 리스트에 2를 쓴다. 자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 결과값 리스트에 3을 쓴다. 자기 자신을 제외한 3의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
이때, 체 역할을 할 소수는 전체수 n의 제곱근보다 작으면 된다.

#include <stdio.h>

void find_primeNumber(int maxNumber) {
    bool arr[maxNumber+1];
    arr[0] = true;
    arr[1] = true;

    // 2부터 해당 숫자의 배수를 지워나간다
    for(int i=2; i<=maxNumber; i++) {
        if(arr[i]) continue; // 이미 지워진 수라면 건너뛴다
        // 이미 지워진 게 아니라면 해당 숫자의 배수를 모두 true로 만든다
        for(int j=2*i; j<=maxNumber; j+=i) {
            arr[j] = true;
        }
    }
 
    for(int i=2; i<=maxNumber; i++) {
        if(!arr[i]) printf("%d ", i);
    }
}

int main(void) {
    find_primeNumber(100); //100까지의 숫자 중 소수 출력 
    return 0;
}

 

단어장
symmetric: 대칭의