Develop & Dream

빅오 표기법(Big-O Notation)

• 알고리즘의 시간 효율성과 메모리 효율성을 나타냄
• 빅오메가 : 하한 점근, 최선의 경우 표기법
• 빅세타 : 상한/하한점근, 정확한 성능 표기법
• 빅오 : 가장 최악인 상황에서 최소 보장되는 성능, 효율성을 상한선 기준으로 표기(최악의 효율)
• 알고리즘 효율성은 값이 클수록, 비효율적임을 의미함
• 알고리즘의 실제 러닝타임이 아니라, 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 나타내는것
• 상수는 항상 제외한다 O(2n) 인경우 O(n)으로 표기해야 맞는것이다
  

성능 순서(오른쪽으로 갈수록 성능이 안좋음)

   O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(n³) < O(2ⁿ) 

HashSearch < Binary Search < Sequential Search < Quick Sort < 구구단 출력 함수 <Floyd-Warshall < 피보나치 수열

O(1) : constant time, 언제나 일정한 속도, HashSearch 

ex)

F(int[] n){

       return (n[0] == 0)? true : false;

}

// n의 크기에 상관없이 언제나 일정한 속도로 결과를 반환

가로축 : data의 크기

세로축 : 처리시간

데이터가 증가함에 따라 처리시간은 항상 일정한 것을 볼 수 있다

O(logN) : logarithmic time, 이진탐색(Binary Search)

ex)

F(k, arr, s, e){

       if ( s > e ) return -1;

       m = ( s + e ) / 2;

       if ( arr[m] == k ) return m;

       else if ( arr[m] > k ) return F(k, arr, s, m-1);

       else return F(k, arr, m+1, e);

}

// 이진 탐색

가로축 : data의 크기

세로축 : 처리시간

데이터가 증가하여도 처리시간이 크게 늘어나지 않는다

O(n) : linear time, n번만큼 동작하는 루프1개, sequential search

ex)

F(int[] n){

       for i = 0 to n.length

              print i

}

// n개의 data를 받으면 n번 만큼의 loop를 돌게된다, 즉 n의 크기에 비례해서 처리시간이 늘어남

가로축 : data의 크기

세로축 : 처리시간

데이터가 증가함에 따라 비례해서 처리시간도 증가함, 언제나 데이터와 시간이 정비례한다

O(nlogn) : log linear, Quick Sort

데이터가 증가함에 대해 처리 시간은 정비례보다 약간 더 많이 증가를함

가로축 : data의 크기

세로축 : 처리시간

데이터양에 따라 걸리는 시간은 제곱에 비례함

O(n²) : quadratic time, n번만큼 동작하는 이중 루프, 구구단 출력 함수

ex)

F(int[] n){

      for i = 0 to n.length

            for j = 0 to n.length

                      print i + j;

}

// n개의 data를 받으면 n번 만큼의 loop를 돌고 이것을 이중으로 함(이중루프)

가로축 : data의 크기

세로축 : 처리시간

데이터양에 따라 걸리는 시간은 O(n²)과 거의 유사하다

O(n³) : cubic time, n번만큼 동작하는 삼중 루프, Floyd-Warshall

ex)

F(int[] n){

     for i = 0 to n.length

          for j = 0 to n.length

              for k = 0 to n.length

                       print i + j + k;

}

O(2ⁿ) : exponential time, 피보나치 수열 

ex)

F(n, r){

      if (n <= 0) return 0;

      else if( n == 1) return r[n] = 1;

      return r[n] = F(n -1, r) + F(n - 2, r);

}

Array vs LinkedList

Array(배열)

1. 중간 삽입, 중간 삭제는 링크드 리스트에 비해서 어렵고 느림

2. 삽입할 때 마다, 메모리 동적 할당 삽입을 하지 않기 때문에, 데이터를 삽입하는 속도는 링크드 리스트에 비해서 빠름

3. 인덱스로 접근 가능 하므로, random access(무작위 접근, 비순차적 접근 가능), sequential access(순차적 접근) 할 필요 없음, 데이터의 위치에 관계없이 접근시간이 일정함

※random access : 무작위 접근, 임의 접근, 비순차적 접근 이라고도 함, 어떤 데이터를 기억장소에 기록하거나 거기에서 읽어 낼 때에, 기억 장소에 관계 없이 동일한 접근 시간이 걸리는 접근 방식

sequential access : 순차적 접근, 데이터를 순차적으로 접근하는 방식, 데이터의 위치에 따라 접근 시간이 달라짐

LinkedList(링크드 리스트)

1. 중간 삽입, 중간 삭제는 배열에 비해서 쉽고 빠름

2. 삽입할 때 마다, 메모리 동적 할당으로 삽입을 하기 때문에, 데이터를 삽입하는 속도는 배열에 비해서 느림

3. sequential access(순차적 접근) 만 가능, index 개념이 없음, random access 불가능, 데이터의 위치에 따라 접근 시간이 달라짐

Binary Search Tree(이진 탐색 트리)

• 이진 트리는 하나의 노드가 두개의 포인터를 가지고 있다

• 그중에서 이진 탐색 트리(binary search tree)는 이진 탐색과 연결 리스트를 결합한 자료구조라고 할 수 있다

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다

• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다

• 중복된 노드가 없어야 한다

• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색 트리이다

순회

트리의 모든 노드를 한 번씩 방문하여 모든 정보에 대한 선형 순서를 만들어내는 방법

전위순회(PreOrder Traversal) : Root를 가장 먼저 들린다

1. Root 를 방문

2. 왼쪽 Subtree 를 방문

3. 오른쪽 Subtree 를 방문

중위순회(InOrder Traversal) : Root를 중간에 들린다

1. 왼쪽 Subtree를 방문

2. Root를 방문

3. 오른쪽 Subtree를 방문

후위순회(PostOrder Traversal) : Root를 가장 나중에 들린다

1. 왼쪽 Subtree를 방문

2. 오른쪽 Subtree를 방문

3. Root를 방문

트리 노드 삭제 루틴

트리 노드를 삭제할시, 3가지 경우로 나뉜다

1. 하위 노드가 없는경우

   • 그냥 삭제 한다
      

2. 하위 노드가 하나만 있는경우(left 또는 right)

• 하위 노드를 삭제된 노드 자리에 앉힌다
   

•  

  

3. 하위 노드가 둘다 있는 경우

• 해당 노드가 head 루트 노드 보다 작으면 right node 를 삭제된 노드 자리에 앉힌다
• (해당 노드가 head 루트 노드 보다 크면 left node 를 삭제된 노드 자리에 앉힌다)
• 나머지 노드 left node를 새로 앉힌 노드의 left node로 맞춘다
• (나머지 노드가 right 노드 였던 경우 새로 앉힌 노드의 right node에 맞춘다)

순회 순서

위와 같은 이진탐색 트리가 존재할때

중위순회를 할경우

4,5,6,7,10,11,13,17,20 순으로 순회 한다 즉 그림으로 그리면

위와 같은 경로가 그려진다

모든 노드는 left, right, root 노드를 가지고 있으며, 각각 노드들이 또다른 어떤 노드의 루트 노드가 될 수 있다, 즉, 순회할수 있는 방향은 left, right, root 등으로 나뉘어지는게 어떤조건에서 어떤 경로로 이동하는 것일까?

일단 첫시작점을 이미 찾았다는 전제 하에서

가고자 하는 방향이 nullptr인 경우 무시하기로 한다

또한 순회하면서 나오는 값들은 이전값보다는 높아야한다

4 -> rightNode -> leftNode

5 -> rootNode

6 -> rightNode/ -> leftNode(nullptr)

7 -> rootNode -> rootNode-> rootNode (7 보다 높지않은 값들(6,4)을 거쳐서 10에 도달

10 -> rightNode->leftNode

11 -> rootNode

13 ->rightNode -> leftNode

17 -> rootNode

20 ->/rightNode(nullptr)

즉 위패턴으로 이터레이터 연산자 오버로딩 operator ++ () 을 구현할 경우

위와 같은 코드가 된다

그럼 반대 루틴을 보면

20 -> leftNode

17 -> rootNode -> rootNode

13 -> leftNode

11 -> rootNode -> rootNode

10 -> leftNode -> rightNode -> rightNode //m_pHead

7 -> rootNode

6 -> leftNode

5 -> rootNode -> rootNode

4

일단 시작은 leftNode로 간뒤 rightNode를 찾는다, 그리고 rightNode가 나오면 나올수록 계속 rightNode로 간다

그리고 rootNode->rootNode 가 되는 부분은 왼쪽으로 뻗은길을 찾기위한 반복되는 과정이라고 할수있다

즉 해당 노드의 데이터가 노드의 루트 데이터 보다 큰경우를 찾는것이다

즉 오른쪽으로 뻗은길이 나올때까지 이동한다

(pNode->iData > pNode->pRoot->iData)

또다른 트리를 통해 다시 한번 자세히 살펴보면 

4,10,11,13,26,27,28,29,30,31 를 노드로 가지고 있는 트리다 이걸 제일 큰값 31에서 제일 작은값 4까지

순회하는 로직을 그려보면 붉은 화살표와 같다

순회 동작 과정

31

처음 31에서 시작할때는 바로 root 데이터가 30이므로 (왼쪽으로 뻗은길)

30으로 한칸 이동하면 끝난다

30

30에서는 왼쪽으로 뻗은길이 있기떄문에 바로 13으로 갈수 있지만

30의 leftNode 자식이 있으므로(30보다 작고 13보다 큰수)

leftNode로 가야 한다

그렇게 해서 29로 이동한후 rightNode가 있는지(29와 30사이의 수) 파악하고 없으면 대기 한다

29

29에서도 마찬가지로 leftNode(27)로 이동

27에서 rightNode가 있는지 확인, 28 발견 했으므로 rightNode 로 이동한다

이때 주의할점은 rightNode로 한번 갈때는

가장 끝의 rightNode까지 이동해야한다는것이다

여기서 나오는 rightNode들은 27과 29사이의 수들이다

즉 가장끝 rightNode 일 수록 29에 가까운 바로 아랫수가 될것이다

그러나 28이 끝이므로 28에서 멈춘다

28

28은 leftNode가 없다 즉 root로 이동해야 하는데,

root로 이동할때는 왼쪽으로 뻗은길이면 한번만 이동하면되고

오른쪽으로 뻗은길이면 왼쪽으로 뻗은길이 나올때까지 계속 이동해야 한다

(28 > root->iData)조건을 만족할때까지

그런데 왼쪽으로 뻗은길 즉 28 은 root->iData 인 27보다 크므로

한번만 이동한다

27

LeftNode가 있으므로, leftNode로 이동

26에서 멈추고 rightNode가 있는지 확인, 없으므로 그자리에 대기

26

leftNode,RightNode 둘다 없으므로 아까처럼 root를 타야한다

그런데 오른쪽길로 뻗어있다 즉 (26 < pRoot->iData) 식이 되므로

26 > pRoot->iData 조건이 만족할때까지 계속 이동한다

그렇게 하면 27, 29, 30,(셋다 전부 26보다 크다) 거쳐서 13에 도착한다 ( 26보다 작은수)

즉 26보다 작은수가 나올때까지 계속 이동한것이다

13에서 대기한다

13

leftNode를 확인하고, 11이 있으므로 11로 이동, rightNode를 확인한다

그러나 rightNode가 없으므로 11에서 대기 한다

11

13에서 대기한다 leftNode, RightNode가 없으므로 root로 올라가는데 마찬가지로

왼쪽으로 뻗은길을 찾을때까지 계속올라간다, 그러나 바로 왼쪽으로 뻗으므로 13 > (pRoot->iData == 10)

바로 한칸 이동한다

10(phead)

head에 도달 이때도 마찬가지로 leftNode를 확인 4가 있으므로 4로 이동한뒤

rightNode를 확인한다

없으므로 ,4에서 대기한다

4

끝에 도달

그림으로 그리면 위와 같다,

위의 경로를 패턴화 시키면

아래와 같은 순서로 동작한다

1.LeftNode를 확인, LeftNode가 있는경우 이동

그리고 rightNode가 있는경우 가장 끝의 rightNode까지 이동

2.LeftNode가 없으므로 Root로 이동 이때

해당 노드 데이터가 root 데이터보다 큰경우가 올때까지 계속

root로 이동(왼쪽으로 뻗은길이 나올때까지 이동)

그래서 코드로 정리하면

위와 같은 코드가 나온다