학습(알고리즘)

1.단일연결은 이상하게 Class를 만든 후 메서드를 이용해 push, pop, shift, unshift, get, set, insert, remove, reverse를 만들었다. 기존과의 차이점은 index를 통한 배열의 기능들은 push, pop만 쉽고 unshift, shift는 idx의 재배치가 필요한데 여기서는 head부분만 교체해주면 끝이기 때문에 오히려 여기서는 pop보다 shift가 더 처리속도가 빠른 것 같다.
정리하면 삽입과 삭제의 경우는 단일연결노드가 유리하지만 임의 접근에는 idx값이 없기 때문에 불리한 면이 있다.
끝나고 생각해보면 만드는 것에 목적이 있는 것이 아니고 그 다음에 배울 스택의 이해도를 올리기 위해 실습하는 느낌이 강한 것 같다.

2.이중연결은 단일연결과는 다르게 이전으로 돌아갈 수 있는 차이점이 있으며 메서드를 만들어줄 때 이전으로 돌아가는 변수를 제거해야 한다는 주의점이 있다.
이중연결은 끝점에서 역으로 추적해 갈 수 있다는 메리트가 있기 때문에 배열과 단일연결의 중간점의 검색속도를 가지고 있다. (특히 끝점에 가까울수록 단일연결보다 유리하다.)
이중연결은 단일연결과는 다르게 실제로 사용되기도 하는데 일반적으로 페이지의 이동(방문기록)등에서 뒤로가기, 앞으로가기 등을 이중연결로 다룬다.

3.스택은 LIFO규칙을 따르는데 Last In First Out으로 후입선출법으로 나중에 들어온 것이 먼저 나간다.
배열의 기본 기능인 push와 pop을 통해서 간단하게 스택을 사용할 수 있다. 물론 unshift를 통해 데이터를 추가했다면 shift를 통해서 데이터를 제거해야 후입선출의 규칙에 맞다.
하지만 스택의 후입선출 규칙만 이용하려면 앞에서 배운 단일연결을 이용하는게 데이터면에서 절약된다.(idx를 저장하지 않아도 되기 때문에) 다만 단일연결에서는 push보다 shift의 비용이 더 저렴하기 때문에 push와 pop이라고 하고 shift와 unshift를 이용해서 구현한다.

4.큐는 FIFO규칙을 따르는데 First In First Out으로 선입선출법으로 처음에 들어온 것이 먼저 나간다. 선착순, 번호표와 유사한 느낌으로 볼 수 있다.
큐는 push, pop만으로 해결할 수 없기 때문에 직접 단일연결리스트로 만들어 주는 것이 훨씬 유리하다. idx값 정도의 비용차이가 나던 스택과는 다르게 큐는 shift 또는 unshift중 하나를 이용해야만 하는데 배열에서는 O(N)의 시간복잡도를 작업마다 가지지만 단일연결의 push와 shift는 모두 낮은 비용(O(1))을 가지고 있기 때문에 데이터의 규모가 크다면 직접 메서드를 만들어 주는 것이 성능 면에서도 압도적이다.

5.트리에는 다음과 같은 용어들이 있다.

Root - 트리의 최상단(시작점)으로 단 하나만 존재해야한다.
Child - 트리에 존재하는 노드의 바로 아래에 연결된 노드(자식노드)를 의미한다.
Parent - 자식 노드와 연결된 바로 위의 노드(부모노드)를 의미한다.
Siblings - 부모가 같은 자식들의 집합(형제노드)를 의미한다.
Leaf - 자식이 없는 최 하위 자식노드를 의미한다.
Edge - 노드의 관계를 나타내는 화살표를 의미한다.

 

트리는 이전에 배웠던 Dom Tree, CSS Tree, virtual Dom Tree 등 익숙한 트리구조등과 인공지능, 심지어는 컴퓨터의 폴더관리? 등에도 사용된다.

6.이진탐색트리는 아래와 같은 조건을 가지고 있는 트리로 검색에 엄청난 이점을 가지고 있다.

 1.자식의 숫자는 둘을 초과할 수 없다.
 2.노드의 좌측(자식노드)는 부모노드보다 작은 숫자여야 하며 우측(자식노드)는 부모노드보다 큰 숫자만 들어갈 수 있다.

이진탐색과 유사하게 루트(이진에서는 중앙값)에서부터 비교해서 중앙값보다 작은 경우 왼쪽 큰 경우 오른쪽의 단순한 반복을 통해 남은 조회숫자를 1씩 줄여나가는 것이 아니라 반씩 줄여나갈 수 있는 기법이다.

 

주말에 강의를 다 들으려고 하다보니 반 강제적으로 일정 이상의 강의를 들어야 했는데 중간에 이런저런 대화도 하고

단일,이중구조에서 시간대비 너무 많은 강의(단일구조 20강, 이중연결 19강)가 내부에 들어있어 학습할 내용이 더 많은 느낌도 들었다.

 

벌써 5시가 되어버렸는데 과연 내일 클래스3을 위한 마지막 한문제를 더 해결할 수 있을지는 모르겠다..