전체 글 224

[알고리즘] 트리4 - 이진 탐색 트리

이진 탐색 트리 이진트리는 트리를 효율적으로 구현하고 관리하기 위해서 일정한 조건으로 정의한 것이며, 이진트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정해둔 것이다. 이진트리에서는 내가 필요한 자료(정보)를 찾을 때 KEY 값을 이용하여 자료를 찾는데 이 KEY 값은 자료를 식별할 수 있는 유일한 값이다. (ex: 대학생의 학번 etc..) 이진 탐색 트리의 정의 모든 원소는 서로 다른 유일한 키를 갖는다. -> 데이터베이스에서의 기본 키(Primary Key) 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다. 오른쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 크다. 왼쪽 서브 트리와 오른쪽 서브 트리 둘 다 이진 탐색 트리이다. ⭐모든 연산에는 탐색 연산이 ..

알고리즘 2023.11.13

[알고리즘] 트리3 - 스레드 이진 트리

목차 스레드 이진트리(Thread Binary Tree) 이전 글 이진 트리의 순회에서는 부모 노드와 자식 노드의 이진트리 기본 구조에서 각 레벨에서 순환적으로 반복되어 전체 트리가 구성되는 구조이다 보니 각 노드에서의 순회 연산을 재귀호출을 이용하여 순환적으로 반복하여 전체 트리에 대한 순회를 처리하였다. 이러한 방식은 함수 구현을 함에 있어서 간단하지만, 수행의 성능 측면에서는 시스템적으로 스택을 사용하여 호출과 복귀를 관리해야하고 이진트리의 하위 레벨로 내려갈수록 재귀호출의 깊이가 깊어지므로(스택에 쌓이는 양이 많아짐) 매우 비효율적일 수 있다. 따라서 이러한 문제점들을 생각하여 재귀호출이 없어도 순회가 가능토록한 것이 스레드 이진트리이다. 스레드 이진트리의 특징 스레드 (Thread) 스레드 이진..

알고리즘 2023.11.13

[알고리즘] 트리2 - 이진 트리의 순회

#1 이진트리의 순회 이진트리의 순회 개념 순회(Traversal)란 모든 원소를 하나라도 빠트리거나 중복하지 않고 처리하는 연산을 의미한다. 리스트, 스택, 큐 등과 같은 선형 자료구조는 원소를 1:1 관계로 구성하기에 순회 연산이 필요가 없지만 이진트리는 1:2의 비선형 계층 구조이기에 현재 노드를 처리한 뒤에 왼쪽 노드, 오른쪽 노드 둘 중 어떤 노드를 처리할지 결정하는 순회 연산이 필요하다. 순회연산 작업 D: 현재 노드를 방문하여 처리. 작업 L: 현재 노드의 왼쪽 서브 트리로 이동. 작업 R: 현재 노드의 오른쪽 서브 트리로 이동. 이 3가지의 작업의 수행 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눈다. 전위 순회 전위 순회(Preorder Traversal)는 D -> L -> R..

알고리즘 2023.11.10

임베디드시스템 스위치 버튼을 통한 LED 응용

1번 스위치 : 홀수 번째 LED 점등 2번 스위치 : 짝수 번째 LED 점등 3번 스위치 : LED들이 Shift Left 4번 스위치 : LED들이 Shift Right 5번 스위치 : 모든 LED 점등 6번 스위치 : 두개의 LED들이 Shift Left되며 점등 7번 스위치 : 두개의 LED들이 Shift Right되며 점등 8번 스위치 : 크리스마스 트리. /* 날짜 : 2023-10-17 작성자 : 권xx 설명 : 스위치 입력에 따라 LED를 제어하는 프로그램. */ #include #include #define LED_CON *((unsigned char *)0x8000) // LED Control bus void main(void) { unsigned char SW = 0; // 변수 SW..

임베디드 시스템 스위치를 이용한 LED 구동

#include // 머크로티에서 Mega128을 위한 헤더 파일을 가져옵니다. #define LED_CON *((unsigned char *)0x8000) // LED_CONTROL을 위한 메모리 주소를 정의합니다. void main(void) { // 메인 함수 시작 DDRB = 0x00; // PORTB를 입력으로 설정 (0x00은 모든 핀을 입력으로 설정합니다). MCUCR = 0X80; // 외부 메모리 및 I/O 제어를 활성화합니다. // 외부 I/O 디바이스 초기화 LED_CON = 0X00; // LED GLCD 제어 버스를 초기화합니다. while(1) { // 무한 루프 시작 static unsigned char Switch_Button = 0; // 스위치 버튼 값을 저장하기 위한 변..

C/C++ OpenGl을 이용한 간단한 태양계 구축 프로젝트(1)

Windows MFC (Microsoft Foundation Classes)를 사용하여 OpenGL을 초기화하고 간단한 2D 그래픽을 렌더링 하는 뷰 클래스를 사용하여 간단한 태양계 구축하기. 이번에는 OpenGL을 사용하여 태양계 모델링을 구현과 MFC(Microsoft Foundation Classes)를 사용하여 Windows 환경에서 OpenGL을 초기화하고 3D 모델을 렌더링 하여 보자. COpenGLView 클래스 COpenGLView 클래스 생성자 (COpenGLView::COpenGLView()) 클래스 생성자에서는 행성과 달의 회전 등 각도 초기화를 수행한다! COpenGLView::PreCreateWindow 함수 윈도우를 생성하기 전에 윈도 클래스 및 스타일을 수정하며, OpenGL ..

C, C++/OpenGL 2023.11.08

[알고리즘] 트리1 - 트리와 이진트리

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

알고리즘 2023.11.03