대엉코딩

1. 배열

- 연속된 메모리 상에 위치 (배정) 된다.

- "시작주소 + (자료형의 크기) * INDEX " 를 통해서 접근이 가능하므로 배열의 이름과 INDEX만으로 쉽게 접근

    이 가능하다. (매우 큰 장점)

- 크기와 자료형을 지정해주어야 한다.

- 동적배열로 어느정도 해결이 가능하지만, 배열이 최대크기를 넘어설 때는 Array Doubling이 발생하는데 

- 두배 크기의 배열이 선언되고, 기존의 데이터들을 새로운 두배크기의 배열로 모두 옮겨야 하므로 O(n) 시간이 소요. 

-(여담으로 수업을 들을 당시에 그럼 n크기의 배열에서 계속 삽입,삭제,삽입,삭제가 일어나면 계속 새로운배열이 생기고

  시간이 오래걸리는 것 인가? 라는 질문이 있었는데, 데이터의 개수가 n+1이 되어서 2n짜리 배열을 선언해서 옮겼을 

  때, 삭제연산이 일어나서 다시 n이 되었을 때 바로 다시 크기가 n인 배열로 옮기진 않는다고 한다. 보통은 n/2 정도가 

  되었을 때 옮긴다고 한다.)

- 탐색, 삽입, 삭제

   (1) 탐색

     -> 원하는 위치가 존재할 경우 index로 바로 접근이 가능하다 (O(n))

     -> 특정한 value를 찾고 싶을 때는 앞쪽부터 탐색하므로 O(n)

    (2) 삽입

      -> 특정위치에 삽입한다면 그 위치부터 끝쪽 까지 위치하던 데이터 들을 모두 한칸씩 미뤄야 하므로 (O(n))

      -> 맨 뒤에 삽입일 경우 옮길 것이 없으므로 빠르지만, 최악의 경우는 맨 앞쪽에 삽입할 경우 이므로 n-1개를

          옮겨야 할 수도 있다.

    (3) 삭제

       -> 삭제된 위치로 부터 뒤에 있는 데이터들을 모두 앞쪽으로 한칸씩 당겨주어야한다. (삽입과 같은 맥락)

- 배열은 메모리상에 연속되게 위치하기 때문에 크기가 큰 배열을 선언하려고 할 경우 남은 공간의 합은 충분하더라도

- 연속된 공간이 확보되지 않을 경우 메모리 할당을 못 받을수도 있다.

2. 연결리스트( 링크드 리스트)

- 단순 연결 리스트 (simple linked list)와 이중 링크드 리스트(doubly linked list)가 존재

- (단순 연결 리스트)  - HEAD Pointer를 통해서 접근

- (이중 연결 리스트)  - HEAD,TAIL을 통해서 접근

- 위의 그림과 같이 연결리스트는 연속된 메모리 공간에서 존재하지 않고 다음 테이터를 가리키는 포인터를

- 통해서 다음 원소에 접근한다.

- 연속된 공간이 필요하지 않고, 크기를 미리 지정해줄 필요도 없다.

- 반면, 다음원소를 가리키는 포인터에 대한 공간낭비 (오버헤드)가 발생한다.

- 심한경우를 예로 들자면 char형을 저장하려고 하는 경우 실제 데이터는 1byte인데

- 이중 연결리스트로 구현할 경우 prev와 next에 해당하는 포인터들이 각각 4byte씩 이므로 총 9 byte를 차지 하게 된다.

   (하나의 노드 당) -- 이는 배보다 배꼽이 더 큰 격이다.

- 탐색, 삽입, 삭제

  (1) 탐색

    - 포인터를 따라서 찾아가야 하므로 탐색시간이 오래 걸린다. (O(N)

  (2) 삽입

     - 간단하다. 탐색이 끝난 상태(탐색은 오래걸림)라면 넣고자 하는 위치의 이전 노드의 next 포인터가 해당데이터를            가리키도록 수정하 고, 해당 데이터의 next 포인터가 원래 이전노드가 가리키던 다음 노드를 가리키도록 설정만             해주면 된다.

        (싱글 링크드 리스트일 경우. 이중을 경우 prev,와 next에 해당되는 포인터 모두를 수정)

     - 단순 연결리스트의 경우 head를 통해서만 접근하므로 앞 쪽에 데이터(노드)를 추가하는 것은 빠르다.

     - 이중 연결리스트의 경우 tail을 통해서도 접근이 가능하므로 앞,뒤쪽에 데이터(노드)를 추가하는 것은 빠르다.

  (3) 삭제

     - 삭제 역시 삽입과 마찬가지로 간단하다.

     - 이전 의 노드의 next 포인터를 다음 노드를 가리키도록 수정해 주면 된다.

        (싱글 링크드 리스트일 경우. 이중을 경우 prev,와 next에 해당되는 포인터 모두를 수정)

3. 배열과 연결리스트의 간단정리.

- 배열을 사용할 경우 index를 통한 접근이 간편하며, 이는 큰 장점이다

   저장할 데이터 수가 어느정도 정해져있고, 데이터들을 중간에 삽입,삭제가 많지 않을 떄 좋다.

  연속된 메모리 공간을 요구한다.

- 연결리스트를 사용할 경우, 데이터의 개수에 제한이 없고 , 연속된 공간의 메모리를 필요로 하지 않는다.

  데이터의 삽입, 삭제가 빈번하고 상대적으로 어떤 위치의 데이터에 대한 탐색이 적을경우 좋다.

  포인터에 대한 오버헤드가 발생한다.

1. 트리[Tree] 란?

- computer science에서 계층구조(hierarchical structure)를 가진 추상자료형

- 트리는 노드로 구성되어 있는데, 노드들은 부모-자식 (parent-child)관계를 가진다.

- 직장에서 부장-과장(1,2,3)-(대리1,2,3,4,5,6) 이 업무연관성에 따라 그려진 조직도를 떠올려보면 좋다.

- File System, Programming enviroment 등에서 사용된다.

2. 용어(Terminology)

- Root (node) : parent가 없는 노드

- Internal node : 적어도(at least) 자식을 하나이상 가지는 노드

- External node : 자식이 없는 노드

- Ancestors of a node(a) : node(a)의 parent,grand parent, grand-grandparent........etc

- Depth of a node(a) : number of ancestors (조상노드의 수)

- Height of a tree(a) : maximum depth of any node (가장 큰 깊이를 가진 노드의 깊이가 트리의 높이)

- Descendant of a node : child, grandchild, ..... etc

3. Method

-기본적인 methods 

-(1) Generic methods

     - int size()

     - bool empty()

-(2) Accessor methods

     - position root()

     - listh<position> positions()

-(3) Position-based methods

     - position parent()

     - list<position> children

-(4) Query methods

     - bool isRoot()

     - bool isExternal()

4. 탐색(순회)

- 트리 자료구조를 탐색하는 방법은 많지만 여기서는 기본적인 2개만 다루겠다.

-(1) 전위순회

     - descendants들을 방문하기 전에 자신의 노드부터 방문처리 하는 것이다.

-(2) 후위순회

     - descendants를 먼저 방문하고 자신을 마지막에 방문처리하는 것이다.

 ** 그래프

 - 정점들간의 관계를 표현하는 자료구조 ( G=(V,E) )

 - V는 Vertex(정점) 과 E는 Edge(간선) 을 의미하며 간선은 정점들 간의 연결관계를 표시합니다.

 - 간선 edge는 두 개의 정점이 있어야 정의가 됩니다 (cycle을 가지지 않을 경우)

 - directred graph(유향그래프) 와 undirected graph(무향 그래프) 가 있으며

 - 유향그래프에서는 vw와 wv는 다른 방향을 가지므로 다른 간선이다.

 - 가중치 그래프(weighted graph) 의 경우 (V,E,W)로 구성

 ** 그래프의 용어

 - 정점(Vertex) : 연결된 객체 (node)

 - 간선(Edge) : 정점들 간의 연결관계를 나타내는 선

 - incident : 정점과 간선의 관계에서 쓰는 용어 (정점에  간선이 연결된 경우)

 - adjacent : 정점과 정점간의 관계에서 쓰는 용어 (정점과 정점이 간선에의해 직접적으로 연결되어있는 경우)

 - 사이클(cycle) : 경로의 시작 정점과 끝 정점이 같을 경우

 - 차수(degree) : 정점에 연결되어 있는 간선의 수를 그 정점의 차수 라고 한다.

 ** 그래프의 구현

 - 보통 인접리스트로 구현을 하여, 인접 행렬으로도 구현 가능하다.

 - 인접행렬로 구현을 할 경우 두 정점이 직접 연결되어있는지 (adjacent) 를 O(1) 에 바로 알아낼 수 있다.

 - 그러나 어떤 특정 정점에 인접한 모든 정점들을 탐색하거나, 그래프의 간선의 수 등을 알아내려면

    O(n*n)이 걸린다 matrix를 모두 조사해야하므로....

 - 인접리스트로 구현할 경우 어떤 정점에 인접한 노드들은 바로 찾을 수 있다는 장점이 있다.

 ** 그래프의 탐색

 1. 깊이우선탐색(DFS, Depth-First-Search)

     - 정점을 탐색을 하는데 다음 연결된 정점을 탐색하기 전에 첫 정점과 연결된 정점을 우선 탐색

     - 모든 노드를 다 탐색하고자 할 경우 자주 사용한다.

     - 특정 정점에서 시작하여 원하는 다른 정점까지 경로가 있는지를 탐색할 때 사용하기도 한다.

 2. 너비우선탐색(BFS, Breadth-First-Search)

     - 탐색 시작 정점으로 부터 연결된 모든 정점을 먼저 탐색을 한 후 그 탐색한 정점과 연결된 다른 정점들을 탐색

     - 보통 최단경로를 찾는 문제에 BFS를 많이 사용한다.

     - 큐를 이용하여 구현을 많이 하는데 탐색정점과 연결된 정점들을 큐에 넣어서 탐색을 해가면서

     - 탐색한 정점은 큐에서 POP하고 그 정점에 연결된 새로운정점들을 큐에 PUSH해 준다.

     - 탐색을 시작할 때의 큐의 SIZE만큼 탐색을 하면 탐색 후에는 직접적으로 연결된 정점들은 모두 POP되었을 것이고

       탐색을 했던 정점들과 연결된 새로운 정점들이 큐에 들어와 있다.

* 벡터(Vector) 란 ?

- 배열의 확장 느낌으로서 시퀀스 컨테이너의 대표적인 자료구조이다.

-  동적배열과 유사하다

- 자료들(data)가 구조적으로 인접한 위치에 있기 때문에 접근이 쉽고 메모리를 효율적으로 관리가능하다

- 배열과 같이 index를 통한 요소(data) 접근이 가능하다 .(매우 편리, 접근이 용이)

- 만약 맨뒤에 삽입이 아닌 맨 앞이나 중간, 임의의 위치 등에 삽입을 하려고 하는 경우 다른 요소들도

  재조정을 해야 하기 때문에 느리다 (비 효율적)

- 임의의 위치에 삽입, 삭제 등이 많이 일어나는 경우 벡터보다는 리스트를 활용하는것이 효과적이다.

* 벡터 ADT

- at( x ) (index가 x인 위치의 자료형 리턴)

- set(int x, object o) (index x의 위치에 o라는 객체 assign)

- insert(int i, object o) (index i의 위체서 o라는 객체 삽입)

- erase(int i) (index i에 있는 객체 삭제)

- size() (vector 의 사이즈 리턴)

- empty() (비어있는지 확인 -bool)

- push_back(object o) (vector 맨 끝에 삽입)

* ADT 시간복잡도 분석

- at(i),  set(i,0)   ----> O(1) ( vector는 index로 접근 가능 하므로 at, set은 모두 직접 접근하여 O(1) 타임에 가능하다.

- insert(i,o)  ----> O(n) (임의의위치 i에 자료를 삽입하는 경우 원래의 i위치 부터 끝까지 있던 자료들을 모두 한칸씩 뒤로 밀린다.)

-erase(i)  ----> O(n) (역시 비슷한 느낌입니다 ---앞으로 땡겨줘야함 )

* 벡터 활용의 예

- 정렬된 객체들의 집합들을 관리 해야할 때

* 벡터의 구현

<잘못된 부분이 있을 수 있습니다>

<알려주시면 수정 하겠습니다>

기본 크기를 64(index) 로 하고 만약 입력을 받다가 이크기를 넘어가게 되면

배열의 크기를 두배로 늘리고 기존의 자료구조들을 모두 옮기는 식으로 구현하였습니다.

* 큐(queue) 란 ?

- FIFO(First In Fisrt Out)

- 편하게 생각해보면 맛집에 줄 서있는 사람들을 떠올리면 될것이다.

  (먼저 줄을 선 사람 순서대로 식당에 들어간다.)

- 그외에 번호표, 버퍼(buffer) 도 같은 개념이라고 보시면 되겠네요 !

* 큐의 연산

- 삽입, 삭제, 비어있는지 확인, 맨 앞 (front) 확인,끝(rear) 확인 크기 등의 연산이 있다.

- 객체 : 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : enqueue(x)

           dequeue()

           front()              

           rear()

           peek() -> front에 위치한 데이터 확인

           empty()

- 시간 복잡도: (배열을 통한 구현으로 생각해보겠습니다.)

                   enqueue의 경우 배열 맨 끝에 추가하면 됩니다. O(1)

                   dequeue의 경우 배열의 앞에서 빼고 다른 요소들을 모두 하나씩 당기는 방식으로 구현할 경우 O(n)

                                         (이경우 front는 무조건 index가 0일 것이므로 따로 index변수를 관리 할 필요가 없겠죠)

                                         배열의 앞에서 빼고 front index를 따로 관리하여 +1만 해주는 경우 O(1) - 효율적

                   그 외 front(), rear(), peek() 등의 연산들은 index를 관리해줄 경우 모두 O(1) 타임 이겠죠?

* 큐 구현상의 문제점

                   만약 index를( 따로 front와 rear 를 가리키는) 관리해주는 방식으로  (효율적)

                   그럴 경우 배열의 크기는 정해져 있다는 것을 생각 해보면 계속 enqueue와 dequeue 작업을 수행하면

                   계속 뒤로 밀려지게 되다가 결국 배열의 크기를 넘어 가게 되면 오류가 발생하게 될 것 입니다.

                   이 때는 환형 배열을 이용 하면 이 방식의 문제를 해결할 수 있습니다.

                   만약 자료가 많아서 배열을 모두 채울경우 배열의 크기를 두배로 늘려서 다시 모든 요소들을 새로운

                   큰 크기의 배열로 옮겨주고 수행해야 하는 경우 enqueue 는 O(n) 타임이 걸릴 것입니다.

                   만약 연결리스트(링크드 리스트)로 구현할 경우 이러한 문제는 해결 할 수 있을것입니다.

                   하지만 링크드 리스트로 구현할 경우 코드상의 즉 런타임시간에 동적할당을 자주 해야 할것이고

                   이로인해 성능이 배열을 통해 구현한 순환큐 보다는 성능이 떨어질 수도 있습니다.

                   그러므로 만약 큐(자료)의 크기가 어느정도 예측이 가능할 경우 배열을 통한 순환큐가 

                   더 적절한 상황이 나타날 수 있습니다.

* 큐 활용의 예

(큐의 특성을 생각해본다면 매우 많겠죠???)

- 프린트기

- 너비우선탐색(bfs)

- 은행업무

- 그외 등등

* 큐의 구현

< 배열 이용한 구현>

* 스택이란 ?

- LIFO(Last In First Out)

- 떠올리기 쉬운것은 주방에 쌓여있는 식기를 놓으면 좋다. 

- 설거지를 해서 위에 쌓으면 사용을 할 때는 위에서 부터 하나씩 가지고 간다.

* 스택의 연산

- 삽입, 삭제, 비어있는지 확인, 상단 확인, 크기 등의 연산이 있다.

- 객체 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : push(x)

               pop()

               size()              

               peek() -> 스택 상단에 위치한 요소를 반환(봄) (스택이 비어있지 않으면)

    시간복잡도 : size()를 제외하고는 모드 O(1)이라고 할수 있습니다.

                            size()는 어떻게 구현하느냐에 따라 다를 수 있습니다.( 배열이나 연결리스트)

- 말이 나와서 하는 것이지만 추상자료형 (Abstract Data Type)은 사실 어떻게 구현하느냐는 사용자는 알 수 없습니다.

   제가 배웠던 것을 항상 떠올릴 때는 문 밖에서 어떠한 입력을 넣고 요구를 하면 안에서는 어떤식이던지 구현을 하여

   정확한 결과만을 문 밖으로 다시 보내주는 것 입니다. 사용자는 결과를 받지만 내부에 어떤식으로 이를 처리 하였는지는

   알 수 없지요

* 스택 활용의 예

- 문서나 그림, 수식 등의 편집기에서 되돌리기 기능

   (최근 사용했던것 부터 다시 되돌리기를 합니다. -스택을 사용하면 편하겠죠????)

- 함수 호출에서 복귀주소 를 기억 할 때

   (예를 들면, main 함수에서 작업을 수행하다가 다른 함수를 호출해서 그 함수로 이동한다고 하면

     그 함수가 끝나고 났을 때 다시 main 함수로 돌아와서 그 다음 작업을 진행 하여야 합니다.

     그럼 그때 복귀주소를 스택에 넣어 놓습니다.)

- main에서 function A를 호출하고 function A에서 function B 를 호출 한다고 가정을 한다면????

    (스택에 우선 main으로 돌아오기 위한 복귀 주소가 먼저  push될 것입니다. 그다음 function A로 가고

      function B가 수행될 때 function A로 돌아오기 위한 복귀 주소가 그 위에 삽입 될 것 입니다.

      function B가 끝나면 스택에서 맨위 (TOP)을 pop해서 function A 나머지를 수행하고 다시 POP 을

      하면 main함수로 돌아올 수 있습니다.)

* 스택의 구현

 - 1. 배열을 이용

 - 2. 연결리스트를 이용

   직접 구현은 하지 않았지만 연결리스트를 사용하면 처음에 스택 사이즈를 지정 해 줄 필요도 없을 것입니다.

     배열을 이용해서 연결리스트 처럼 구현을 하려면 사이즈를 넘어 갈경우 max사이즈를 두배로 증가시켜서

     다시 배열을 만들고 모든 요소들을 새로운 배열로 이동시키고 원래 배열을  delete 시키고 하는 그런 복잡한

     작업을 해야할 것 입니다. 

링크드 리스트는 노드의 sequence로 구성된 data structure 이다.

즉 노드들이 선형적으로 순서화된 형태의 집합체 이다.

싱글링크드 리스트의 경우 각 노드 들은다음 노드를 가리키는 next 포인터를 포함하고 있으며

물론 자신의 자료도 저장하고 있다.

싱글 링크드 리스트의 경우  처음노드와 마지막 노드 를 가리키는 head와 tail을 가지고 있다.

그리고 링크드리스트는 고정된 크기를 가지고 있지 않고

노드를 추가하거나 삭제함으로써 사이즈를 자유롭게 조정 할 수 있다.

밑의 내가 구현한 싱크드 리스트의 코드의 경우  tail에 삽입 삭제를 하게끔 설정하고 구현하였는데

싱글 링크드 리스트의 경우 prev를 가리키는 포인터가 없으므로

tail에서 삭제하기 위해서 새로운 임시 포인터 tmp를 선언한후 head부터 차례대로 따라가서 tail의 바로 앞

노드를 찾아서 삭제하게끔 구현 하였다 ( O(n) 시간이 걸리겠죵?)

삽입은 O(1)이라고 할 수 있겠네요.!