알고리즘 : 프로그램을 어떻게 작성하느냐?
자료구조 : 자료를 어떻게 구조화하느냐?

이 두 가지가 프로그래밍 실력을 업그레이드 시킴

---

알고리즘

최적화(optimization)

• 자원(cpu,memory,gpu,hdd..)을 효율적으로 사용하는지?
• 속도가 얼마나 (실행시간)이 어떻게 나오는지?
• 하드웨어 성능과 환경의 차이 때문에 측정하기 어려움 -> 고정되고 정형화된 수치가 필요함

성능을 체크할 수 있는 수단 (정형화된 값)

복잡도(complexity)

• time complexity - 시간 cpu
• space complexity - 공간 메모리

시간 복잡도 : 코드가 몇 줄 실행되느냐?
공간 복잡도 : 변수가 몇 개가 올라가느냐?
(메모리 차지 정도)
(주어진 입력은 차이가 없으므로 비교하지 않음)

---

BIG O Notation(표기법)

• 입력에 대한 추상적인 정량화
• 구체적인 단위(초, 바이트)가 아닌 추상적인 코드의 성능
• 시간이나 공간이 입력에 따라 얼마나 늘어나느냐가 초점
• 곱하기는 변수를 제외한 상수는 무시
  ( 0[3*n]=0[n] )
• 더하기는 가장 높은 차수만 사용함
  ( 0[3] = [3*n^0] = 0[n^0] = 0[1] )
  ( 0[4x^2 + x] = 0[x^2] )
  (0[10000] = 0[1] )
  (0[10000 * n] = 0[n] )
  0([n / 1000]=[n* 1/10000] = 0[n])
• 점근법 : 점점 n(입력의 개수)에 대한 근사치가 되는 방식
• 입력이 늘어났을 때 프로그램에 가장 영향을 주는 것이 무엇인지 찾아내는 것

void Ex1(int n)
{
        for (int i = 0; i < n / 2; ++i)
        {
                std::cout << i << std::endl;
        }

        for (int i = 0; i < n; ++i)
        {
                for (int j = 0; j < n; ++j)
                {
                        std::cout << i + j << std::endl;
                }
        }
}
//시간복잡도 : n^2+1/2n >> n^2
//공간복잡도 : o(3) >> o(1)(j도 하나임 왜냐면 블럭을 빠져나가면 없어지고 다시 만들어지기 때문에)

void Ex2(int n)
{
        for (int i = 0; i < 3; ++i)
        {
                for (int j = 0; j < n; ++j)
                {
                        std::cout << i * j << std::endl;
                }
        }

        for (int i = 0; i < 1024; ++i)
        {
                std::cout << i << std::endl;
        }
}//시간복잡도 : 3n +1024*1 >> 3n >> n
 //공간복잡도 : 0(3) >> o(1)

void Ex3(int n)
{
        for (int i = 0; i < 5; ++i)
        {
                Ex4(n);
        }
        
        for (int j = 0; j < 10; ++j)
        {
                std::cout << j << std::endl;
        }
}
//시간 : 5*ex4() + 10 ex4 는 k^2 >> n2>> 5n^+10 >>n^2
//공간 : 2+ex4(2) >> 0(4) 기존변수가유지된상태로 변수가 추가됨 >>0(1)

void Ex4(int k)
{
        for (int i = 0; i < k; ++i)
        {
                for (int j = 0; j < k; ++j)
                {
                        std::cout << i * j << std::endl;
                }
        }
}

동적 할당 메모리

int* Clone(int array[], int count)
{
    int* pArray = new int[count];
    for (int i = 0; i < count; i++)
    {
        pArray[i] = array[i];
    }
    return pArray;

    
    //공간복잡도는 n+2 (동적으로 할당하는 것은 메모리에 만들어지기 때문에 count개로 취급)
}
    

int main()
{
    const int COUNT = 10;
    int array[COUNT]{ 1,2,3,4,5,6,7,8,9,10 };
    int* newArray;
    newArray = Clone(array, COUNT);
    for (int i = 0; i < COUNT; i++)
    {
        std::cout << newArray[i] << std::endl;
    }
    delete[] newArray;
    newArray = nullptr;
    //delete는 여기에 왜냐하면 써야하기 때문
}

재귀함수

void Countdown(int n)
{
	//base case
	if (n == 0)
	{
		std::cout << "FIRE!" << std::endl;
		return;
	}
	//recursive case
	std::cout << n << std::endl;

	Countdown(n - 1);
}

int main()
{
	Countdown(5);
}
//시간 복잡도 :0(n)
//공간 복잡도 :0(n) (재귀호출은 메모리를 쌓는방식이라서 공간복잡도도 증가함)
void CountDown(int n)
{
	...

		CountDown(n - 2);
}
//o(1/2n)=>0(n)

---

패턴이 정해저 있음

숫자가 작게 증가(=시간 복잡도가 낮음 =빠름)
O(1)
O(log n)
O(n)

O(n log n)
O(n^2) : 정렬
O(2^n)
O(n!)
숫자가 크게 증가(=시간 복잡도가 높은 =느림)

로그

• 2^3 = 222 = 8
• 8을 2로 몇번 나눌 수 있느냐?
• 승수의 반대개념
• x^y =k
• logx에 몇번 곱하면 k를 만드냐
• logxk = y

void Logarithmic(int n)
{
	while (x>=1)
	{
		n /= 2;
 //log(2)n 2로 나누면 최대 몇 번 나누기가 가능하냐
	}