GYU's DEV STORY

시퀀스 컨테이너 = list, vector, deque.

적은 자료를 보관. 

연관 컨테이너 = map, set, hash_map, hash_set.

Key값이 중복되어도 괜찮다면, 컨테이너 앞에 'multi'를 붙인다.

multi_map, multi_set, hash_multimap, hash_multiset을 사용한다.

map, set, hash_map, hash_set 뭔 차이?

map, set  = 자료를 정렬하여 저장. 따라서 데이터를 순회할때 정렬된 순서대로 순회한다.

hash_map, hash_set = 정렬 X 저장. 그래서 검색 속도가 map,set보다 빠름.

BUT!

해시 테이블은 저장한 자료가 적으면.... 메모리 낭비, 검색시 오버헤드가 생긴다.

hash_map

hash_map을 이용하여, 반복되지 않는 첫 번째 문자 찾기.

http://www.hanbit.co.kr/network/view.html?bi_id=1618

자료구조는 알고리즘 + 프로그램 이다. 프로그램에서 자료(data)를 처리하고 있고 이들 자료는 자료구조(data structure)를 사용하여 표현되고 저장된다. 또한 주어진 문제를 처리하는 절차가 필요하다. 이것은 알고리즘(algorithm)이라고 불린다.

자료 구조가 결정되면 그 자료 구조에서 사용할 수 있는 알고리즘이 결정된다.

알고리즘이란 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것이다.

알고리즘 조건은 무엇일까?

알고리즘을 기술하는데 유사코드(preudo-code) , 프로그래밍 언어가 가장 많이 쓰인다.

유사코드는 흔히 알고리즘을 기술하는데 선호되는 표기법이다.

EX> 최대 값을 찾는 알고리즘을 유사코드로 표현

ArrayMax(A,n)

tmp <-- A[0];

for i <-- 1 to n-1 to

if tmp < A[i] then

tmp <-- A[i];

return tmp;

tmp = A[0];

for(int i = 1 ; i<n-1; i++)
{

if(tmp < A[i])

{

tmp = A[i];

}

}

프로그램에서 데이터(data)란 처리의 대상이 되는 모든 것을 말한다.

데이터 타입(data type)? 데이터의 집합과 이러한 데이터에 적용할 수 있는 연산의 집합을 의미한다.

추상화란, 어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것이다.

추상 데이터 타입이란 새로운 데이터 타입을 추상적으로 정의한 것이며, 자료 구조를 추상적, 수학적으로 정의한것이다.

추상데이터 타입은 많은 장점을 가지고 있으니까  거부감 갖지말고.. 무서워 하지말자...

자료구조 (data structure)는 이러한 추상 데이터 타입을 프로그래밍 언어로 구현한 것이라 할 수 있다.

좋은 추상화는 어떤것일까?

사용자에게 중요한 정보는 강조되고 반면 중요하지 않은 구현 세부 사항은 제거되는 것이다.

이를 위하여 정보은닉기법(information hiding)이 개발되었고 추상 데이터 타입의 개념으로 발전 되었다.

추상 데이터 타입(abstract data type: ADT)은 데이터 타입의 프로그램이 그 데이터 타입의 구현으로부터 분리된 데이터 타입을 말한다. 즉, 데이터 타입을 추상적으로 정의함을 의미한다. 데이터의 집합과 데이터에 가해지는 연산들의 집합의 수학적인 명세이다.

효율적인 알고리즘이란 결과가 나올 때까지의 수행 시간이 필요하면서 컴퓨터 내에 있는 메모리와 같은 자원을 덜 사용하는 알고리즘이다.

수행 시간 측정 방법

주로 clock 함수가 이용된다.

clock 함수는 호출 프로세스에 의하여 사용된 CPU 시간을 계산한다.

clock_t clock(void);

clock 함수는 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환한다.

알고리즘을 시작하기 전에 한번 clock 함수를 호출하여 start 변수에 기록하고, 알고리즘이 끝나면 다시 clock 함수를 호출하여 finish 변수에 기록한 다음, 초단위의 시간을 측정하기 위하여 (finish - start)값을 CLOCKS_PER_SEC으로 나누어 주면 된다.