개념 - 자료구조와 알고리즘의 이해

이하 출처 : c++로 쉽게 풀어쓴 자료구조

자료구조

- 자료들을 정리하고 조직한 방법

선형 자료구조 linear data structure

직접 접근(direct access) : 배열. [i]를 한번에 접근 가능.

순서 접근(sequential access) : 연결 리스트. 하나씩 순서대로 접근해야함.

- 스택, 큐, 덱 : 배열이나 연결리스트로 구현 가능하나 접근이 처음과 끝으로 제한됨.

비선형 자료구조

트리 : 계층 구조의 표현에 적합

- 이진 탐색 트리 : 탐색에 적합

- 힙

- AVL 트리

그래프 : 관계도를 표현하는 복잡한 형태의 자료구조

- 방향 그래프

- 무방향 그래프

- 가중치 그래프 : 신장 트리, 최단 경로

자료구조의 활용 방법 : 정렬과 탐색

알고리즘

- 어떤 문제를 해결하는 절차

- 프로그램 = 자료구조 + 알고리즘

- 알고리즘의 조건

- 출력은 반드시 존재해야함

- 종료 조건이 반드시 있어야함

- 실행할 수 있는 모호하지 않은 연산이어야 함

- 알고리즘 기술 방법

- 자연어

- 흐름도

- 유사코드 (psuedo-code)

- 프로그래밍 언어

ADT

객체와 연산의 정의 및 "구현으로부터 명세의 분리" (정보은닉)

C++의 객체지향의 개념은 ADT의 개념과 일치함

---

이하 출처 : 열혈 자료구조

01-1. 자료구조(Data Structure)에 대한 기본적인 이해

- 자료구조란 무엇인가?

데이터의 저장 방법.

선형구조 : 데이터가 나란히, 일렬로 정렬

리스트, 스택, 큐

비선형구조 : 나란히 저장하지 않음

트리, 그래프

--------------------- ↑책에서 공부할 내용

파일 구조

순차파일

색인파일

직접파일

단순구조

정수

실수

문자

문자열

- 자료구조와 알고리즘

자료구조 : 데이터의 저장 방법

알고리즘 : 자료구조를 대상으로 하는 문제 해결 방법

자료구조에 따라서 알고리즘은 달라진다. 즉 알고리즘은 자료구조에 의존적이다.

02-2. 알고리즘의 성능분석 방법

- 시간 복잡도(Time Complexity)와 공간 복잡도 (Space Complexity)

시간 복잡도 : 속도. 데이터의 개수 n에 대한 연산횟수의 함수 T(n)을 작성해서 변화량을 체크.

중요한 건 데이터가 일정량 이상 늘어났을 때의 연산량의 증가량이다.

그렇다고 데이터가 적을 때 빠른 알고리즘이 중요하지 않다고 생각하면 안된다.

알고리즘은 절대적인 정답이 있는 것이 아닌 상대적인 것이기에 

상황에 맞는 알고리즘을 적용할려면 문제를 잘 이해하는 능력을 길러야 할 것이다.

공간 복잡도 : 메모리 사용량.

- 순차 탐색 알고리즘과 시간 복잡도 분석의 핵심요소

for(int i = 0; i < len; ++i)

{

if(ar[i] == target)

return i; //찾은 대상의 인덱스 반환

}

위 알고리즘에서 데이터의 수 n에대한 연산횟수의 함수 T(n)을 구하려 할 때 가장 핵심적인 연산은 무엇일까?

바로 비교를 수행하는 ==이다. <와 ++는 이에 종속적이다. 따라서 ==연산의 횟수로 시간 복잡도를 분석하면 된다.

모든 알고리즘에는 최선의 경우(best case)와 최악의 경우(worst case)가 존재한다. 

위 순차 탐색의 최선의 경우는 1이고 최악의 경우는 n이다.

평균적인 경우도 물론 중요하지만 그 기준을 새우기도 애매하거니와 구하기도 힘들기 때문에 신뢰도가 낮아

보통 최악의 경우를 알고리즘 평가에 사용한다.

- 순차 탐색 알고리즘의 시간 복잡도 계산하기1 : 최악의 경우

n개의 모든 원소와 ==를 비교할 때가 최악이므로 T(n) = n

- 순차 탐색 알고리즘의 시간 복잡도 계산하기1 : 평균적인 경우

n개의 원소 중 찾는 답이 없을 때의 복잡도 n  * 1/2(50퍼 확률)

n개의 원소 중 찾는 답이 있을 때의 평균 복잡도 n/2 * 1/2

T(n) = n/2 + n/4 = 3/4n

이처럼 구하기도 번거롭고 값의 신뢰도도 떨어진다.

- 이진 탐색 알고리즘의 소개

이진 탐색 알고리즘은 순차 탐색보다 훨씬 성능이 좋지만 자료가 정렬되어있어야 한다.

작동방식은 다음과 같다. (자료구조가 정렬되어있다고 가정)

1. 시작 인덱스와 끝 인덱스를 더하고 2로 나눈다.

2. 해당 값을 인덱스로 하는 원소 즉 중간값과 찾는 값이 일치하는지 확인

3. 일치하지 않으면 중간값과 찾는 값과의 대소를 비교한다

4. 중간값이 찾는 값보다 작으면 중간값의 인덱스+1 에서 끝 인덱스로 범위를 제한

   중간값이 찾는 값보다 크면 중간값의 인덱스-1에서 시작 인덱스로 범위를 제한

값을 찾거나 시작 인덱스가 끝 인덱스를 넘어설 때까지 (모든 값을 다 확인할때까지) 1~4를 반복. 

- 이진 탐색 알고리즘의 시간 복잡도 계산하기 : 최악의 경우(worst case)를 기준으로

while(first <= last)

{

mid = (first+last) / 2;

if(target == ar[mid])

{

return mid;

}

else

{

//...

}

}

위 알고리즘에서 제일 중요한 연산은 역시 ==다. 그렇다면 T(n)은 몇일까? 

결론적으로 이진탐색은 자료의 개수 n이 1이 될때까지 1/2로 나눈 횟수 k가 바로 연산횟수다. 

1/2로 나눠서 평균값을 구할 때마다 == 연산을 하고있기 때문이다.

따라서 n * (1/2)^k = 1 이라서 n = 2^k, k는 밑이 2인 log n이다. 즉 T(n)은 밑이 2인 log n이 되는 것이다.

- 빅-오 표기법 (Big-Oh Notation)

빅오는 T(n)에서 가장 영향력이 큰 부분이 어디인지를 따지는 것이다.

n^2 + 2n + 1 에서 가장 영향력이 큰 n^2만을 보는 것이다. 이를 O(n^2)이라 한다. (Big-oh of n^2)

- 단순하게 빅-오 구하기

T(n)이 다항식으로 표현된다면 최고차항의 차수가 빅-오가 된다.

빅오는 오직 데이터 수의 증가에 따른 연산횟수의 증가형태에 관심이 있을 때 사용하는 표기법이다. 

4,8,6씩 늘어나든 99,198,396이든 같다는 소리.

따라서 O(log n)은 n이 커질수록 연산횟수의 증가량이 점점 둔화되는 형태다. 로그 그래프와 유사해진다.

이게 무슨말이냐면 예를들어 2^6과 2^7 사이의 수는 6번만 연산해도 된다는 것이기에, 지수가 커질수록 수비범위는 넓어질것이다.

- 대표적인 빅-오

밑으로 갈수록 데이터수에 비해 엄청난 연산횟수 증가량을 보인다.

O(1) : 상수형 빅오.

1번만 연산한다는 뜻이라기보단 연산횟수가 고정이라 항상 똑같은 상수 시간이 걸리는 연산이다.

O(log n): 로그형 빅오.

데이터 수의 증가율에 비해 연산 횟수의 증가율이 훨씬 낮은 아주 착한 알고리즘. 밑은 거의 무시됨

O(n) : 선형 빅오.

데이터 수와 연산 횟수가 비례한다.

O(n log n) : 선형로그형 빅오

데이터의 수가 두배가 될 때, 연산 횟수는 두배가 조금 넘는 형태. 

O(n^2) : 제곱

주로 중첩된 반복문에서 사용되는 형태. 데이터의 양이 커질수록 노답

O(n^3) : 세제곱

주로 삼중첩 반복문에서 사용됨. 개노답

O(2^n) : 지수형 빅오

컴퓨터에 악의를 담은 알고리즘

- 순차 탐색 알고리즘과 이진 탐색 알고리즘의 비교

선형빅오는 5억개의 있을 때 5억인 반면 로그형빅오는 계산기써보니 28이다. 엄청나군

-빅-오에 대한 수학적 접근 : 

f(n)과 g(n)이 있을 때, 

모든 n>=k 에 대하여 f(n) <= Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면 f(n)의 빅-오는 O(g(n))이다.

여기서 k는 n이 어느순간부터 f(n) <= Cg(n)를 항상 만족하는지를 나타내는 상수다.

C는 f(n)이 아무리 커져도 g(n)을 넘지 못하는지를 나타내는 상수다. 

즉 두 조건을 모두 만족하면 f(n)의 빅오는 O(g(n))이 되는 것이다.

따라서 빅오는 데이터 수의 증가에 다른 연산의 증가율의 상한선을 표현한 것이다. 

함수의 최고차항의 차수를 제외한 뭐가 아무리 많아도 모든 n>=k에 대하여 f(n) <= Cg(n)을 만족한다면 g(n)인 것이다.