[Algorithm/Divide&Conquer] 03. Merge Sort(병합 정렬)
·
Computer Science/Algorithm
분할 정복을 이용한 정렬 알고리즘유명한 알고리즘 문제 중의 하나인 정렬(sorting)을 분할 정복으로 구현하는 방법에 대해 알아보자 정렬 알고리즘 구현에 있어 필요한 요구사항모든 데이터 타입에 대해 동작해야 한다. 심지어 C++ 구조체, 클래스에 대해서도 서로 다른 멤버를 기준으로 정렬할 수 있어야 한다많은 양의 데이터를 처리할 수 있어야 한다.점근적 시간 복잡도 측면이나 실제 동작 시에 빠르게 동작한다현실적으로 두 번째와 세 번째 요구사항을 동시에 만족하기는 어렵다. 두 번째 요구사항은 외부 정렬(external sorting), 즉 컴퓨터의 메모리에 데이터가 상주하지 않은 상태에서 수행되는 정렬을 필요로 한다.외부 정렬 알고리즘은 실행 중 임의 시점에서 전체 데이터의 일부만을 메모리에 올려놓고 동작..
[C++] stream(istream, ostream, sstream)과 stream insertion/extraction 연산자 (>>, <<)
·
Programming Language(Sub)/C++
C++에서 istream, ostream, sstream는 모두 표준 라이브러리에서 제공하는 스트림 클래스입니다. 이 클래스들은 입출력 작업을 추상화하여 파일, 콘솔, 문자열 등을 손쉽게 다룰 수 있도록 도와줍니다. 각각에 대해 자세히 설명하겠습니다.1. istreamistream은 입력 스트림을 나타내는 클래스입니다. 이 클래스는 데이터 입력을 위한 다양한 메소드를 제공합니다. istream의 주요 역할은 데이터의 입력을 관리하는 것입니다.주요 기능연산자 오버로딩 (>>, stream insertion operator): 데이터를 입력받을 때 사용하는 연산자입니다.ex) cincin은 c++ 표준 라이브러리에서 제공하는 객체로, istream 클래스의 객체임int x;std::cin >> x; // 콘..
[C++] std::distance, std::advance
·
Programming Language(Sub)/C++
(알고리즘 코드를 보다가 GPT를 통해서 얻은 답변을 따로 정리해둔 게시글이에요) std::distance()와 std::advance() 함수는 C++ 표준 라이브러리에서 제공하는 반복자 관련 함수입니다. 이 두 함수는 반복자를 다루는 데 유용하게 사용될 수 있습니다.std::distance()std::distance(first, last) 함수는 두 개의 반복자 first와 last 사이의 거리를 계산하여 반환합니다. 이 함수는 다음과 같은 형태로 사용됩니다:template typename std::iterator_traits::difference_typedistance(InputIt first, InputIt last);first: 거리를 계산할 첫 번째 반복자last: 거리를 계산할 두 번째 반복..
[Algorithm/Divide&Conquer] 02. 이진 검색(binary search)
·
Computer Science/Algorithm
이진 검색(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) 알고리즘
·
Computer Science/Algorithm
분할 정복 설계 패러다임효율적인 알고리즘을 설계하기 위한 일반적인 접근 방법이 개발되어 다양한 문제 해결에 사용되고 있다.분할 정복(divide-and-conquer)은 가장 널리 사용되는 알고리즘 설계 패러다임 중 하나이다.분할 정복 알고리즘이란?주어진 문제를 작은 부분 문제로 나누고, 나줘진 각 부분 문제의 솔루션을 구하고, 각 부분 문제 솔루션을 합쳐서 전체 문제에 대한 솔루션을 구하는 방식binary search(이진 탐색), quick sort(퀵 정렬), merge sort(병합 정렬), matrix mulitplication(행렬 곱셈), Fast Fourier Trnasform(고속 푸리에 변환), skyline algorithm(스카이라인 알고리즘) 등에서 사용되는 패러다임이다.분할 정복..
[Algorithm] Introduction
·
Computer Science/Algorithm
Introduction of Algorithm자료 구조 : 다양한 방식의 데이터 저장 방식을 의미하고, 그 안에 저장된 데이터에 접근하는 데 필요한 비용을 결정알고리즘: 주어진 문제가 있을 때, 데이터에 대한 정확한 정의와 데이터 변환 순서에 대한 일련의 명령알고리즘의 좋고 나쁨은 알고리즘 동작의 효율성에 의해 결정된다. 또는 알고리즘 수행에 필요한 명령의 개수도 판단의 근거가 될 수 있다.알고리즘 문제 분류(계산 복잡도 기준)P 문제: 다항 시간 알고리즘을 이용하여 솔루션을 구할 수 있는 문제NP 문제: 특정 솔루션을 다항 시간으로 검증할 수는 있지만 알려진 다항 시간 솔루션은 없는 경우EXPTIME 문제(지수 시간 문제): 입력 크기에 대한 지수 함수 형태의 시간 복잡도 솔루션을 갖는다PSPACE(다..
[HTTP] 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
·
Programming Language(Sub)/C++
추후 내용 보충. 예정 std::move와 std::forward는 모두 C++11 이후부터 도입된 유틸리티 함수들로, 둘 다 값의 전달 방식을 조절하는 데 사용됩니다. 그러나 각각의 역할과 사용하는 상황이 다르므로, 이 둘을 정확히 이해하는 것이 중요합니다.std::move역할: std::move는 주어진 인자를 "이동"할 수 있도록 하는 역할을 합니다. 이동(move)이란 객체의 자원(메모리 등)을 다른 객체로 옮기는 것을 말하며, 복사보다 효율적인 자원 관리를 가능하게 합니다.사용 방법: std::move는 주로 객체를 이동할 때 사용됩니다. 이 함수는 주어진 인자를 rvalue reference로 변환하여, 이동 연산자(move constructor 또는 move assignment operato..
[C++ STL] std::tuple
·
Programming Language(Sub)/C++
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
·
Programming Language(Sub)/C++
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');// "..