Brute force Study

[Algorithm/Divide&Conquer] 02. 이진 검색(binary search)

이진 검색(binary search) (a.k.a 이진 탐색) 일반적인 검색 문제정렬되어 있는 정수 시퀀스가 있고, 여기에 숫자 N이 있는지 확인하려고 한다.이러한 검색 문제는 두 가지 방법으로 접근할 수 있다.  선형 검색(linear search)시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지를 확인하는 방식이다.bool linear_search(int n, vector& sequence) { for (auto i : sequence) { if (i == n) { return true; } } return false;} 장점 : 입력 시퀀스의 정렬 여부와 상관 없이 항상 잘 동작한다단점 : 효율적이지 않음.O(N)주어진 배열이 정렬되..

[Algorithm/Divide&Conquer] 01. 분할 정복(Divide & Conquer) 알고리즘

분할 정복 설계 패러다임효율적인 알고리즘을 설계하기 위한 일반적인 접근 방법이 개발되어 다양한 문제 해결에 사용되고 있다.분할 정복(divide-and-conquer)은 가장 널리 사용되는 알고리즘 설계 패러다임 중 하나이다.분할 정복 알고리즘이란?주어진 문제를 작은 부분 문제로 나누고, 나줘진 각 부분 문제의 솔루션을 구하고, 각 부분 문제 솔루션을 합쳐서 전체 문제에 대한 솔루션을 구하는 방식binary search(이진 탐색), quick sort(퀵 정렬), merge sort(병합 정렬), matrix mulitplication(행렬 곱셈), Fast Fourier Trnasform(고속 푸리에 변환), skyline algorithm(스카이라인 알고리즘) 등에서 사용되는 패러다임이다.분할 정복..

[Algorithm] Introduction

Introduction of Algorithm자료 구조 : 다양한 방식의 데이터 저장 방식을 의미하고, 그 안에 저장된 데이터에 접근하는 데 필요한 비용을 결정알고리즘: 주어진 문제가 있을 때, 데이터에 대한 정확한 정의와 데이터 변환 순서에 대한 일련의 명령알고리즘의 좋고 나쁨은 알고리즘 동작의 효율성에 의해 결정된다. 또는 알고리즘 수행에 필요한 명령의 개수도 판단의 근거가 될 수 있다.알고리즘 문제 분류(계산 복잡도 기준)P 문제: 다항 시간 알고리즘을 이용하여 솔루션을 구할 수 있는 문제NP 문제: 특정 솔루션을 다항 시간으로 검증할 수는 있지만 알려진 다항 시간 솔루션은 없는 경우EXPTIME 문제(지수 시간 문제): 입력 크기에 대한 지수 함수 형태의 시간 복잡도 솔루션을 갖는다PSPACE(다..

[HTTP] HTTP 메서드

HTTP 메서드HTTP API를 만들어보자HTTP 메서드 - GET, POSTHTTP 메서드 - PUT, PATCH, DELETEHTTP 메서드의 속성HTTP API 만들기Example.요구사항 : 회원 정보 관리 API 만들기회원 목록 조회회원 조회회원 등록회원 수정회원 삭제API URI 설계회원 목록 조회/read-member-list회원 조회/read-member-by-id회원 등록/create-member회원 수정/update-member회원 삭제/delete-member이것이 과연 좋은 URI 설계일까?URI는 리소스를 기준으로 설계를 해야한다.URI에서 가장 중요한 것은 리소스 식별이다리소스의 의미?회원을 등록하고 수정하고 조회하는 것이 아님ex) 미네랄을 캐는 동작에서 미네랄이 리소스임회원이..

[Modern C++] std::move, std::forward

추후 내용 보충. 예정 std::move와 std::forward는 모두 C++11 이후부터 도입된 유틸리티 함수들로, 둘 다 값의 전달 방식을 조절하는 데 사용됩니다. 그러나 각각의 역할과 사용하는 상황이 다르므로, 이 둘을 정확히 이해하는 것이 중요합니다.std::move역할: std::move는 주어진 인자를 "이동"할 수 있도록 하는 역할을 합니다. 이동(move)이란 객체의 자원(메모리 등)을 다른 객체로 옮기는 것을 말하며, 복사보다 효율적인 자원 관리를 가능하게 합니다.사용 방법: std::move는 주로 객체를 이동할 때 사용됩니다. 이 함수는 주어진 인자를 rvalue reference로 변환하여, 이동 연산자(move constructor 또는 move assignment operato..

[C++ STL] std::tuple

std::tuple이란?기존에 다른 데이터 타입의 값 2개를 저장하기 위해 pair를 사용했지만, first와 second 두 개의 요소만 관리할 수 있었다.C++11부터 STL에서 tuple을 제공하여 다수의 요소를 관리할 수 있는 tuple을 제공한다.에 정의되어 있다. 기본 사용법#include #include int main() { // 다양한 타입의 요소들을 포함하는 튜플 생성 std::tuple myTuple(1, 3.14, "Hello"); // 튜플의 요소에 접근 std::cout (myTuple) (myTuple) (myTuple)  별 특이한 점은 없지만, std::get을 사용할 수 있다. std::getstd::get 템플릿 함수를 이용해서 튜플의 요소에 접근할..

[C++ STL] std::string

std::string이란?STL에서 제공하는 문자열 처리 클래스동적 길이 문자열을 다루기 쉽게 만들어준다.에 정의되어 있다. 내부 구현?문자열의 크기에 따라 동적으로 할당하여 문자열 데이터를 저장한다짧은 문자열은 내부 버퍼에 따로 저장하여 동적 할당을 하지 않는다복사 및 연산 과정에서 기본적으로 깊은 복사를 사용한다. 포인터나 참조가 기반으로 관리되지 않는다초기화기본 생성자 : 빈 문자열 생성std::string s; C-스타일 문자열로부터 생성std::string s1("Hello");std::string s2 = "Hello";std::string s3 = ""; 반복자로부터 생성std::string s(iter1, iter2); 특정 문자 n개로 초기화std::string s(5, 's');// "..

[C++ STL] std::pair

std::pair란?두 개의 이질적인 데이터 타입의 값을 하나로 묶어서 저장하는데 사용되는 템플릿 클래스두 개의 값을 리턴해야 해야 하거나, 두 개의 값을 key와 value로 사용하는데 유용하다에 정의되어 있다. std::pair의 구현 방식실제 구현 코드는 아니지만, 이러한 방식으로 구현되어 있다template struct pair { T1 first; T2 second; // 기본 생성자 pair() : first(T1()), second(T2()) {} // 사용자 정의 생성자 pair(const T1& a, const T2& b) : first(a), second(b) {} // 복사 생성자 template pair(const pair& p) :..

friend 선언(클래스, 함수)friend는 친구라는 의미를 가지고 있다.클래스의 friend 선언클래스를 friend로 선언한다는 것은 어떤 의미일까? 예를 들어 클래스 A와 B가 있다고 해보자. 이 때 클래스 A가 "클래스 B는 내 믿을만한 친구야."라고 컴파일러에게 알려준다. 그러면 클래스 B에서 클래스 A의 모든 멤버(private까지)를 접근할 수 있게 된다A 클래스가 B 클래스를 friend 클래스로 선언하면, B 클래스는 A 클래스의 private 멤버까지 직접 접근이 가능하다.a.GetX()가 아니라 a.x 이런식으로 직접 접근이 가능해진다반대로 A 클래스가 B 클래스의 private멤버까지 직접 접근을 하기 위해서는 B 클래스에서 A 클래스를 frined 클래스로 선언해줘야 한다즉, 클..

스마트 포인터스마트 포인터를 이용하면 동적할당된 메모리를 알아서 지워준다3가지 종류 존재unique_ptrshared_ptrweak_ptrunique_ptrint *a = new int(5);를 스마트 포인터를 이용하여 동적할당해보자#include #include using namespace std;int main() { // int *a = new int(5);를 스마트 포인터를 이용하여 생성해보자 // 다음은 불가능 // unique_ptr a = new int(5); unique_ptr a(new int(5));}unique_ptr a = new int(5);은 불가능함이 경우 변환 생성자가 호출되는데, 스마트 포인터의 경우 묵시적 형변환이 불가능하기 때문따라서 생성자를..