본문 바로가기
반응형
[C++로 배우는 알고리즘과 자료구조 심화] Day 16: DP 최적화 기법 (Convex Hull Trick, Divide and Conquer Optimization) DP 최적화 기법동적 계획법(DP)은 많은 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. 그러나 때로는 DP의 시간 복잡도를 더 최적화할 필요가 있습니다. 오늘은 두 가지 주요 DP 최적화 기법에 대해 학습하겠습니다: Convex Hull Trick과 Divide and Conquer Optimization.Convex Hull TrickConvex Hull Trick은 주로 함수 (y = ax + b)의 최솟값이나 최댓값을 효율적으로 찾는 문제에서 사용됩니다. 이 기법은 선형 함수들의 집합을 유지하고, 각 쿼리마다 특정 (x)에서의 최소 (y) 또는 최대 (y)를 빠르게 계산합니다.문제 예시다음과 같은 문제를 고려해봅시다:주어진 선형 함수들의 집합 ({y = a_1x + b_1, y = a_2x.. 2024. 8. 1.
[C++ 게임 개발 시리즈] Day 16: 플레이어 입력 처리 플레이어 입력 처리플레이어 입력 처리는 게임의 핵심 요소 중 하나입니다. 플레이어는 키보드, 마우스, 게임패드 등 다양한 입력 장치를 통해 게임과 상호작용합니다. 오늘은 SFML을 사용하여 플레이어 입력을 처리하는 방법을 학습하겠습니다.기본적인 입력 처리SFML은 sf::Keyboard와 sf::Mouse 클래스를 사용하여 키보드와 마우스 입력을 처리할 수 있습니다.키보드 입력 처리키보드 입력은 sf::Keyboard::isKeyPressed 메서드를 사용하여 특정 키가 눌려 있는지 확인할 수 있습니다.#include #include #include #include int main() { // 창 생성 sf::RenderWindow window(sf::VideoMode(800, 600), "K.. 2024. 8. 1.
[C++ 임베디드 시스템 프로그래밍 시리즈] Day 16: I2C 통신 I2C 통신의 개요I2C(Inter-Integrated Circuit) 통신은 두 개 이상의 장치가 서로 데이터를 송수신할 수 있도록 하는 직렬 통신 방식입니다. I2C는 SDA(데이터)와 SCL(클럭) 두 개의 라인을 사용하여 여러 장치를 연결할 수 있으며, 하나의 마스터와 여러 슬레이브 간의 통신을 지원합니다. 오늘은 I2C 통신의 기본 개념과 사용 방법을 학습하겠습니다.1. I2C 통신의 기본 개념I2C는 다음과 같은 특징을 가집니다:멀티마스터/슬레이브 구조: 하나의 마스터와 여러 슬레이브 장치 간의 통신을 지원합니다.2개의 와이어 사용: SDA(Serial Data Line)와 SCL(Serial Clock Line)를 사용합니다.주소 지정: 각 슬레이브 장치는 고유한 주소를 가지며, 마스터는 주.. 2024. 8. 1.
[C++ 마스터] Day 17: 템플릿 기초 템플릿 (Templates)템플릿은 함수나 클래스를 작성할 때, 데이터 타입을 일반화하여 다양한 데이터 타입에 대해 동작할 수 있도록 하는 기능입니다. 템플릿을 사용하면 코드의 재사용성을 높일 수 있습니다. 1. 함수 템플릿함수 템플릿은 데이터 타입에 관계없이 동일한 기능을 수행하는 함수를 작성할 수 있게 합니다.#include using namespace std;template T add(T a, T b) { return a + b;}int main() { cout  2. 클래스 템플릿클래스 템플릿은 데이터 타입에 관계없이 동일한 기능을 수행하는 클래스를 작성할 수 있게 합니다.#include using namespace std;template class Calculator {private:.. 2024. 8. 1.
[C++ 고급 프로그래밍과 응용 프로젝트 시리즈] Day 17: 프로젝트 1 - 요청 처리 및 라우팅 구현 요청 처리 및 라우팅요청 처리는 클라이언트의 요청을 적절한 핸들러에 전달하고, 라우팅은 요청 경로에 따라 다른 처리를 할 수 있도록 합니다. 오늘은 요청 처리 및 라우팅을 구현하여 웹 서버의 기능을 확장하겠습니다. 라우팅의 필요성라우팅은 다양한 URL 경로에 대해 다른 응답을 제공할 수 있도록 합니다. 예를 들어, / 경로는 홈 페이지를, /about 경로는 소개 페이지를 제공할 수 있습니다.라우팅 구현라우팅을 구현하기 위해, 요청 경로에 따라 다른 핸들러를 호출하는 기능을 추가합니다. 1. 라우터 클래스 정의라우터는 요청 경로에 따라 적절한 핸들러를 호출하는 역할을 합니다. router.h#ifndef ROUTER_H#define ROUTER_H#include #include #include class.. 2024. 8. 1.
[C++ 성능 최적화 및 고급 테크닉] Day 17: 병렬 알고리즘과 std::async 병렬 알고리즘의 중요성병렬 알고리즘은 여러 작업을 동시에 수행하여 프로그램의 성능을 극대화하는 데 도움을 줍니다. C++17에서는 표준 라이브러리에 병렬 알고리즘을 도입하여, 쉽게 병렬 처리를 구현할 수 있습니다. 병렬 알고리즘C++17 표준 라이브러리에서는 병렬 알고리즘을 지원하기 위해 std::execution 네임스페이스를 도입했습니다. 이를 통해 기존 알고리즘을 병렬로 실행할 수 있습니다. std::execution 정책seq: 순차적으로 실행par: 병렬로 실행par_unseq: 병렬로 실행하고, 실행 순서는 정의되지 않음 예제 코드병렬 정렬#include #include #include #include int main() { std::vector vec = {5, 2, 9, 1, 5, 6.. 2024. 8. 1.
[C++ 네트크 프로그래밍] Day 17: 네트워크 보안 기초 (SSL/TLS) 네트워크 보안 기초 (SSL/TLS)SSL(Secure Sockets Layer)과 TLS(Transport Layer Security)는 네트워크 통신을 보호하기 위한 프로토콜입니다. SSL은 초기 버전이고, TLS는 SSL의 업그레이드 버전입니다. 이들은 데이터를 암호화하여 중간에서 도청하거나 변조하지 못하도록 보호합니다.SSL/TLS의 주요 기능암호화: 전송되는 데이터를 암호화하여 보호합니다.무결성: 데이터가 전송 중에 변조되지 않도록 합니다.인증: 서버와 클라이언트의 신원을 확인하여 신뢰할 수 있는 통신을 보장합니다.SSL/TLS의 주요 구성 요소공개 키 암호화: 데이터 암호화에 사용되는 두 개의 키(공개 키와 비밀 키)를 이용한 암호화 방식입니다.대칭 키 암호화: 동일한 키로 데이터를 암호화하고.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 17: 삽입 정렬과 쉘 정렬 삽입 정렬 (Insertion Sort)삽입 정렬은 배열의 요소를 하나씩 정렬된 부분에 삽입하는 방식으로 동작합니다. 각 요소를 적절한 위치에 삽입하기 위해 이미 정렬된 부분을 오른쪽으로 이동시킵니다.삽입 정렬의 시간 복잡도:최선의 경우: (O(n))평균의 경우: (O(n^2))최악의 경우: (O(n^2))삽입 정렬 구현#include #include // 삽입 정렬 함수void insertionSort(std::vector& arr) { int n = arr.size(); for (int i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 정렬된 부분에서 키보다 큰 요소 이동 --j; } .. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 17: 비트마스크 동적 계획법 (Bitmask DP) 비트마스크 동적 계획법 (Bitmask DP)비트마스크 동적 계획법은 상태를 이진수로 표현하여 여러 상태를 효율적으로 관리하는 기법입니다. 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 상태를 이진수로 표현하면 각 비트가 특정 원소의 포함 여부를 나타내어 간결하게 표현할 수 있습니다.문제 예시: 외판원 문제 (Traveling Salesman Problem, TSP)외판원 문제는 주어진 도시들을 방문하여 모든 도시를 한 번씩 방문하고 시작점으로 돌아올 때, 이동 비용의 합이 최소가 되도록 하는 경로를 찾는 문제입니다. 비트마스크 DP를 사용하여 해결할 수 있습니다.문제 정의주어진 도시 수 (n)각 도시 간의 거리 (dist[i][j])최소 이동 비용을 계산하여 출력비트마스크 DP 구현다음은 C+.. 2024. 8. 1.
[C++ 게임 개발 시리즈] Day 17: 게임 상태 관리 게임 상태 관리게임 상태 관리는 게임이 다양한 상태(예: 메인 메뉴, 게임 플레이, 일시 정지, 게임 오버 등)를 가질 수 있도록 하는 중요한 개념입니다. 상태 패턴(State Pattern)을 사용하여 이러한 상태 전환을 관리할 수 있습니다.상태 패턴(State Pattern)상태 패턴은 객체의 상태에 따라 다른 동작을 수행하도록 하는 디자인 패턴입니다. 이를 통해 상태 전환을 간단하고 명확하게 관리할 수 있습니다.게임 상태 인터페이스 정의먼저, 게임 상태 인터페이스를 정의합니다. 이 인터페이스는 각 상태에서 필요한 공통 메서드를 선언합니다.class GameState {public: virtual ~GameState() {} virtual void handleEvent(sf::Event& .. 2024. 8. 1.
반응형

티스토리툴바