자료구조 기초

Stack And Queue

- 가장 기본적인 자료구조

- Stack

    ㆍLIFO ( Last In First Out )

    ㆍ비어있는 Stack 에서 데이터를 pop할 때 발생하는 오류는 Stack Underflow

    ㆍStack의 최대 사이즈가 넘어가면 Stack Overflow

    ㆍStack의 구현방법

         ㆍArray or LinkedList 로 구현

         ㆍ두 개의 차이점 : Array는 top에 바로 접근 가능하지만

                                       Linked List는 마지막 데이터에 접근하기 위해 모든 데이터를 거쳐야함

    ㆍStack의 활용

         ㆍ웹 브라우저 방문기록, 역순 문자열 만들기, 수식의 괄호 검사, 메모리의 Stack 영역, Undo ( 실행 취소 )

         ㆍ메모리의 Stack 영역에 대한 개념 필요 : 지역 변수, 매개변수(parameter) 저장

    ㆍ왜 Stack Overflow 가 발생할까? : 재귀함수 무한호출, 너무 큰 지역 또는 매개변수

 

- Queue

    ㆍFIFO ( First In First Out )

    ㆍFront, Rear 개념 : Front로 들어와서 Rear로 반출

    ㆍQueue의 활용

         ㆍ우선순위가 같은 작업의 예약 ( 스케줄링 기법으로도 사용)

         ㆍBFS ( 너비 우선 탐색 ) 알고리즘에 사용

 

- 비어있는 스택 참조 경우?

  : 스택이 비어 데이터가 없는데 데이터를 참조하는 경우 Stack Underflow 발생할 수 있음

    스택이 수용범위까지 가득찼는데 데이터 푸시하는 경우 Stack Overflow 발생

 

- 스택은 언제 활용할까?

  : 하나의 프로세스가 동작할때 할당되어 함수를 참조할 경우 함수 코드가 마칠 때 돌아갈 코드의 위치를 스택에 쌓아둠

     가장 마지막으로 실행된 함수가 돌아갈 리턴될 위치 필요

 

Graph & Tree & Heap

- 3개가 비슷하면서도 다른 것 같지만 연관성이 있음

- Graph

    ㆍNode (vertex) 와 Edge로 구성

    ㆍ주로 Tree와 차이점 및 사용 예시, 특징 그리고 탐색방법 ( BFS, DFS ) 에 대해 질문

    ㆍ간선에 Weight에 대한 개념 숙지 필요

    ㆍTree와 비교

         ㆍGraph는 방향성이 존재할 수 있고, 아닐 수도 있음 ( Tree는 일종의 Directed Graph )

         ㆍRoot node 개념이 존재하지 않음 ↔ Tree는 시작점인 Root node 존재

         ㆍ부모 자식 개념이 존재하지 않음 ↔ Tree는 부모 자식 개념 존재

    ㆍDFS ( 깊이 우선 탐색 )

         ㆍ모든 노드를 방문하고 싶을 때 사용

    ㆍBFS ( 넓이 우선 탐색 )

         ㆍ두 노드 간의 최단 경로 또는 임의의 경로 탐색

    ㆍ사용 예시 : 도로 길찾기, 지하철 노선도 등 → 어떤 탐색 방법?

 

- Tree

    ㆍTree는 Binary Tree, Binary Heap ( Min Heep, Max Heap ), Binary Search Tree 등이 있음

    ㆍBinary Tree : 자식 노드를 2개만 가지는 Tree >> 트리 순회 알고리즘 알기

    ㆍBinary Search Tree

         ㆍ'모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들' 조건을 만족하는 Tree

         ㆍ활용 예시 : 사전 탐색 // Up & Down 게임도 일종의 위의 개념을 활용

                              ( 단어가 1000개 있는 사전에서 특정 단어를 찾으려고 하면 최대 몇 번만에 탐색이 가능할까? )

 

- Heap

    ㆍ완전 이진 트리( Complete Binary Tree )의 일종으로 우선 순위 큐(Priority Queue)를 구현하기 위해

        만들어진 자료구조

    ㆍPriority Queue 란?

        : 앞에서 배운 Queue는 먼저 들어온 데이터가 가장 먼저 반출되는 구조라면 Priority Queue는 데이터에 우선순위를

          부여해서, 우선순위가 높은 순서대로 나가게 만든다.

    ㆍPriority Queue를 활용하는 예시 → OS 스케줄링 → OS 스케줄링 중 어떤 상황에서 사용? → SJF(Shortest Job First)

    ㆍ왜 그럼 Heap이 Priority Queue를 구현하는데 사용되는가?

        : 다른 자료구조들(Array, Linked List)은 데이터 삭제에는 O(1) 효율을 보이나 삽입의 경우에는 O(n)으로

          효율이 떨어진다. 하지만 Heap은 둘 다 O(log n)으로 구현이 가능

    ㆍHeap에 데이터가 들어가거나 삭제하는 순서에 대해서도 알고 있으면 직접 손으로 써보라고 할 때 유리

    ㆍMax Heap & Min Heap

    ㆍ자식 node의 key 값이 부모 node의 key 값보다 작거나 큰 기준으로 구현된 완전 이진 트리