본문 바로가기
반응형
[C++로 배우는 알고리즘과 자료구조] Day 19: 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort)퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 피벗(Pivot)을 기준으로 두 개의 하위 배열로 나눈 다음, 각각을 정렬합니다. 퀵 정렬은 평균적으로 매우 빠른 정렬 알고리즘으로 간주됩니다.퀵 정렬의 시간 복잡도:평균의 경우: (O(n \log n))최악의 경우: (O(n^2))최선의 경우: (O(n \log n))퀵 정렬의 공간 복잡도:(O(\log n)) (재귀 호출 스택 공간)퀵 정렬 구현퀵 정렬의 주요 단계:분할 (Partition): 피벗을 기준으로 배열을 두 부분으로 나눕니다.정복 (Conquer): 하위 배열을 재귀적으로 정렬합니다.결합 (Combine): 분할된 하위 배열이 정렬된 상태이므로 추가.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 19: 스테이트 컴프레션 동적 계획법 (State Compression DP) 스테이트 컴프레션 동적 계획법 (State Compression DP)스테이트 컴프레션 동적 계획법(State Compression DP)은 상태를 비트마스크로 표현하여 동적 계획법을 적용하는 기법입니다. 이는 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 이 기법은 상태를 효율적으로 관리하고, 메모리 사용량을 줄일 수 있습니다.문제 예시: 여행 계획주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 스테이트 컴프레션 DP를 사용할 수 있습니다. 여기서 dp[mask][i]는 방문한 도시 집합이 mask이고 현재 i 도시에 위치한 경우의 최소 비용을 의미합니다.스테이트 컴프레션 DP 구현다음은 C++로 스테이트 컴프레션 DP를 사용하여 문제를 해결하는 예제입니다.#.. 2024. 8. 1.
[C++ 마스터] Day 16: 가상 함수와 추상 클래스 가상 함수 (Virtual Function)가상 함수는 기본 클래스에서 선언되고 파생 클래스에서 재정의될 수 있는 함수입니다. 가상 함수는 다형성을 구현하는 데 사용됩니다. 1. 가상 함수 선언가상 함수는 기본 클래스에서 virtual 키워드를 사용하여 선언합니다.class Base {public: virtual void show() { cout show(); // Derived class show function return 0;} 추상 클래스 (Abstract Class)추상 클래스는 하나 이상의 순수 가상 함수를 포함하는 클래스입니다. 추상 클래스는 직접 인스턴스화할 수 없으며, 이를 상속받는 파생 클래스에서 순수 가상 함수를 반드시 재정의해야 합니다. 1. 순수 가상 함수순.. 2024. 8. 1.
[C++ 고급 프로그래밍과 응용 프로젝트 시리즈] Day 16: 프로젝트 1 - HTTP 프로토콜 이해 및 구현 HTTP 프로토콜 이해HTTP(HyperText Transfer Protocol)는 웹에서 클라이언트와 서버 간의 통신을 위한 프로토콜입니다. HTTP 요청과 응답은 텍스트 형식으로 전송되며, 요청은 클라이언트에서 서버로, 응답은 서버에서 클라이언트로 전송됩니다. HTTP 요청의 구성요청 라인: 메서드, 경로, 버전으로 구성됩니다.헤더: 키-값 쌍으로 이루어진 메타데이터입니다.바디: 선택적이며, 주로 POST 요청에서 사용됩니다.HTTP 요청 예시:GET /index.html HTTP/1.1Host: localhost:8080User-Agent: curl/7.68.0Accept: */* HTTP 응답의 구성상태 라인: 버전, 상태 코드, 상태 메시지로 구성됩니다.헤더: 키-값 쌍으로 이루어진 메타데이터입.. 2024. 8. 1.
[C++ 성능 최적화 및 고급 테크닉] Day 16: std::thread와 동기화 기법 std::thread 클래스std::thread 클래스는 C++11 표준 라이브러리에서 제공하는 멀티스레딩을 위한 클래스입니다. 이를 통해 쉽게 스레드를 생성하고 관리할 수 있습니다. std::thread의 주요 함수생성자: 새로운 스레드를 생성합니다.join(): 스레드가 종료될 때까지 대기합니다.detach(): 스레드를 분리하여 백그라운드에서 실행되도록 합니다.joinable(): 스레드가 join 또는 detach 가능한 상태인지 확인합니다.예제 코드#include #include void threadFunction() { std::cout  동기화 기법여러 스레드가 공유 자원에 접근할 때, 동기화가 필요합니다. C++ 표준 라이브러리는 동기화를 위한 여러 도구를 제공합니다. std::mut.. 2024. 8. 1.
[C++ 네트워크 프로그래밍] Day 16: 비동기 I/O와 이벤트 드리븐 프로그래밍 비동기 I/O와 이벤트 드리븐 프로그래밍비동기 I/O(Asynchronous I/O)는 프로그램이 I/O 작업을 요청한 후, 그 작업이 완료될 때까지 기다리지 않고 다른 작업을 계속 수행할 수 있도록 하는 방식입니다. 이벤트 드리븐 프로그래밍(Event-driven programming)은 특정 이벤트가 발생할 때 미리 정의된 작업(콜백 함수)을 수행하는 프로그래밍 방식입니다. 이 두 가지 개념을 결합하면 효율적이고 응답성이 좋은 네트워크 애플리케이션을 개발할 수 있습니다.비동기 I/O의 장점높은 응답성: I/O 작업이 완료될 때까지 기다리지 않으므로, 다른 작업을 계속 수행할 수 있습니다.효율적인 자원 사용: 비동기 I/O를 사용하면 스레드가 블록되지 않으므로, 시스템 자원을 효율적으로 사용할 수 있습.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 16: 버블 정렬과 선택 정렬 버블 정렬 (Bubble Sort)버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 자리를 바꾸면서 배열을 정렬합니다. 배열의 끝까지 이 과정을 반복하면 가장 큰 값이 맨 끝에 위치하게 됩니다. 이 과정을 여러 번 반복하여 배열이 정렬될 때까지 진행합니다.버블 정렬의 시간 복잡도:최선의 경우: (O(n))평균의 경우: (O(n^2))최악의 경우: (O(n^2))버블 정렬 구현#include #include // 버블 정렬 함수void bubbleSort(std::vector& arr) { int n = arr.size(); for (int i = 0; i arr[j + 1]) { std::swap(arr[j], arr[j +.. 2024. 8. 1.
[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.
반응형

티스토리툴바