[알고리즘] 개념

Study/Algorithm

[알고리즘] 개념

김성인 2023. 12. 4. 22:19

[알고리즘] 개념

알고리즘을 공부하고, 이해하며 잊지 않도록 이것저것 기록

1. 알고리즘 개요

2. 알고리즘의 분석

3. 유클리드 알고리즘

4. 소수 알고리즘

알고리즘 개요

알고리즘?

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

유한 집합 : 집합의 원소 개수가 한정되어 원소의 개수가 무한개가 아닌 집합
그렇다면 문제를 해결하기 위해서 중요한 것은 무엇인가?
- 문제를 잘 이해하는 것으로부터 출발한다.
- 이것은 컴퓨터 그래픽스에서도 마찬가지이다. 비단 문제가 아니더라도, 어떤 비주얼을 얻기 위해서는 특징이 무엇인지, 최종 결과물, 내가 목표로 하는 것이 무엇인지 잘 아는 것부터 시작이다.

하나의 문제에는 여러 알고리즘이 존재한다.

절대적인 최상의 알고리즘은 없다.
- 조건, 상황에 따라 효율적이고 적합한 방법이 존재한다.
- 최적화나 문제 해결에 있어서, 기능 개발에 있어서 가성비를 따지게 되는데, 개발 스펙, 타깃 디바이스 등에서 선택하는 것들이 달라지는 것과 같은 이치인 것 같다.
- 예를 들어서 내가 출근을 한다고 가정하자.
  - 새벽 5시이다. 이 경우 버스를 타고 가면 차가 막히지 않기 때문에 빨리 갈 수 있다.
  - 오전 9시이다. 이 경우 버스를 타고 가면 차가 막히기 때문에 느리게 간다. 그렇기 때문에 지하철을 이용한다.
- 위와 같이 조건 중 시간만으로도 2가지 이상의 방법 중, 효율적인 방법을 찾을 수 있다.

단순한알고리즘이 좋다.

지나친 속도 결벽증은 금물
- 개발 프로세스 시작부터 성능을 너무 중요하게 생각하면 시각적으로 매력적인 요소를 만드는 것이 어려울 수 있다. 성능에 대한 이러한 강조는 스트레스를 가중시켜 전반적인 개발의 진전을 어렵게 만들 수 있다.
알고리즘의 사용빈도에 따른 선택 등이 존재한다.
- 얼마나 자주 사용하는가?
- 예를 들어서 1초에 100만법 계산을 한다면 당연히 빠른 알고리즘이 좋을 수 있다.
- 빠르지만 메모리 등을 많이 잡아먹게 되면 상황에 따라서 문제가 될 수 있다.
- 최적화 작업을 할 때, 언제나 가장 먼저 되는 것은 병목현상을 찾는 것이다. 병목이 파악되었으면 부하가 걸리는 곳에서 여유로운 곳으로 넘기는 작업을 진행하기도 한다.
- 예를 하나 들면 데이터 하나를 CPU와 GPU의 메모리에 오고 가면 연산을 하는 것보다, 양쪽의 메모리에 올려 두고 연산을 진행하는 것이 메모리적으로는 손해지만, 연산속도로는 더 빠르다.

자료구조?

구조화되고, 조직화된 자료의 저장, 추출, 관리 방법의 총집합

추상 데이터 타입(추상 자료형). Abstructed Data Type > ADT
- 구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 자료구조의 특성들과 어떤 명령들이 있는지를 설명하는 자료구조의 한가지 형태. 즉, 일종의 '규칙'들의 나열이라고 쉽게 이해할 수 있다.
배열, 스택, 큐, 트리
- 배열 : 연관된 데이터를 모아서 관리하기 위해서 사용되는 데이터 타입
- 스택 : 쌓아 올린다는 것을 의미하는데, 최상위(제일 마지막에 들어온)의 데이터를 먼저 처리하는 방식이다.
- 큐 : 선입선출, 먼저 들어온 데이터가 먼저 나간다.
- 트리 : 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조
자료구조는 알고리즘의 구성 요소인 것 같다.

알고리즘의 예

두 정수의 곱셈
- 전통적인 곱셈의 기본연산
- 임의의 정수 * 한자리 정수 > 두 정수를 더하기
- 45 * 37이라고 하면, 45 * 30 + 45 * 7 = 1665인데 이것은 사람에게 적합하지만, 컴퓨터에게는 어려운 알고리즘이다.
- a la russe : 두 정수의 곱셈을 하기 위한 알고리즘
  - 두 정수를 첫 번째 열과 두 번째 열에 각각 씁니다.
  - 첫 열에 숫자를 2로 나누고 몫을 두 번째 행의 첫 열에 쓰고
  - 두 번째 열에 있는 숫자를 2를 곱하여 만약 첫 열의 숫자가 홀수라면
  - 세 번재 열에 2를 곱한 수를 써줍니다.
  - 이렇게 첫 열 숫자가 1이 될 때까지 반복하여 세 번째 열에 있는 숫자를 전부 더해줍니다.

45	37	37
22	74	-
11	148	148
5	296	296
2	592	-
1	1184	1184
		1665

- - 기본연산
    - 정수를 2로 나눈다.
    - 정수에 2를 곱한다.
    - 두 정수를 더한다.
- 쉬프트 연산
  - a << 1 // 2를 곱함.
  - a >> 1 // 2로 나눔.
    - 0110 << 1 // 이런 식이면 0110은 6인데, 1100이 되며 12가 된다.
    - 0110 >> 1 // 이런 식이면 0110은 6, 0011은 3이 된다.

a la russe algorithm(러시아 농부 알고리즘) : https://dlwjdcks5343.tistory.com/40

알고리즘 분석

경험적 분석 / 수학적 분석

분석은 왜 하는가?
- 알고리즘의 종류가 많기 때문에 정확히 선택하기 위한 방법
- 시간 소요량(문제 해결에 소요되는 시간) vs 공간 소요량(메모리)
  - 현재는 공간에 대한 소요량보다 시간 소요량을 중요시한다.
  - 메모리의 가격이 떨어졌기 때문에...
경험적 분석 (Empirical Analysis)
- 실제 코드를 작성 후, 실행하여 시간을 측정
- 데이터 수를 다르게 하여 함수관계 유추
수학적 분석 (Mathematical Analysis)
- 알고리즘 자체를 가지고 수학적인 분석을 함.

최악의 경우 / 최선의 경우

최악의 경우 (Worst case)
- 가장 많은 시간과 자원을 필요로 하는 경우
- 이 경우는 흔하게 일어 나지 않는다.
최선의 경우 (Best case)
- 가장 적은 시간과 자원만이 소요되는 경우
평균적 경우 (Average case)
- 개념이 모호함.
- 자료의 균일분포? 가장 많은 빈도의 경우?

알고리즘 유형

1 (상수)
- 입력자료수와 관계없이 일정한 실행 시간
- 해쉬 검색 알고리즘 등
log N
- Divide & Conquer 방법 사용시
- 이진검색, 이진트리 검색
N
- Scan 방법 사용시
- 선형검색 : https://andrew0409.tistory.com/143
N log N
- Divide & Conquer & Merge 방법 사용시
- 병합정렬(merge sort) : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
N2
- 이중루프
- 삽입정렬, 선택정렬
N3
- 삼중루프

알고리즘 성능 표기법

Big - Oh : https://noahlogs.tistory.com/27
오메가 표기법
세타 표기법...
- https://detail-from-a-to-z.tistory.com/7
- 한번씩 읽어 보면 좋을 것 같다.

유클리드 알고리즘

최대공약수(Great Common Divisor) 찾기

2개의 자연수, 또는 정식의 최대공약수를 찾는 알고리즘
- 자연수 : 0을 포함하지 않는 1로 시작하고 무한정 확장되는 양의 정수 집합
- 정식 : 문자에 대하여 덧셈, 뺄셈, 곱셈만의 연산을 사용하여 얻어지는 대수식, 나누는 일이 없는 유리식
- 약수 : 어떤 수나 식을 나누어 나머지가 없이 떨어지는 수나 식
예를 들어서 280, 30의 GCD는 10이다.
- 280의 약수 : 1, 2, 4, 7, 8, 10, 14, 20, 28, 40, 56, 70, 140, 280
- 30의 약수 : 1, 2, 3, 5, 6, 10, 15, 30
소인수분해를 통해 GCD를 구할 수 있다.
- 소인수분해의 경우 직관에 의존하는 방법으로 컴퓨터에게는 어렵기 때문에 부적절하다.

임의의 두 정수 u, v에 대해
- v가 u보다 크면 v와 u의 값을 바꾼다.
- u = u - v
- u가 0이면 v가 최대공약수, 0이 아니면 다시 위로 돌아 간다.
- 여기서 u = u - v를 반복하게 되는것이 비효율적이다.

int get_gcd(int u, int v)
{
	int t;
	while (u > 0) 
	{
		if (u < v) // v 가 u 보다 크면...
		{
			t = u; u = v; v = t; // u와 v의 값을 바꾼다.
		}
		u = u - v;
	}
	return v;
}

유클리드 알고리즘의 개선

뺄셈 기반 알고리즘의 문제

u, v의 값 차이가 클 때 많은 뺄셈을 요구한다.
뺄셈의 결과는 나눗셈의 나머지를 구하는 것이 포인트
이 포인트를 착안하여 반복해서 뺄셈을 하는 부분을 점프 한다.

임의의 두 정수 u, v에 대해

v가 0이 아니면...
- u = u % v
- u와 v 교환 // u를 v로 나누면, 나머지의 값은 무조건 v가 u보다 크기 때문에 교환
- 위로 돌아감
v가 0이면 u가 GCD

#include <stdio.h>

int get_gcd(int u, int v)
{
	int t;
	while (u > 0) 
	{
		if (u < v) // v 가 u 보다 크면...
		{
			t = u; u = v; v = t; // u와 v의 값을 바꾼다.
		}
		u = u - v;
	}
	return v;
}

int gcd_modulus(int u, int v)
{
	int t;
	while (v > 0)
	{
		t = u % v;
		u = v;
		v = t;
	}
	return u;
}

int gcd_recursion(int u, int v)
{
	if (v == 0)
	{
		return u;
	}
	else
	{
		return gcd_recursion(v, u % v);
	}
}

void main(void)
{
	int u, v;
	int gcd;

	u = 280;
	v = 30;

	printf("get_gcd result : ");
	gcd = get_gcd(u, v);
	printf("%d\n", gcd);

	printf("gcd_modulus result : ");
	gcd = gcd_modulus(u, v);
	printf("%d\n", gcd);

	printf("gcd_recursion result : ");
	gcd = gcd_recursion(u, v);
	printf("%d\n", gcd);
}

소수 알고리즘

소수(Prime Number) ?

1과 자기자신 외에는 나누어 떨어지는 정수가 없는 양의 정수
1은 소수가 아니다.
2, 3, 5, 7, 11, 13, 17, 19...

소수 판별법

소수를 판별하고자 하는 정수 N에 대해...
- 2 ~ N-1 까지의 정수로 나누어 보는 방법 - O(N)

int is_prime(int n)
{
	int i;
	for (i = 2; i < n; i++)
	{
		if (n % i == 0)
		{
			return false;
		}
	}
	return true;
}

2 ~ sqrt(N)까지의 정수로 나누어 보는 방법 - O(N^0.5)

int is_prime2(int n)
{
	int i, sqrn;
	sqrn = (int)sqrt(n);
	for (i = 2; i <= sqrn; i++)
	{
		if (n % i == 0)
		{
			return false;
		}
	}
	return true;
}

O(N), O(N^0.5) : Big O 표기법
- 컴퓨터 과학에서 알고리즘 시간 복잡도의 상한 또는 최악의 시나리오를 설명하는데 사용되는 수학적 표기법.
- 알고리즘의 런타임 또는 메모리 요구 사항이 입력 크기의 함수로 어떻게 증가하는지 표현하는 방법을 제공한다.

에라토스테네스의 체(Eratosthenes sieve)

주어진 정수 N보다 작은 모든 소수를 구한다.
자세한 설명 링크 : https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

#include <stdio.h>

int number = 100000;
int a[1000001];

void primeNumberSieve() 
{
    for (int i = 2; i <= number; i++)
    {
        a[i] = i;
    }

    for (int i = 2; i <= number; i++) 
    {
        if (a[i] == 0) continue;

        for (int j = 2 * i; j <= number; j += i) 
        {
            a[j] = 0;
        }
    }

    for (int i = 2; i <= number; i++) 
    {
        if (a[i] != 0) printf("%d ", a[i]);
    }
}

int main(void) {
    primeNumberSieve();
    delete[] a;
    return 0;
}

위 링크의 코드에 main 함수쪽에 delete[] a; 코드 추가로 할당된 메모리 해제

어떤 문제의 해결 알고리즘은 여럿이 존재하며 선택의 문제가 있다.

알고리즘의 선택은 문제의 제한사항과 문제해결의 환경에 대한 고려가 필요하다.

알고리즘의 분석은 알고리즘 선택을 위한 객관적 기준을 제공하기 위함이다.

일을 할 때, 문제가 되는 부분을 정확하게 파악하는 것, 목적, 목표를 정확하게 아는 것은 최고, 최적의 결과를 얻기 위해서 매우 중요하다. 이것은 알고리즘을 공부하면서 너무나 흡사한 모습이 많은 것 같다.

컴퓨터의 계산은 인간의 직관적인 사고방식이 다르기 때문에 컴퓨터, 컴퓨터 그래픽스에 대해서 이해하는 것은 매우 중요한 것 같다.

저작자표시 비영리 변경금지

'Study > Algorithm' 카테고리의 다른 글

[알고리즘] Atlas : Shelf, Guillotine, Maxrects (0)	2024.05.01

현재글[알고리즘] 개념

뉴비 TA

뉴비 TA 김성인

shader, 문제해결, study, PostProcessing, UE5, Optimization, 리소스 관리, Render Monkey, rendermonkey, Algorithm, UE4, Unreal, light, rendering, 최적화, 블루프린트, HLSL, TroubleShooting, blueprint, LIGHTING,

Today :
Yesterday :

뉴비 TA