자료구조와 알고리즘

 

자료구조 (Data Structure)

데이터를 조직하는 방법

데이터를 어떻게 조직하는가에 따라 프로그램의 성능이 달라지기 때문에 자료구조가 필요하다.

데이터 조작에 적합한 알고리즘을 선택하는 것도 중요하다.

자료구조와 알고리즘은 필수로 알아야 한다. 구현력의 차이가 다름

 

재귀

함수가 자기자신을 호출하는 것

 

재귀의 구조

기저 조건 : 재귀를 중단시키는 조건

재귀 조건 : 재귀의 조건 (기저 조건에 수렴하도록 설계)

재귀 조건을 돌면서 기저조건에 점점 수렴하게되다가 기저 조건에 걸리면 중단됨

 

 

재귀호출을 사용하는 이유

문제에 따라 전체를 한 번에 해결하기보다 같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적일 수 있기 때문 (분할 정복법)

 

단점

함수를 호출하기 때문에 함수에 따른 오버헤드가 발생할 수 있다.

 

 

자료구조

크게 선형 구조와 비선형 구조로 나뉜다.

선형구조 : 서로 일렬로 이렇게 조직이 되어 있는 것

비선형 구조 : 일렬이 아니라는 거죠

 

연산 : 읽기 검색 삽입 삭제

 

순차 자료구조 : 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장 (배열)

연결 자료구조 : 노드라는 여러개의 메모리 청크에 저장 (포인터)

 

 

알고리즘의 분석

알고리즘을 분석한다 : 알고리즘의 자원의 사용량을 분석한다?? 자원을 적게 사용할수록 효율적이다

 

 

시간 복잡도

시간이 적게 걸리는게 좋다.

단순 측정으로는 측정하기 어렵다 → 객관적인 지표가 필요함 → 시간 복잡도가 생김

(연산이 몇개나 필요한가를 중접적으로 본다)

어떻게 구현하는가에 따라 입력값에 따라 큰 차이가 나타난다는 것을 알 수 있다. (시간의 성장률)

 

점근적 표기법

Big-O 표기법

리미트를 표현(최악의 경우일 때)의 시간 복잡도를 나타내기 때문에 많이 사용

 

카테고리는 위와같이 나누어지지만 항상 그런것은 아니다.

사용하기기 편하게 한 눈에 파악하기 위함으로 Big-O는 대략적인 지표만 제공한다 (정확한 시간 X)

같은 카테고리라면 어떤 알고리즘이 더 빠른지 면밀한 분석이 필요할 것

정확한 정보를 얻고 싶다면 정확한 시간복잡도 함수를 사용하는 것을 권장한다.

 

공간 복잡도

얼마나 메모리를 추가적으로 더 사용해야 하는가.

알고리즘을 수행하는 데 메모리가 얼마나 필요한가

많이 신경쓰지는 않는다 (시간이 중요하니까)

보통 시간이랑 공간 복잡도는 반비례하는 성향을 보임 ( 가치 : 시간 > 공간(메모리) )

메모리가 충분하면 시간을 활용한다.

 

 

STL

C++에서는 표준 템플릿 라이브러리 (Standard Template Library) 라고 한다.

그때그때 찾아보면서 사용해보자

 

우리가 살펴볼 내용

컨테이너 라이브러리, 반복자 라이브러리, 알고리즘 라이브러리

 

- 임의 타입의 객체를 보관할 수 있는 컨테이너 라이브러리(Container Library)
- 컨테이너에 보관된 원소에 접근할 수 있는 반복자 라이브러리(Iterator Library)
- 반복자를 가지고 일련의 작업을 수행하는 알고리즘 라이브러리(Algorithm Library)

 

컨테이너는 앞으로 배울 구현체

반복자는 컨테이너에 접근할 수 있는 포인터라 생각할 수 있다.

 

이는 구현 코드의 개수를 줄이기 위해 나눠놓음

 

알고리즘 각각을 컨테이너에 적용하지 않아도

반복자를 통해 N * M 이 아니라 N + M으로 줄일 수 있다고 하는데.... <<<<<<여기 좀 더 보충

 

컨테이너 개수를 N, 알고리즘의 개수를 M이라 하면

N *  M 개의 구현 코드가 발생하는데

반복자를 추가하면서 N + M 개로 줄일 수 있대