알고리즘, 자료구조

알고리즘 (Algorithm)

문제를 해결하기 위해 정해진 진행절차나 방법을 의미하며,
컴퓨터에서 알고리즘이란 어떠한 행동을 하기 위해서 만들어진 프로그램 명령어의 집합이다.

<알고리즘 조건>
1. 입력 : 알고리즘은 0개 이상의 입력을 가져야 함
2. 출력 : 알고리즘은 최소 1개 이상의 결과를 가져야 함
3. 명확성 : 수행 과정은 모호하지 않고 정확한 수단을 제공해야 함
4. 유한성 : 수행 과정은 무한하지 않고 유한한 작업 이후에 정지해야 함
5. 효과성 : 모든 과정은 명백하게 실행 가능해야 함

자료구조(DataStructure)

프로그래밍에서 데이터를 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리 저장을 의미한다.
데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다.

<자료구조 형태>
선형구조 : 자료 간 관계가 1 대 1인 구조
배열, 연결리스트, 스택, 큐, 덱
비선형구조 : 자료 간 관계가 1 대 다 혹은 다 대 다인 구조
트리, 그래프

알고리즘 성능

효율적인 문제해결을 위해선 알고리즘의 성능을 판단하 수 있는 기준이 필요하다.
상황에 따라 적합한 알고리즘을 선택할 수 있도록 하는 기준이다.

<알고리즘 평가 기준>
컴퓨터에서 알고리즘과 자료구조의 평가는 시간과 공간 두 자원을 얼마나 소모하는지가 효율성의 중점을 둔다.
일반적으로 시간을 위해 공간이 희생되는 경우가 많다.
시간복잡도 : 알고리즘의 시간적 자원 소모량
공간복잡도 : 알고리즘의 공간적 자원 소모량

<Big-O 표기법>
알고리즘의 복잡도를 나타내는 점근표기법으로 이터 증가량에 따른 시간 증가량을 계산한다.
가장 높은 차수의 계수와 나머지 모든 항을 제거하고 표기하며 고리즘의 대략적인 효율을 파악할 수 있는 수단으로 사용한다.

 int Case1(int n) //n을 n곱한다
 {
     int sum = 0;
     sum = n * n;
     return sum;
 }
 int Case2(int n) //n을 n번만큼 더한다
 {
     int sum = 0;
     for (int i = 0; i < n; i++)
         sum += n;
     return sum;
 }
 int Case3(int n) //1을 n만큼 더하는 것을 n만큼 더한다.
 {
     int sum = 0;
     for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
             sum++;
     return sum;
 }
 
 // 입력값       Case1	    Case2   	   Case3
// n = 1            1           1              1
// n = 10           1          10            100
// n = 100          1         100         10,000
// n = 1000         1        1000      1,000,000
// Big-O		 O(1)	     O(n)   	   O(n²)

// ex) 0(n+3) → +3 중요성 낮음
//     0(2n²+2) → n²이 작업량에 따라 시간복잡도의 증가폭을 결정하는 핵심으로 나머지 항은 무시

<수행 시간 분석>
알고리즘의 성능은 상황에 따라 수행 시간이 달라지는데, 수행 시간을 분석하는 경우 평균의 상황과 최악의 상황을 기준으로 평가한다.
최선의 상황의 경우 알고리즘의 성능을 분석하는 수단으로 적합하지 않다.

int FindIndex(int[] array, int value) //배열 array에서 값 value 찾기
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == value)
            return i;
    }
    return -1;
}
// 최선   평균               최악
// O(1)   O(n/2)→0(n)       O(n)