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) 스택 또는 재귀 함수를 활용: 깊이 우선 탐색은 특정 경로를 따라 끝까지 탐색한 후 다른 경로를 탐색하고, 이를 위해 스택을 사용하거나 재귀 함수를 호출하여 구현한다. 노드 방문: 시작 노드에서 출발하여 한 경로를 끝까지 탐색한 후 되돌아와서 다른 경로를 탐색하며, 방문한 노드는 표시하여 중복 방문을 방지한다. 깊이 우선 탐색의 특징: 한 경로를 완전히 탐색하기 때문에 목표 노드가 발견되면 바로 종료할 수 있으며, 특히 트리 구조에서는 재귀를 통해 간단하게 구현이 가능하다. 즉, 시작..

목차 그래프의 개념 그래프는 원소 사이의 다대다 n:n 관계를 표현하는 비선형 자료구조이다. 예를 들어 지하철 노선도나 버스 노선도를 보면 선형 자료구조로는 표현할 수가 없기 때문이다. 그래프는 객체를 나타내는 정점 Vertex와 객체를 연결하는 간선 Edge의 집합으로 구성된다. 그래프 G는 G=(V, E)로 정의하는데, V는 그래프에 있는 정점의 집합을 뜻하고 E는 정점을 연결하는 간선의 집합을 뜻한다. 그래프의 종류 무방향 그래프 무방향 그래프 Undirected Graph는 두 정점을 연결하는 간선에 방향이 없는 그래프인데, 무방향 그래프에서 정점 Va와 Vb를 연결하는 간선을 (Va, Vb)로 표현하고 각 정점에서는 (Va, Vb) 또는 (Vb, Va)처럼 간선을 나타낸다. 위에 사진이 무방향 ..

2023.11.18 - [C\C++/OpenGL] - C/C++ OpenGl을 이용한 간단한 태양계 구축 프로젝트(2) C/C++ OpenGl을 이용한 간단한 태양계 구축 프로젝트(2) 2023.11.08 - [C\C++/OpenGL] - C/C++ OpenGl을 이용한 간단한 태양계 구축 프로젝트(1) C/C++ OpenGl을 이용한 간단한 태양계 구축 프로젝트(1) Windows MFC (Microsoft Foundation Classes)를 사용하여 OpenGL을 초기화하고 간 sun-dori.tistory.com 목차 OpenGL 재질효과 OpenGL에서 재질(Material)은 물체가 빛과 상호 작용하는 방식을 제어하는 데 사용되는 속성의 힙합이먀, 재질은 주변광, 확산광, 반사광 등을 포함한 ..

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

릴레이 부저 제어 테스트 LED_CON과 SET_CON은 각각 0x8000 및 0x8100의 주소를 할당받고, 부호 없는 문자형 포인터로 취급하며, 이러한 주소는 외부 I/O를 제어하는 데 사용한다. #define LED_CON *((unsigned char *)0x8000) #define SET_CON *((unsigned char *)0x8100) Buzz, Relay1, Relay2는 특정 핀 번호에 할당하며, 그다음의 라인에서는 이러한 핀을 켜고 끄기 위한 비트 마스크를 정의한다. #define Buzz 6 #define Relay1 0 #define Relay2 1 #define Relay1_on 1

외부 인터럽트 미리 배정되어 있는 처리기의 핀으로 입력되는 트리거 신호에 의해 발생하는 인터럽트이다. 프로그램에 의해 발생하는 타이머/카운터 인터럽트와 비교하면 외부 인터럽트는 하드웨어적인 인터럽트라 할 수 있고 주변 장치들의 요청에 가장 신속하게 대처할 수 있는 인터럽트의 대응 방식이다. 글쓴이가 공부할 때 사용하는 ATmega128 보드 에서는 ... 외부 인터럽트 관련 레지스터 외부 인터럽트 마스크 레지스터 : EIMSK("External Interrupt Mask Register") EIMSK 레지스터는 외부 인터럽트를 사용하거나 무시할지를 제어하는 데 사용하는데, 외부 인터럽트는 외부에서 발생하는 신호나 이벤트에 응답하여 마이크로컨트롤러의 실행을 중단하고 특정한 인터럽트 서비스 루틴(ISR)을 ..

2023.11.08 - [C\C++/OpenGL] - C/C++ OpenGl을 이용한 간단한 태양계 구축 프로젝트(1) C/C++ OpenGl을 이용한 간단한 태양계 구축 프로젝트(1) Windows MFC (Microsoft Foundation Classes)를 사용하여 OpenGL을 초기화하고 간단한 2D 그래픽을 렌더링 하는 뷰 클래스를 사용하여 간단한 태양계 구축하기. 이번에는 OpenGL을 사용하여 태양계 모델링을 구 sun-dori.tistory.com 저번 글에 이어서 이번에는 조명 효과를 넣어보고자 한다. OpenGL 조명 효과 조명의 종류 주변광 (Ambient Light) : 모든 방향에서 나타나는 조명으로 모든 물체에 균일하게 영향을 미친다. 주변 어디에서나 나오는 일반적인 빛을 말하..

목차 2023.11.13 - [알고리즘] - [알고리즘] 트리 4 - 이진 탐색 트리 [알고리즘] 트리4 - 이진 탐색 트리 이진 탐색 트리 이진트리는 트리를 효율적으로 구현하고 관리하기 위해서 일정한 조건으로 정의한 것이며, 이진트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정해둔 sun-dori.tistory.com 균형 이진 탐색 트리 이진 탐색 트리에서 좌우 균형이 올바르다면 탐색을 할 때 성능이 좋고 이 성능은 탐색 트리의 높이와 밀접한 상관관계를 가진다. 높이가 3인 (a) 트리에서는 17을 탐색하려면 루트 노드 8에서 비교 연산을 4번을 수행해야 하지만... 높이가 5인 (b) 트리에서는 17을 탐색하려면 (a) 트리보다 더 많은 비교 연산이 필요하다.. n개의 노드를..