본문 바로가기
반응형
[C++로 배우는 알고리즘과 자료구조] Day 13: 이진 힙과 힙 정렬 이진 힙 (Binary Heap)이진 힙은 완전 이진 트리의 형태를 가지며, 각 노드가 특정한 우선순위를 가지는 자료구조입니다. 이진 힙은 주로 최대값이나 최소값을 빠르게 찾기 위해 사용됩니다. 이진 힙에는 최대 힙(Max-Heap)과 최소 힙(Min-Heap)이 있습니다.이진 힙의 종류:최대 힙 (Max-Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.최소 힙 (Min-Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.힙 정렬 (Heap Sort)힙 정렬은 이진 힙을 이용한 정렬 알고리즘으로, 최대 힙 또는 최소 힙을 사용하여 배열을 정렬합니다. 힙 정렬은 평균 및 최악의 경우 시간 복잡도가 (O(n \log n))입니다.힙 정렬의 과정:배열을 이진 힙으로 변환합니다... 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 13: 이분 그래프 매칭 (Hopcroft-Karp 알고리즘) 이분 그래프 매칭 (Bipartite Graph Matching)이분 그래프 매칭은 두 개의 분리된 정점 집합을 가지는 그래프에서 최대 매칭을 찾는 문제입니다. 이분 그래프 매칭은 네트워크 플로우, 작업 할당 문제, 매칭 문제 등 다양한 응용 분야에서 사용됩니다.Hopcroft-Karp 알고리즘Hopcroft-Karp 알고리즘은 이분 그래프에서 최대 매칭을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 BFS와 DFS를 결합하여 구현됩니다.Hopcroft-Karp 알고리즘의 시간 복잡도:(O(\sqrt{V}E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.Hopcroft-Karp 알고리즘 구현다음은 C++로 Hopcroft-Karp 알고리즘을 구현한 예제입니다. 그래프 클래스 정의#includ.. 2024. 8. 1.
[C++ 게임 개발 시리즈] Day 13: 충돌 처리와 반응 충돌 처리와 반응충돌 처리와 반응은 물리 기반 게임에서 중요한 요소입니다. 오늘은 Box2D를 사용하여 충돌을 처리하고, 충돌에 반응하는 방법을 학습하겠습니다.충돌 처리 기초Box2D는 충돌을 감지하고 처리하기 위해 충돌 콜백 시스템을 제공합니다. 이 시스템을 사용하면 두 물체가 충돌했을 때 특정 동작을 수행할 수 있습니다.Box2D 충돌 콜백Box2D에서 충돌을 처리하려면 b2ContactListener 클래스를 상속하고, BeginContact와 EndContact 메서드를 재정의합니다. 이 메서드들은 충돌이 시작되거나 끝날 때 호출됩니다.충돌 콜백 클래스 정의#include #include #include // 픽셀을 미터로 변환하는 비율const float SCALE = 30.0f;// 사용자 정.. 2024. 8. 1.
[C++ 임베디드 시스템 프로그래밍 시리즈] Day 13: 서보 모터 제어 서보 모터의 개요서보 모터는 정밀한 위치 제어가 필요한 애플리케이션에서 사용됩니다. 서보 모터는 특정 각도로 회전할 수 있으며, 이를 통해 로봇 공학, 모델링, 자동화 시스템 등 다양한 분야에서 사용됩니다. 오늘은 서보 모터의 기본 개념과 제어 방법을 학습하겠습니다.1. 서보 모터의 기본 개념서보 모터는 내부에 제어 회로와 위치 피드백 시스템을 갖추고 있습니다. 일반적으로 0도에서 180도 또는 360도까지 회전할 수 있으며, 정확한 각도 제어가 가능합니다. 서보 모터의 주요 특성제어 신호: 서보 모터는 PWM 신호를 통해 제어됩니다. PWM 신호의 듀티 사이클에 따라 회전 각도가 결정됩니다.회전 각도: 일반적인 서보 모터는 0도에서 180도까지 회전할 수 있습니다. 일부 서보 모터는 360도 회전이 가.. 2024. 8. 1.
[C++ 마스터] Day 14: 연산자 오버로딩 연산자 오버로딩 (Operator Overloading)연산자 오버로딩은 기존의 C++ 연산자를 사용자 정의 타입(클래스)에 대해 재정의하는 기능입니다. 이를 통해 객체 간의 연산을 보다 직관적으로 수행할 수 있습니다. 1. 기본 개념연산자 오버로딩은 함수 형태로 정의되며, 클래스의 멤버 함수 또는 전역 함수로 구현할 수 있습니다. 2. 멤버 함수로 연산자 오버로딩연산자를 멤버 함수로 오버로딩하는 방법은 다음과 같습니다:class Complex {private: double real; double imag;public: Complex(double r = 0, double i = 0) : real(r), imag(i) {} // + 연산자 오버로딩 Complex operator .. 2024. 8. 1.
[C++ 네트워크 프로그래밍] Day 10: HTTP 서버 개발 (Boost.Beast) Boost.Beast 소개Boost.Beast는 HTTP와 WebSocket 프로토콜을 지원하는 라이브러리입니다. Boost.Asio를 기반으로 하여 비동기 네트워크 프로그래밍을 쉽게 구현할 수 있습니다. HTTP 서버를 개발하기 위해 Boost.Beast를 사용하면 간단하고 효율적인 코드 작성을 할 수 있습니다.Boost.Beast 설치Boost 라이브러리 설치는 이전 단계에서 다루었으며, Boost.Beast는 Boost 라이브러리의 일부입니다.HTTP 서버 구현HTTP 서버를 구현하기 위해 다음과 같은 단계를 따릅니다:io_context: 비동기 작업을 관리하는 io_context 객체를 생성합니다.tcp::acceptor: 클라이언트 연결을 수락하기 위한 acceptor 객체를 생성합니다.세션 관.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 ] Day 10: 트라이 (Trie) 트라이 (Trie)트라이는 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다. 트라이는 주로 문자열 집합의 검색, 삽입, 삭제에 사용되며, 접두사 검색에 매우 효율적입니다.트라이의 특징:노드 구조: 각 노드는 문자와 자식 노드를 가집니다.루트 노드: 루트 노드는 빈 문자열을 나타냅니다.경로: 문자열은 루트 노드에서 시작하여 각 문자에 해당하는 노드를 따라 내려가면서 표현됩니다.접두사 검색: 공통 접두사를 가진 문자열을 효율적으로 검색할 수 있습니다.트라이 구현TrieNode.h#ifndef TRIENODE_H#define TRIENODE_H#include // 트라이의 노드 구조체struct TrieNode { std::unordered_map children; // 자식 노드를 .. 2024. 8. 1.
[C++ 게임 개발 시리즈] Day 10: 애니메이션 기법 (프레임 기반 애니메이션) 애니메이션 기법 (프레임 기반 애니메이션)애니메이션은 게임에서 캐릭터의 움직임, 환경의 변화 등을 생동감 있게 표현하는 중요한 요소입니다. 오늘은 프레임 기반 애니메이션 기법을 사용하여 애니메이션을 구현하는 방법을 학습하겠습니다.프레임 기반 애니메이션프레임 기반 애니메이션은 여러 개의 이미지(프레임)를 순차적으로 표시하여 움직임을 표현하는 방식입니다. 각 프레임은 일정한 시간 동안 화면에 표시되며, 모든 프레임이 순서대로 표시되면 하나의 애니메이션이 완성됩니다.애니메이션 구현 예시다음 예제에서는 SFML을 사용하여 간단한 캐릭터 애니메이션을 구현합니다.텍스처와 스프라이트 설정먼저, 애니메이션에 사용할 텍스처와 스프라이트를 설정합니다.#include #include #include #include #inc.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 10: 위상 정렬 (Topological Sorting) 위상 정렬 (Topological Sorting)위상 정렬은 유향 비순환 그래프(DAG, Directed Acyclic Graph)의 정점을 순서대로 나열하는 방법입니다. 이 순서는 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 나오는 순서를 의미합니다. 위상 정렬은 주로 작업 스케줄링, 컴파일러에서의 심볼 테이블 생성 등에 사용됩니다.위상 정렬의 주요 특징DAG: 위상 정렬은 반드시 유향 비순환 그래프에서만 가능합니다.순서: 정점 u에서 정점 v로 가는 모든 경로에 대해 정점 u는 정점 v보다 먼저 나옵니다.위상 정렬의 구현 방법Kahn's Algorithm: 진입 차수를 이용한 위상 정렬DFS 기반 알고리즘: 깊이 우선 탐색을 이용한 위상 정렬Kahn's AlgorithmKahn's Al.. 2024. 8. 1.
[C++ 임베디드 시스템 프로그래밍 시리즈] Day 10: 온도 센서 제어 온도 센서의 개요온도 센서는 주변 환경의 온도를 측정하여 아날로그 또는 디지털 신호로 출력하는 장치입니다. 임베디드 시스템에서는 다양한 온도 센서를 사용하여 온도를 모니터링하고 제어할 수 있습니다. 오늘은 온도 센서를 사용하는 방법을 학습하겠습니다.1. 온도 센서 종류온도 센서는 출력 신호 형태에 따라 아날로그 센서와 디지털 센서로 나눌 수 있습니다.아날로그 온도 센서: TMP36, LM35 등. 아날로그 전압을 출력하며, 이를 ADC를 통해 읽습니다.디지털 온도 센서: DS18B20, DHT11, DHT22 등. 디지털 데이터를 출력하며, I2C, SPI, 1-Wire 등의 인터페이스를 사용합니다.2. 아날로그 온도 센서 사용TMP36 온도 센서를 사용하여 아날로그 온도를 측정하는 방법을 살펴보겠습니다.. 2024. 8. 1.
반응형

티스토리툴바