면접전 자료구조 최종정리(열혈강의 자료구조 윤성우 아님!)

알고리즘의 대부분은 시간복잡도가 공간복잡도보다 더 중요하다.

sum(n)

{
    i <- start;

    sum <- 0;

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

sum <- sum + i

return suk

2 + n * 3 = 3n + 2가 된다.

---

배열리스트보다 연결리스트가 탐색 연산의 비용이 높다..

원하는 자료(원소)를 찾을때까지 포인터로 노드를 탐색해야하니까..

탐색 : 배열(O(c), 연결(O(n)) 

---

원형 큐에서 뭐랄까...그 Rear의 위치 인덱스가 Front의 인덱스보다 작을 경우가 있다..돌다보면 흔한일..

그럴때 특히나..ShowQueue같이 데이터를 출력하는 경우가 있다고 할때...

Front를 기준으로 리어의 인덱스 값을 다시 계산해서 사용한다....그냥 곧바로 Rear의 인덱스를 사용해도 될꺼라고 생각하지만..아니다.

만약에.. for문으로 Front인덱스부터 Rear인덱스까지 순회하는 과정이라면..Rear가 이미 나머지 연산을 통해서 작아있는 경우니까..안되는거다..그래서..

maxIndex(프런트를 기준으로 리어의 인덱스값을 계산한것) = front + currentElementCount;

for(in i = front + 1; i < maxIndex; ++i)

pos = i % maxElemenetCount ; //위에 for문에서 front + 1해준거..나머지 연산할때 + 1해준걸 저기서 미리 해준거다..)

이런식으로 처리하면된다..

덜덜..디큐..두개의 끝을 가지는 큐라는 뜻이였다.. double ended qeueu를 줄인말이였어..

deque!이름도 덱이야..디큐가 아니라네..

---

보통 재귀호출은 느리다. 반복호출보다 느리다..시스템 스택때문에..(무한한 재귀호출은 없다. 스택오버플로우 되서 터진다..)

실제 설명은 재귀방식으로 하고 구현은 반복으로 할때도..

특히 재귀 호출이 함수의 끝에서 이루어지는 꼬리 재귀함수의 경우 쉽게 반복호출로 변경이 가능하다.

꼬리 재귀호출 이라 함은...아래 재귀 호출식에서 알 수 있듯이..재귀 호출이 함수의 끝 부분에 있는 경우를 말한다.

factorial(n) = n * factorial(n - 1)

으아 근데..이렇게 한번 호출되는 꼬리 재귀함수의 경우 반복으로 바꾸기가 변할텐데..만약에 트리에서 순회같이

재귀호출이 2번일 경우에는...스택을 이용해서 처리해야한다..그건 잠시만...

피보나치 수열은 말이다..첫 번째 항과 두 번째 항에 대해서 각각 값이 0, 1이지만..진행과정은

이전 두 항을 더한 값으로 정의되는 수열이다..

0 1 1 2 3 5 8 13 21 ....

근데 왜 이걸 재귀함수로 하면 안되냐면..성능면에서 일단 비효율적인데 그 이유는...같은 숫자에 대한 피보나치 수열 계산이 중복된다는거야...

예를 들어 fib(6)의 계산을 하기 위해..fib(4)가 몇번? 적어도 2번이상일텐데..그런데 실제 fib(4)의 계산은 1번이면 족하다..왜냐면 변하는게 아니니까...불필요한 호출을 한번더 하는 건데..

어쨌든 결론은 불필요한 중복 호출의 증가로 인해서 안좋다는 것이다.

재귀호출에 의한 시간복잡도 : O(2^n)이다 최악이다!!

int fib(int n)        //재귀함수로 구현한 피보나치..

{

int ret = 0;

if(n == 0)
    ret = 0;

else if(n == 1)

ret = 1;

else

ret = fib(n - 1) + fib(n - 2);

return ret;

}

오오...이해가 한번에 된다..그러나 못쓰낟...ㅠ

int fib2(int n)

{

int ret = 0;

if(n < 2)

ret = n;

else

{

int i = 0; temp = 0, current = 1, last = 0;

for(i = 2; i <=n; ++i)

{

temp = current;

current += last;

last = temp;

}

ret = current;

}

return ret;

}

하노이~~ 탑

풀이 과정은 

1. n - 1개의 원판을 A에서 B로 옮기고 나서 

2. 맨 밑의 원판을 C로 옮기고 

3. n - 1개의 원판을 B에서 C로 옮기는 것으로 구성된다.

의사코드로 정리하면..

야 그런데..2번은 문제가 없어 왜냐면 1개 움직이니까..그런데..

1번과 3번봐바..어떻게 옮길까?

근데 1번이나 3번은 같은 원판 옮기기 문제이다..

그런데..같은 옮김이긴 한데..이동해야될 원판은 기존의 원판과 같지 않다..맨 밑 원판을 제외한 나머지 원판들이라는 차이가 있다..

음..문제의 범위가 n - 1로 줄어든것뿐..계속 같다..같은 형식의 문제이면서 호출 때마다 문제의 범위가 줄어든다는 점에서 재귀적 호출로 변경할 수 있다는 것을 추측할 수 있다.. 단, 여기서 from과 to의 대상은 변경되기 때문에..

hanoi(front temp to)

if(n==1)

from에서 to로 원판을 옮기고

else

hanoi(n - 1, from to temp)

from에 있는 한개 원판을 to로 옮기고

hanoi(n - 1 temp front to)

재귀 호출이 함수의 끝에서 이루어지는게 아니라, 머리와 꼬리 2군데에서 발생하니까 반복 호출로 쉽게 변경하기 어렵다..

재귀연습문제

1 + 2 + 3 + 4 .... + n 만들어봐

int sum(int n)

 if(n > 1)

return sum(n - 1) + n;

return 1;

1 + 1/2 + 1/3 + 1/4 .... + 1 / n

double cal(double n)

if(n > 1)

return sum(n - 1) + (1.0 / n);

return 1;

int sum(int n)

if(n == 1)

return 1

else

return n + sum( n - 1)

이걸 반복호출로 바꿔봐..

---

트리에서

자식들의 수를 차수라고 한다~ 차수~!!

레벨이란 그냥 맨 위의 루트노드를 레벨1로 하나씩 단계별로 내려가는것..(레벨은 증가하지..)

루트가 1이면 그 다음 자식들은 레벨 2

그럼 높이는 뭐냐..높이는 자신의 자식 노드중에서 높이가 가장 높은 자식 노드의 높이에 1을 더한 값이다.

즉, 노드의 높이를 계산하기 위해서는 먼저 자식 노드들의 높이를 먼저 알아야 한다.

단만 노드의 높이는 1이다. 부모로 올라갈 수록 1씩 증가..이때 각 노드에서는 더 높은 높이를 가진 자식 노드의 높이에 1을 더한다.

B

E         F

I

M

이런식의 트리가 있다면 B의 높이는?? 여기서 단말인 M, F는 높이가 1이고 I는 M에서 올라가니 높이가 2, E는 높이가 3

그럼 B의 입장에서는 더 높은 높이인 E의 높이 3에 1을 더한 4가 높이다.

배열을 이용한 이진 트리 구현

 - 노드의 번호가 인덱스 역활을 한다.

노드의 개수가 N개인 이진 트리를 위와 같은 방식으로 1차원 배열에 저장할 때에는 다음과 같은 규칙이 적용된다.

1) 노드 I의 부모 노드 인덱스  = *I / 2, 단 I > 1

2) 노드 I의 왼쪽 자식 인덱스 = 2 X I

3) 노드 I의 오른쪽 자식 노드 인덱스 = (2 X I) +1

즉, 노드 번호가 I인 노드가 배열에서는 위치 인덱스 I에 저장된다.

*이거 붙은 I / 2는 소수점 부분을 제거한다..예를 들어 인덱스가 3인 노드의 부모는 위식에 의해 인덱스가 1인 노드가 부모가 된다..

근데 이거 잘 안써 왜냐고? 메모리 공간이 낭비가 심해 

높이가 H인 트리에 대해서는 미리 최대 저장 노드 개수보다 한개 더많게 2^h - 1 + 1메모리를 할당해야하기 때문이야..

(알지? 루트부터 1 2 4 8 16 32 64 순으로 자식들이 확장하는것, 이진트리라 그런거다)

ㅋㅋ 야 근데 순회에서 전위 중위 후위 말고도 레벨 순회라는게 있네..

기존 순회는 현재 노드 방문과 서브트리 방문으로 구성된것에 비해 레벨은 형제 노드 방문으로 구성되어있어..

즉...레벨 1 시작으로 레벨 2모든 노드 방문 레벨 3 모두 방문..이런식..레벨 내에서는 왼쪽에서 오른쪽으로 순회가 진행되..

자 레벨 순회 모르니까 한번보자

낮은 레벨에서 높을 레벨로 진행된다. ..뭐냐 없네..

야 순회할때 재귀함수 말고 반복호출(스택)써서 하는거 보자..

우선 노드에는 방문여부를 저장할 변수가 있어야 한다..

그리고

반복 전위순회는 스택을 활용하는데..

스택에서 팝된 노드가 현재 노드라고 하면 현재 노드를 먼저 방문 처리하고 난뒤 현재 노드의 오른쪽 자식 노드와 왼쪽 자식 노드를 차례로 푸쉬한다. 저장된 노드가 더 없을떄까지 반복한다. (스택에 처음 푸쉬되는건 루트 노드다)

왜 오른쪽부터하냐고? 스택 특성떄문이다.나중에 추가된 자료가 먼저 반환되잖아.

반복 중위 순회는

좀 틀려...왼쪽 서브트리를 먼저 방문해야하니까..스택에 현재노드부터 왼쪽 서브트리 노드들을 차례로 푸쉬한다.

(왼쪽으로 막 내려간다!)

즉 또 스택의 후입선출 특성을 이용해서 현재 노드보다 왼쪽 서브트리가 항상 먼저 팝되게.. 

팝된 현재 노드를 처리하고 오른쪽 서브트리가 있는지를 확인하고 없다면 다시 하나더 팝하고..

만약에 오른쪽 트리가 있다면! 다시 앞서 작업을 반복..

즉, 오른쪽 서브트리를 시작으로 해당 노드의 현재노드부터 왼쪽 서브트리 노드들을 차례대로 푸쉬하는거임..

이햐 레벌순회다

레벨 순회는 선입 선출의 특성인 큐를 활용해야한다..

즉, 루트노드를 시작으로 각 노드의 왼쪽 서브트리와 오른쪽 서브트리를 큐에 인큐한다.

큐에는 이미 상위 레벨의 노드들이 인큐되어 있기 때문에 새로 인큐되는 하위레벨의 노드들은 기조 ㄴ상위 레벨의 노드 이후에 인큐되는것..

---

힙 구조 키값이 중복도 되네..

완전 이진트리여야 하는데 그 조건은 같이 높이가 h에서는 레벨 1부터 레벨 h - 1까지는 포화 이진트리와 마찬가지로 꽉 채워져있다가

마지막 레벨 h에서는 왼쪽에서 오른쪽으로노드가 채워져있는 이진 트리를 이야기한다.

즉, 마지막 레벨h에서는 노드가 왼쪽부터 차례로 채워져있어야 하며, 중간에 빈 노드가 발생해서는 안된다.(빈노드가 없다는게 중요하다!)

삭제는 O(logn), 추가도 O(logn)

---

이진 탐색트리는 이름에 탐색이 들어간것 처럼..자료의 검색이 주된 기능이다..

힙과는 다르게 이건 신속하게 찾는 것이 기본기능이다..

이건 중복없어..유일한 키를 가질뿐....

삭제할때 조건이 좀 있어..

일단 먼저 삭제하려는 노드를 찾고

1) 삭제하려는데 자식노드가 1개인경우

2) 삭제하려는데 자식노드가 2개인경우

3) 자식이 없는경우

3번은 그냥 삭제하면되 단말노드야,, 삭제 노드를 가리키는 부모만 NULL로 처리하면됨

1번은 해당 노드 삭제하고 삭제 노드의 자식 노드를 삭제 노드의 위치에 이동시켜야한다 링크들 설정하고..아 이떄도 당연히 왼쪽은 작고 오른쪽은 크고 특징이 유지됨

2번이 조금 복잡한데 단순히 자식 둘중에 하나를 올릴 순 없다.

일단 삭제되는 노드를 기준으로

왼쪽 트리에서 가장 큰값, 오른쪽 트리에서 가장 작은 키값이 후보가 될 수 있다. 그 후보들이 삭제되는 노드 자리에 가는거야

그래야지 전체적으로 이진트리의 특성이 유지된다고

보통은 왼쪽트리에서 가장 큰 값을 후보로하는데...좋아 했다고 치자 그런데 말이야..그 후보가 빠지면서 중간에 빈곳이 생길수도 있다.

물론 그 노드는 오른쪽 자식이 없다 왜냐면 왼쪽에서 제일 큰놈이니까..

만약에 중간에 빈곳이 생긴다면(왼쪽 자식이 있다는 소리랑 같다) 그 후보의 위치로 자식을 올린다.

(후보군을 오른쪽에서 했다면..뭐 대충 비슷해지겠지?)

왼쪽 트리에서 가장 큰 값찾기는 단순해 루트에서 왼쪽으로 간뒤에 계속 우측으로 가면되

---

그래프의 구현은 인접행렬(2차원 배열로 저장) 인접 리스트(연결리스트)로 구현할 수 있다.

인접 리스트는 정점별 인접 정점을 연결리스트로 저장하는 방식이다. (연결되는 노드를 연결리스트에 넣는것이다)

가중치가 있어야 한다면 각 연결리스트가에 저장될때 가중치가 같이 저장되어야 한다.