[두근두근 자료구조] 05,06,07장

05장 포인터와 연결리스트

연결 리스트 : 포인터의 이용

스택

pop 연산의 시간복잡도 O(1)

시험 무조건 나옴(linked list로 구현한 stack의 push, pop) 

 

큐

---

06장 리스트

 

단순 연결 리스트

size 함수 시간 복잡도 O(n) 

삭제 연산 시험 !!

 

이중 연결 리스트

무조건 암기

같은 유형

 

---

07장 순환

순환 의 예 : 팩토리얼 값 구하기, 피보나치 수열, 이항계수, 하노이의 탑, 이진탐색

# 팩토리얼
int factorial(int n)
{
	printf("factorial(%d) \n" , n);
    if (n==1) return 1;
    else return (n*factorial(n-1));
}

분할 정복 (divide and conquer)

 

순환 vs. 반복

복잡도 분석(2^n)-거듭제곱 구하기 : 순환 O(logn) / 반복 O(n)

피보나치 수열 : 순환 2^n / 반복 O(n) 

recursion이 속도가 느린이유 -> 함수 호출 시 스택을 이용해 push, pop을 사용하기 때문에 

 

예제 : 연습문제