공상개발

상상 박스

Computer Science/Data Structure

BFS 1. BFS(Breadth-First Search : 너비 우선 탐색) 시작 정점으로부터 가까운 정점들을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법. 방문한 정점과 인접한 정점들 중 방문하지 않은 정점을 큐(FIFO)에 삽입. https://commons.wikimedia.org/wiki/File:Animated_BFS.gif File:Animated BFS.gif - Wikimedia Commons No higher resolution available. commons.wikimedia.org 노드를 넓게 탐색한다. BFS는 시작 정점으로부터 다른 정점까지의 간선의 수를 최소로 하는 경로를 구한다. # BFS 활용 사례 라우팅(routing) : 통신망에서 홉 카운트를 최..

2021. 5. 26.

Computer Science/Data Structure

DFS 1. 탐색 그래프의 탐색은 하나의 정점에서 시작하여 모든 정점들을 간선을 따라 한 번씩 방문하는 것을 의미합니다. 주로 트리, 그래프와 같은 자료구조에서 데이터를 탐색할 때 사용됩니다. 이번 시간에는 대표적인 그래프 탐색 방법인 DFS(Depth First Search)에 대해 알아보겠습니다. 2. DFS(Depth First Search : 깊이 우선 탐색) DFS는 시작 정점을 방문한 후, 인접한 정점들 중 방문하지 않은 정점을 다시 시작 정점으로 하여 재귀적으로 탐색을 합니다. DFS 알고리즘 특징 루트 노드나 임의의 노드에서 시작하여 더 이상 진행할 길이 없을 때까지 찾아가면서 탐색. 만약, 진행할 길이 존재하지 않는다면 이전의 위치로 돌아와 찾아가지 않은 길로 뻗어 나가며 탐색. DFS는..

2021. 5. 24.

Computer Science/Data Structure

안녕하세요. 공상 개발입니다. 이번 시간에는 우선순위 큐(priority queue)와 힙(heap)에 대해 알아보는 시간을 갖겠습니다. 1. 우선순위 큐 (priority queue) 개념 2. 힙(heap) 개념 3. upheap, downheap 연산 4. LPT(longest processing time first) # 우선순위 큐 (priority queue) 개념 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조입니다. 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다. 응용분야 : 네트워크 트래픽 제어, 운영 체제에서의 작업 스케줄링. 자료구조 삭제되는 요소 스택 가장 최근에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위큐 가장 우선순위가 높은 ..

2021. 3. 2.

Computer Science/Data Structure

안녕하세요. 공상 개발입니다. 지난 시간에 이어 트리(Tree)에 대해 마저 알아보는 시간을 갖겠습니다. 1. 이진 탐색 트리 2. 탐색 연산 -구현 방법 3. 삽입 연산 4. 삭제 연산 5. 성능 분석 # 이진 탐색 트리 이진 탐색 트리(binary search tree)는 탐색 작업을 효율적으로 하기 위한 자료구조입니다. key(왼쪽서브트리) ≤ key(루트노드) ≤ key(오른쪽서브트리) 구조입니다. 위의 수식을 말로 풀어 본다면, "왼쪽 서브 트리의 키들은 루트의 키보다 작으며, 오른쪽 서브 트리의 키들은 루트의 키보다 크다"입니다. 이진 탐색 트리의 정의를 보여주는 이미지로 예시를 확인해보겠습니다. 또한 이진 탐색를 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있습니다. # 탐색 연산 탐색 ..

2021. 2. 25.

Computer Science/Data Structure

안녕하세요. 공상 개발입니다. 오늘은 트리(Tree)에 대해 간단히 알아보는 시간을 갖겠습니다. 1. 트리(Tree)란? 2. 트리의 용어 3. 트리의 종류 - 이진 트리(Binary Tree) - 이진 트리의 분류 - 이진 트리의 표현 4. 이진 트리의 순회 5. 레벨 순회 (level order) 6. 이진 트리 연산 1. 트리(Tree)란? 트리(TREE) 리스트, 스택, 큐 등은 선형 구조 트리 : 계층적인 구조를 나타내는 자료구조 자료구조에서는 부모-자식 관계의 노드들로 구성되어 있는 구조를 트리라고 부릅니다. 응용 분야로는 1. 계층적인 조직 표현 2. 컴퓨터 디스크의 디렉터리 구조 3. 인공지능에서의 결정 트리(decision tree) 등이 있습니다. 2. 트리의 용어 노드(node): 트..

2021. 2. 23.

Computer Science/Data Structure

안녕하세요. 공상 개발입니다. 이번 시간에는 저번 연결 리스트(linked list) 리뷰를 이어서, 원형 연결 리스트(Circular Linked List)와 이중 연결 리스트(Doubled Linked List)에 대해 간단히 알아보는 시간을 갖겠습니다. 2. 원형 연결 리스트(Circular Linked List) 2.1 이중 연결 리스트(Doubled Linked List) 3. 연결 리스트(Linked List)로 구현한 큐(Queue) 프로그램 *Data Structure - linked list(Vol.1)을 먼저 읽어보시는 걸 추천합니다. 2. 원형 연결 리스트(Circular Linked List) 큐와 마찬가지로 연결 리스트도 원형으로 구현이 가능합니다. 기본적인 형태는 마지막 노드의 ..

2021. 2. 18.

Computer Science/Data Structure

안녕하세요. 공상 개발입니다. 자료구조는 알고리즘과 더불어 컴퓨터공학부에서 중요하다고 자주 언급되는 과목인 만큼, 어느 정도 시간을 투자해야 됩니다. 이번 시간에는 자료구조 단원 중 하나인 연결 리스트(linked list)에 대해 간단히 알아보겠습니다. 2. 리스트(list)의 이해 2.1 배열을 이용한 리스트 3. 연결 리스트(linked list)의 이해 3.1 단순 연결 리스트(Singled Linked List) 3.2 원형 연결 리스트(Circular Linked List) 3.3 이중 연결 리스트(Doubled Linked List) * 이번 linked list(Vol.1)에서는 굵게 표시된 개념들을 리뷰(review) 합니다. 2. 리스트(list)의 이해 리스트란? 리스트는 Stack,..

2021. 2. 17.

Computer Science/Data Structure

안녕하세요. 공상 개발입니다. 자료구조는 알고리즘과 더불어 컴퓨터공학부에서 중요하다고 자주 언급되는 과목인 만큼, 어느 정도 시간을 투자해야 됩니다. 이번 시간에는 자료구조 단원 중 하나인 큐(Queue)에 대해 간단히 알아보겠습니다. 2. 큐의 이해 2.1 선형 큐 (Linear Queue) 2.2 원형 큐 (Circular Queue) 2.3 덱 (Deque) 2.1 선형 큐 (Linear Queue) 큐(Queue)는 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조입니다. 위의 이미지를 예로 든다면, 가장 먼저 줄을 선 사람이 먼저 줄을 빠져나가게 됩니다. 이러한 구조를 선입 선출(FIFO : First-In First-Out) 구조라고 합니다. 더 쉬운 이해를 위해 큐의 삽입..

2021. 2. 13.