항상 시간복잡도 다음에는 공간복잡도를 생각해야한다.
리스트 관련
리스트에서 머리 원소에 대한 추적
여기서 주의할것은 바로 bool insertInfront(IntElement **head, int data)
이런 함수에서 head가 계속 갱신이 되야 한다면 이중포인터로 넘겨야 한다. 그래야지 안에서 된다! 주의하자!
bool insertInfront(IntElement* head, int data)로는 안된다..지역변수만 바꾸기 때문에..Swap함수를 잘 생각해보자.
(만약에 멤버변수로 있다면 상관이 없겠지...)
리스트 종주(순회)
머리리스트가 아닌 다른 리스트 원소를 가지고 작업을 해야하는 경우도 있다. 연결 리스트의 첫 번째 원소가 아닌 원소에 대한 연산을 하려면
일부를 종주(순회)해야한다.
주의해야할것은 마지막 next의 null값 여부를 꼭 확인해야한다.
while(elem != null && elem.value() != data) 이런식으로 null과 data를 모두 비교해야한다는것..
리스트 삽입 및 삭제
만약에 단일 연결리스트에 있는 원소들 사이에 중간에 원소를 삽입하게 된다면..
그 앞 원소의 연결고리를 수정해야한다. 그 앞 원소의 연결고리를 알아낼 수 있는 방법은..리스트 순회를 해서 알아내는 방법밖에 없다..
만약 삭제라고 하면..
1. 들어오는 값들의 null상태 확인
2. 머리삭제인지 확인
머리 삭제면 머리를 삭제 다음값으로 바꾸고..삭제함
3. 머리삭제가 아니라면..
while(elem)
if(elem->next == 삭제할 노드)
이런식으로 비교를 해가며 순회한다.
한번에 모두 삭제하려면..
void deleteList(IntElement** head)
temp = *head;
while(temp != null)
{
temp2 = temp->next;
delete temp;
temp = temp2;
}
리스트로 스택 구현
배열로 구현된거나 리스트로 구현되거나 삽입은 연산이 O(c)로 같다 왜냐면..임의접근이 허용되지 않은 자료구조 이기 때문이다.
오히려 동적배열은 자료가 커짐에 따라서 크기가 조절되야하니까..안좋을 수도 있다.
배열 기반 Stack
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | /** * @file ArrayStack.cpp * @brief Stack implemented using array * @author velopert * @version 1.0 * @date 2016-04-13 */ #include <iostream> using namespace std; /* * Node Class */ class Node { public: int data; Node(int data); Node(); ~Node(); }; Node::Node(int data) { this->data = data; } Node::~Node() { cout << "deleting node (" << this->data << ")" << endl; } /* * Stack Class */ class Stack { public: int capacity; int top; Node** nodes; Stack(int capacity); ~Stack(); void push(int data); int pop(); bool isEmpty(); int getSize(); }; Stack::Stack(int capacity){ this->nodes = new Node*[capacity]; this->capacity = capacity; this->top = 0; } Stack::~Stack() { for(int i = 0; i < this->capacity; i++) { if(this->nodes[i]) { delete this->nodes[i]; } } delete[] this->nodes; } void Stack::push(int data) { this->nodes[this->top++] = new Node(data); cout << "push: " << data << endl; } int Stack::pop() { int data = this->nodes[--(this->top)]->data; cout << "pop: " << data << endl; return data; } bool Stack::isEmpty() { return (this->top == 0); } int Stack::getSize() { return this->top - 1; } /* * testing */ int main() { Stack stack(30); stack.push(1); stack.push(2); stack.push(3); cout << "size: " << stack.getSize() << endl; stack.pop(); stack.pop(); cout << "empty: " << (stack.isEmpty() ? "true" : "false") << endl; stack.pop(); cout << "empty: " << (stack.isEmpty() ? "true" : "false") << endl; } |
LinkedList 기반 Stack
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | /** * @file LinkedListStack.cpp * @brief Stack implemented using LinkedList * @author velopert * @version 1.0 * @date 2016-04-13 */ #include <iostream> using namespace std; /* * Node */ class Node { public: int data; Node* prevNode; Node(int data); ~Node(); }; Node::Node(int data) { this->data = data; } Node::~Node() { cout << "deleting node (" << this->data << ")" << endl; } /* * Stack */ class Stack { public: Node* topNode; int length; Stack(); ~Stack(); void push(int data); int pop(); int getLength(); }; Stack::Stack() { this->topNode = NULL; this->length = 0; } Stack::~Stack() { Node* top = this->topNode; while(top) { Node* old = top; top = top->prevNode; delete old; } } void Stack::push(int data){ if(this->topNode == NULL) { this->topNode = new Node(data); } else { Node* old = this->topNode; this->topNode = new Node(data); this->topNode->prevNode = old; } length++; cout << "push: " << data << endl; } int Stack::pop() { int data = this->topNode->data; delete this->topNode; this->topNode = this->topNode->prevNode; length--; cout << "pop: " << data << endl; return data; } int Stack::getLength() { return length; } /* * testing */ int main() { Stack stack; stack.push(1); stack.push(2); stack.push(3); cout << "length: " << stack.getLength() << endl; stack.pop(); stack.pop(); stack.push(4); stack.pop(); cout << "length: " << stack.getLength() << endl; stack.pop(); cout << "length: " << stack.getLength() << endl; stack.push(10); stack.push(11); stack.push(12); } |
리스트 문제를 풀때 가장 중요한것은.
처음 머리만 있을때, 자료가 없을때, 꼬리에 넣을때를 구분해서 함수를 작성해야한다..!!
트리에 대해서 확실하게 짚고 넘어가야한다. 트리가 이진트리인지 이진검색트리인지 물어봐야함..
삽입 삭제, 검색 모두 nlogn 혹시나 최악의 경우 o(n) 자식이 1개이라면
힙은 삽입, 삭제 nlogn 이고 검색은 상수시간이다.(가장 큰 또ㅡㄴ 작은 값이 루트이기 때문이다)
너비우선검색 : 탐색시간은 o(n) 큰트리에서는 못씀
각 층의 자식들을 저장해야하기 때문에..(그래야지 순회하니.. 메모리를 많이 사용하게 된다.)
깊이우선탐색 : 너비와는 다르게 모든 자식노드를 저장할 필요가 없어서 메모리 요구량이 훨씬 적다
종주(순회)
프리오더 : 전방순회
인오더 : 중위순회
포스트오더 : 후위순회
트리 같은건 회사 조직도나..등등 이런문제에..
그래프는 물이 흘러가는 것 같은거..결국 다돌아야하니까? 아 아닌데..
재귀적인 성질을 대신 쓸만한 자료구조 알고리즘은 데이터를 호출 스택에 집어넣는 식으로 스택 데이터를 사용하기 마련이다.
명시적으로 스택을 사용하면 재귀호출을 쓰지 않고도 똑같은 풀이를 만들어낼 수 있어야 한다.
배열을 이진균형트리로 만드는 방법은.
층 단위로 배치를 하면된다. 맨 앞에는 루트(트리의 가장 위층)가 놓이고 그 다음으로는 그 자식들(둘째 층)이 온다.
그리고 그 두자식의 자식들 (셋째층)을 배치한다. 너비우선 종주와 같은 순서라는데..
배열로부터 균형 힙을 구축하는데 핵심은 어떤 노드를 기준으로 그 자식의 상대적인 위치를 파악하는것.!!
즉 부모의 인덱스에 2를 곱하고 1을 더한 값부터 자ㅣㄱ의 인덱스가 시작된다.
즉..루트가 인덱스가 0이고
루트 인덱스 * 2 + 1은? 1이고.(왼쪽,) 루트 인덱스 * 2 + 2는? 2이고 (오른쪽)
AVL LL회전 RR회전 다시봐야할듯..
불균형 이진트리에 대한 해결책 문제가 나왔음..AVL로 풀어야함