Chapter01 자료구조와 알고리즘의 이해

자료구조와 알고리즘

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

알고리즘: 표현 및 저장된 데이터를 대상으로 하는 문제의 해결방법

예)

다음과 같은 배열 선언은 자료구조적 측면의 코드이다.

int arr[10] = {1, 2, 3, 4, 5, 6, ,7, 8, 9, 10}

반면 배열에 저장된 모든 값의 합을 더하는 다음 반복문의 구성은 알고리즘적 측면의 코드이다.

for(i=0; i<10; i++)

sum += arr[i];

자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있기 때문에 자료구조와 알고리즘은 밀접한 관련이 있다.

"자료구조에 따라서 알고리즘은 달라진다"

"알고리즘은 자료구조에 의존적이다"

시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity)

시간 복잡도: 속도에 해당하는 알고리즘의 수행시간 분석 결과

공간 복잡도: 메모리 사용량에 대한 분석결과

문제 01-1[빅-오 구하기]

아래 식들을 대상으로 빅-오를 판단해보자.

$$3n+2$$

$$O(n)$$

$$7n^3+3n^2+2$$

$$O(n^3)$$

$$2^n+n^2$$

$$O(2^n)$$

$$n+logn$$

$$O(n)$$

$$n+nlogn$$

$$O(nlogn)$$

$$2^n+n^3$$

$$O(2^n)$$

대표적인 빅-오

'데이터 수의 증가'에 따른 '연산횟수의 증가 형태를 표현한 것'

• O(1)
  상수형 빅-오. 연산 횟수가 고정인 유형의 알고리즘을 대표한다.

• O(logn)
  로그형 빅-오. '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘. 매우 바람직한 유형.

• O(n)
  선형 빅-오. 데이터의 수와 연산횟수가 비례하는 알고리즘

• O(nlogn)
  선형로그형 빅-오. 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘. 이에 해당하는 알고리즘이 적지 않다.

• O(n^2)
  데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘. 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생.

• O(n^3)
  데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘. 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생.

• O(2^n)
  지수형 빅-오. 사용하기에 매우 무리가 있는, 사용한다는 것 자체가 비현실적인 알고리즘.