[자료구조 알고리즘] 자료구조, 알고리즘, 함수(패턴), 빅-오 표기

[자료구조와 알고리즘]

- 프로그램 : 데이터 표현(자료구조)하고, 표현된 데이터를 처리(알고리즘)하는 것임

=> 어떤 자료구조를 사용했을 때 효율적(알고리즘 : 시간, 공간)으로 처리할 수 있을 것인가?

=> 어떤 결과값을 리턴해내야하는가 : 어떤 결과가 필요한가부터 정하고 

     => 반 학생(36명) 중 아침을 먹고온 사람이 있는지 없는지 체크할 때 : 배열, 순차탐색 알고리즘

(1) 선형구조 : 리스트, 스택, 큐

(2) 비선형구조 : 트리, 그래프

(3) 파일구조 : 순차파일, 색인파일, 직접파일

(4) 단순구조 : 정수, 실수, 문자, 문자열

- 알고리즘 맛 보기

(1) 순차탐색알고리즘

int LSearch(int arr[], int len, int target){
     for(int i=0; i<len; i++{
          if(arr[i] == target){
               return i;
          }
     }
     return -1;
}

- 순차탐색알고리즘 중심 연산 : == , target과 맞는지 아닌지를 보는 것이 중요

=> 주변에 여러 연산자가 있지만 중심 연산자에 따라 주변 연산자 처리 횟수가 달라짐

=> 최악의 경우를 근거로 알고리즘 평가 : 끝까지 순차탐색을 하는 경우

(2) 이진탐색알고리즘

int Lsearch(int arr[], int len, int target){
 
     int first = 0;
     int last = len-1;
     int mid;
 
     while(first <= last){
          mid = (first + last) / 2;
     
          if(arr[mid] == target){
               return arr[mid];
          } else {
               if(arr[mid] > target){
                    last = mid-1;
               } else { // arr[mid] < target 
                    first = mid+1;
               }
          }
     }
 
     return -1; // 찾지 못했을 때
}

- 순차탐색과 달리 배열이 정렬되어있어야함 : 장점이자(좋은 성능) 단점

=> 정렬 기준은 상관없지만 정렬은 되어있어야함 : 그래서 좋은 성능

- 배열의 중간 인덱스를 구한 뒤 중간 인덱스의 값을 기준으로 왼쪽 or 오른쪽 선택 탐색

=> first와 last를 줄여나감 : 탐색 범위를 줄여나감

     => first와 last가 같을 때에는 1개의 대상이 남음 : 탐색 확인해야함

     => 반복문 : first와 last가 같거나 last가 클 때까지 : 탐색 범위가 있을 때까지

=> 왼/오른쪽에서 1/2 : 쪼개서 탐색 : 쪼갤 때 중간이 또 기준을 삼아서 기준부터 비교, 어느쪽을 선택해서 탐색할 것인지

     => 나머지를 버리면 됨 : 그대로 정수만 저장되게 int형 mid

=> 경우의 수 : 찾지 못했을 때까지 생각

- mid + 1 or mid -1 : mid를 first나 last에 그대로 대입하면 결국 first+last/2값을 그대로 대입한 것이므로 역전현상이 일어나지못함

=> 마지막에 탐색 대상이 2개에서 1개로 줄어들 때 first와 mid는 계속 같은 값을 가지게됨 

- 알고리즘을 구현하는 것도 중요하겠지만 알고리즘 순서도를 머릿속에 그릴줄 알아야함 

- 알고리즘 성능분석 : 시간(처리속도) / 공간 복잡도(메모리) - 함수( T(n) )를 구하는 것(일반화 == 수식화)

=> 알고리즘을 왜 공부해야할까?

=> 알고리즘을 아는 것과 알지 못하는 것의 차이...?

=> 데이터 개수가 늘어날 때 : 일정값 이하일 때에는 A 알고리즘이 좋다가, 일정값 이상이 되자 B 알고리즘이 더 효율적

     => 데이터 개수(n)일 때 연산 횟수가 급격하게 늘어나지 않는 알고리즘

(1) 기본적으로 함수에 대해서 이해하기 : 지수, 로그  / x (데이터 수)에 따라 y (시간)이 듦

=> 패턴 분석 : 알고리즘이 어떤 처리 패턴을 보이는가? - 그래프

=> 예시 : 이진탐색알고리즘 - 타겟을 찾을 때까지 1/2를 하고 범위를 좁혀나가는 알고리즘

     => n이 1이 되기까지 2로 나눈 횟수 k회 : n(arr[mid])개의 숫자에서 숫자(임의 수 1)를 찾을 때까지 몇번 비교 연산을 하는가

     => 함수화 : 1 = n x (1/2)^k  -> n x 2^-k  -> 2^k = n -> log2_n = k -> 예시 - 8개 일 때 연산은 3회

(2) 시간과 공간복잡도 

- 시간복잡도 : 얼마나 빠른가?(CPU)

=> 중심이 되는 특정 연산(CPU) 횟수 

=> 데이터 수에 대한 연산 횟수 함수 T(n) 구하기 : 그래프

     => 적은 경우에는 큰 의미가 없음 : 함수를 구해두는 것이 좋음

     => 패턴! : 그래프!

- 공간복잡도 : 얼마나 메모리를 적게 쓰는가?(Memory) - 메모리 액세스 횟수에 따라 망

- 시간복잡도를 더 중요시 함

(3) 빅-오 표기법 : 시간 복잡도의 목적은 n의 값에 따른 T(n)의 증가 및 감소 정도를 판단하는 것임

- 변화를 봄 : 실제로 영향력을 끼치는 부분만 남김

=> 예시 : T(n) = n^2 + 2n +1 

     => T(n) = n^2 + 2n

     => T(n) = n^2

     => O(n^2) : 빅-오의 표기 방법 - T(n)의 빅-오는 n^2

     => 진짜 이래도 될까? 기준이 있음

          => 10, 100, 1000, 10000 ---- 을 넣고 결과값에 기여하는 비율을 따짐 : 그런 후 제외

- 실제로 영향력을 끼치는 부분을 가리켜 빅-오 라 함

=> 최고차항의 차수가 빅-오가 됨 : 5n^3 + 3n^2 + 2n + 1 -> O(n^3)

     => 차수만 빼는 것 : 앞의 수가 있고 없고에 따라 기울기는 다르겠지만 패턴은 같음 

     => 결국 시간복잡도 계산은 패턴찾기 : 세밀함을 따질 때에는 붙임

- 로그형 빅 - 오 가 좋다 : 데이터 개수가 증가하지만 연산횟수가 크게 늘어나지않음

=> O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) ....

- 빅-오 표기법으로 변환하기에 앞서 패턴을 구해야지?

=> 패턴(알고리즘)이 얼마만큼 효율적인가 봐야할 것 아니겠음 : 빅 - 오 표기법으로 변환했을 때

     => 핵심 연산을 찾고, T(n)을 구하고 : 어떤 알고리즘을 사용하는지에 따라 연산횟수가 달라짐

     => 예시 : 데이터가 n개 일 때 target을 구하기위해 k회 연산 : T(n) 함수 구하기

     => 알고리즘! 효율적인 프로그램을 만들기위해 필요함!     

     => 각 상황에서 어떤 알고리즘을 사용해야 효율적인지 생각할 수 있어야함