알고리즘 공부-1 (기초 이론)

오늘은 C++ 자료구조를 배우기위해서 먼저 알고리즘에 대한 기초 내용을 공부해보았습니다.

아래는 오늘 공부한 내용을 요약한 노트입니다. (저 자신이 기억력이 낮은 걸 잘 알아서, 글을 남기지 않으면 또 까먹어요….)

말 그대로 저 혼자 공부한 내용을 끄적인거라, 잘 정리가 안된 포스팅입니다. 양해부탁드립니다.

개념 노트

알고리즘 : 주어진 문제를 해결하기 위한 정의된 유한 집합입니다.

자료구조 : 알고리즘의 겍체. 구조화되고, 조직화된 자료의 저장/추출/관리 방법이며 추상적입니다. 배열, 스택, 큐 등이 존재합니다.

연속과 비연속적인 데이터 구조를 나누면 다음과 같습니다.

연속 : 배열, 스택, 큐

비연속 : 트리

알고리즘 선택하려면, 한 문제를 해결할 때 속도와 자원을 고려해야합니다.

예를 들면,

지갑에 돈이 없을때 택시를 타고가는 것보다 지하철을 타는 것이 좋다.

와 같이 속도와 자원을 고려해야 됩니다.

또한 알고리즘은 단순하면 단순할수록 좋습니다.

알고리즘 기초

  • 정수 곱셈
45 * 37 = 45(30+7)=(45*30)+(45*7)=315+1350=1665

위와 같은 식은 사람이 작성하면 좋지만, 기계가 작성하기에는 좀 나쁩니다.

  • a la russe 알고리즘
  1. 두 정수를 (0,0) (0,1)에 쓴다
  2. 첫번째 수가 홀수면 두번째 수를 (0,2)에 쓴다
  3. (0,0)는 나머지 버리며 나누고, (0,1)는 곱한다
45  37      37
22  74
11  148     148
5   296     296
2   596
1   1184    1184
답:          1665

위와 같은 알고리즘으로 구현하면 기계가 이해하기 편합니다.

알고리즘 예시

void algorithm(int a[], int n){
    for (int i = 0; i < n; i++){
        // c1
        for (int j = 0; j < i; j++){
            // c2
        }
    }
}

T(n) = c1 + (c1+c2)+(c1+c2*2)+(c1+c2*3)+...+(c1+c2*(n-1))

성능 : O(N^2)

알고리즘 성능 표기법

(Big-Oh) : O 표기법

T(N) = O(f(N))

(가장 영향력있는 항이 선택됨)

유클리드 알고리즘

  1. 임의 정수 U,V v가 더 크면 u로 바꾼다

  2. u에 v를 뺀다

  3. u가 0이면 v가 최대 공약수, 0이 아니면 1번으로 돌아간다

    280 30
250 30
220 30
190 30
160 30
130 30
100 30
70  30
40  30
10  30
30  10
20  10
10  10
0   10
=10

개선해보기

위처럼 하면 많은 뺄셈을 요구합니다.

결국 뺄셈 값은 나눗셈의 나머지이므로 아래처럼 바꿔도 됩니다.

  1. 임의 정수 U,V를 v가 0이 아니면, u를 v로 나누어준다

  2. u와 v를 교환한다

  3. 다시 1번으로 돌아간다

  4. v가 o이면 u가 값이다

30  280
280 30
10  30
30  10
0   10
10  0
=10

(재귀함수로 작성시 더 간단히 작성 가능합니다.)

소수 판별 알고리즘

소수 : 1과 자기자신 외에 나누어 떨어지는 정수가 없는 양의 정수

차례대로 나누어보면 O(N)이고, 루트N까지 정수로 나누어 보면 O(N^0.5)입니다.

에라토스테네스의 체

주어진 정수보다 작은 모든 소수 구하는 알고리즘입니다.

위키피디아 참고

Written on January 2, 2018