sundori DevStory

목차 신장트리 그래프의 관점에서 트리를 보면 사이클이 없는 연결 그래프이다. 사이클이란 순환 경로에서 시작 정점과 종료 정점이 동일한 경우를 말한다. 모든 정점이 n개인 무방향 그래프에서 정점이 n개이고 간선이 n-1개인 트리의 형태의 부분 그래프를 신장 트리 Spanning Tree라고 한다. 깊이 우선 탐색을 이용하여 생성된 신장 트리를 깊이 우선 신장 트리(Depth First Spanning Tree)라고하며, 너비 우선 탐색을 이용하여 생성된 신장 트리를 너비 우선 신장트리(Breadth First Spanning Tree)라고 한다. 위의 사진을 보면 알다시피 모든 정점이 무조건 한 번씩 연결이 되어있는데 이것이 바로 간선을 최소로 이용하여 모든 정점을 연결한 신장트리이다. 이렇게 간선을 최소..

목차 너비 우선 탐색(BFS) 큐를 활용: 너비 우선 탐색은 시작 노드에서 인접한 모든 노드를 먼저 방문한 후, 그 다음 레벨의 노드들을 방문하며, 이를 위해 큐를 사용한다. 노드 방문: 시작 노드에서 인접한 노드를 먼저 모두 방문한 후, 다음 레벨의 노드로 이동하며 방문한 노드는 표시하여 중복 방문을 방지한다. 너비 우선 탐색의 특징: 레벨 단위로 탐색하기 때문에 최단 경로를 찾는데 효과적이며, 큐를 사용하기 때문에 반복문으로 구현하기 용이하다. 즉, 시작 정점에 인접한 정점을 모두 차례로 방훈하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례대로 방문하는 방법이다. 가까운 정점을 먼저 방문하고 난 뒤 멀리 있는 정점을 나중에 방문한다. #pragma once #include #include ..

목차 그래프 순회의 개념 한 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 확인하는 것을 그래프 순회 Graph Traversal 또는 그래프 탐색 Graph Search라고 한다. 깊이 우선 탐색(DFS) 스택 또는 재귀 함수를 활용: 깊이 우선 탐색은 특정 경로를 따라 끝까지 탐색한 후 다른 경로를 탐색하고, 이를 위해 스택을 사용하거나 재귀 함수를 호출하여 구현한다. 노드 방문: 시작 노드에서 출발하여 한 경로를 끝까지 탐색한 후 되돌아와서 다른 경로를 탐색하며, 방문한 노드는 표시하여 중복 방문을 방지한다. 깊이 우선 탐색의 특징: 한 경로를 완전히 탐색하기 때문에 목표 노드가 발견되면 바로 종료할 수 있으며, 특히 트리 구조에서는 재귀를 통해 간단하게 구현이 가능하다. 즉, 시작..

ㅊ2023.11.14 - [알고리즘] - [알고리즘] 트리 5 - 균형 이진 탐색 트리(AVL) [알고리즘] 트리5 - 균형 이진 탐색 트리(AVL) 목차 2023.11.13 - [알고리즘] - [알고리즘] 트리 4 - 이진 탐색 트리 [알고리즘] 트리4 - 이진 탐색 트리 이진 탐색 트리 이진트리는 트리를 효율적으로 구현하고 관리하기 위해서 일정한 조건으로 정 sun-dori.tistory.com 목차 히프 히프는 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키잡이 가장 작은 노드를 찾을 때 필요한 자료구조이다. 키값이 가장 큰 노드를 찾기 위한 히프를 최대 히프(Max Heap), 키값이 가장 작은 노드를 찾기 위한 히프를 최소 히프(Min Heap)라 한다. 히프의 개념 최대 히프 최..

목차 01 트리의 이해 트리(Tree)는 자료들이 리스트, 스택 큐와 같은 1:1 관계의 선형 구조가 아니라 1:n 관계의 비선형 자료구조이며, 계층 자료구조이다. 트리의 구성 요소 노드 Node: 트리를 구성하는 원소(자료)를 노드(Node)라고 한다. 간선 Edge: 노드를 연결하는 선. 루트 Root 노드, Level 0: 트리의 시작 노드. 형제 Sibling 노드: 같은 부모 노드를 가진 자식 노드들. 조상 Ancestor 노드: 루트 노드까지 이르는 경로에 있는 노드는 모두 그 노드의 조상. (노드 K의 조상은 F, B, A) 서브 트리 Subtree: 자식 노드들은 독립하여 새로운 트리 구성이 가능 따라서 각 노드는 자식 노드 수만큼 서브트리를 가짐. (노드 B의 자손 노드는 서브트리 E의 ..

목차 # 순차 자료구조의 개념 자료는 구조화하는 방법에 따라 리스트, 스택, 큐, 데크, 트리, 그래프 등으로 나뉘는데 이러한 자료구조 유형을 프로그램으로 구현하는 방식에는 순차 자료구조와 연결 자료구조가 있다. 순차 자료구조 메모리 저장 방식 : 순차 자료구조는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 방식. 연산 특징 : 삽입, 삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장되며 변경된 논리적인 순서와 저장된 물리적인 순서가 일치. 프로그램 기법 : 배열을 이용하여 구현 연결 자료구조 메모리 저장 방식 : 연결 자료 구조는 노드라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 메모리에 저장된 물리적 위치나 순서와 상관없이, 링크에 의해 논리적인 순서를 표현하는 방..

목차 # 재귀호출의 개념 재귀호출은 함수가 자기 자신을 호출하여 순환하여 수행되는 것으로 순환 호출 또는 Recursion이라고 부른다. 함수에서 실행해야 하는 작업에 따라 재귀호출을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성이 가능하다. 재귀호출을 사용하는 경우는? 팩토리얼 함수 대표적인 재귀호출 함수는 팩토리얼(Factiroal)인데 n에 대한 팩토리얼 함수는 1부터 n까지 모든 자연수를 곱하는 연산이다. #include int fact(int n){ int value; if(n

목차 # 구조체 개념 구조체도 배열처럼 여러 데이터를 그룹으로 묶어 하나의 자료형으로 정의가 가능하며, 배열은 자료형이 같을 때만 그룹으로 묶을 수 있지만, 구조체는 서로 다른 자료형도 그룹으로 묶을 수 있어 다양한 자료형을 가지거나 복잡한 자료의 형태를 정의할 때 유용하게 사용한다. 자료를 체계적으로 관리하려면 일정한 단위 형식으로 구성해야 하는데, 밑에 표가 이를 알려준다. 행, ROW, RECORD, 데이터베이스(RECORDS, Tuple) 열, Column, Field 행 ROW RECORD 김00 2014년 가입 3000 하00 2015년 가입 4000 홍00 2018년 가입 2000 권00 2023년 가입 5000 열, Column, Field 명칭 열, Column, Field 행 ROW R..

목차 # 포인터 개념 사용한느 모든 변수는 메모리의 특정 위치에 저장되는데 그 위치를 나타내는 메모리 주소를 포인터라고 한다. 포인터 변수는 메모리의 주소값을 저장하며, 포인터 변수 P가 어떤 변수 A의 주소를 저장하고 있다는 것은 포인터 변수 P가 변수 A의 위치(메모리 주소)를 가리키고 있다는 의미이다. 다른 말로는 포인터를 사용해 다른 변수를 액세스 할 수 있다는 소리이다. int A; int *P = &A; // 메모리 주소 한 개 저장. /* *int A에서 int 형 A변수를 선언했을 때 할당된 메모리 번지 예를들어 1번지라할 때, int *P = &A에 의해서 *변수 A의 주소 1번지를 포인터 P에 저장하므로 포인터 P는 변수 A를 가리키게 된다. *그러면 변수 A와 포인터 P가 논리적으로 ..

목차 #1 알고리즘 알고리즘은 주어진 문제를 해결하는 방법을 추상화하여 일련의 단계적 절차를 논리적으로 기술해 놓은 명세서이다. 알고리즘 표현 방법의 종류 자연어를 이용한 서술적 표현 알고리즘을 사람이 쓰는 자연어(언어)로 표현하는 방법이다. 자연어는 서술적일 뿐만 아니라 쓰는 사람에 따라 일관성이나 명확성을 유지하기 어렵다. 따라서 누구라도 쉽게 이해하고 쓸 수 있어야 하는 알고리즘을 표현하는데 한계가 있다. 순서도를 이용한 도식화 알고리즘을 순서도(Flow Chart)를 작성하는 규칙에 따라 도식화하는 방법이다. 순서도를 이용하면 명령의 흐름을 쉽게 파악할 수 있지만 복잡한 알고리즘을 표현하는 데에 한계가 있다. 프로그래밍 언어를 이용한 구체화 알고리즘을 프로그래밍 언어를 사용하여 표현하는 방법이다...