자료구조 강의 1
자료구조 강의 복습 1
웹개발에서 자료구조, 알고리즘은 많이 안 쓰이니 누군가는 시간낭비라고 생각 할 수 있지만,
나의 실력의 토대가 되는 작업이라 생각하고 다시 기본부터 찬찬히 공부하려 한다.
하루의 강의 20분 남짓 알고리즘 풀이 1시간 정도로 나의 기본기를 쌓을 시간을 가질 예정이다.
매일은 아니더라도 꾸준히 올릴 수 있는 포스팅이 되길 나에게 바란다!
자료구조의 기본
선형구조
- 배열
- 연결 리스트
- 스택
- 큐
비선형 구조
- 트리
- 그래프
프로그램의 성능 측정 방법론
시간복잡도 : 알고리즘에 사용되는 연산 횟수
- 최악의 경우를 나타내는 Big-O 표기법을 사용한다
- 시간 복잡도 표기시 항상 큰 항과 계수만 표기한다.
- 현실적인 문제에서 시간 제한은 1초 정도라고 생각한다.
공간 복잡도 : 알고리즘에 사용되는 메모리의 양
- MB 단위로 일반적으로 표기한다
- int a[1000] : 4KB
효율적인 알고리즘인 경우 일반적으로 시간과 공간은 반비례 관계이다.
//O(n)의 시간 복잡도
int main(void){
int a,b;
cin >> a >> b;
int sum = 1;
for(int i = 0; i <b ; i++){ //i가 b만큼 반복한다는 의미
sum *= a;
}
cout << sum;
}