나만의 작은 도서관

parametric search란?parametric search는 최적화 문제를 결정 문제로 바꾼 뒤 이진 탐색을 이용해 최적해를 찾는 방식이다.  최적화 문제와 결정 문제최적화 문제(mathematical optimization problem)는 주어진 조건을 만족하는 여러가지 해 중에서 가장 최적해를 구하는 문제이다. 우리가 접하는 대부분의 알고리즘 문제들이 최적화 문제이며, "OO을 만족하는 최솟값을 구하시오" 또는 "OO을 만족하는 최댓값을 구하시오" 와 같이 적혀있는게 특징이다. 결정 문제(decision problem)는 주어진 조건을 만족하는 해가 존재하는 지 여부를 구하는 문제로, YES 또는 NO 이렇게 단 두 가지의 결과만이 나온다는 것이 특징이다. 예로, "X라는 값이 배열 arr에..

이진 탐색이란?이진 탐색은 정렬된 일련의 값들에서 찾고자 하는 값을 중앙값과 비교한 다음, 비교 결과에 따라 탐색 범위를 중앙값 왼쪽 범위 또는 오른쪽 범위로 줄이며 값을 찾아가는 방식을 의미한다. 매 반복마다 탐색 범위가 절반씩 줄어들기 때문에 시간복잡도는 O(logN)으로 속도가 매우 빠르다는 장점이 있지만 정렬되어 있어야한다는 제약조건이 있다. 동작방식이진 탐색을 구현하는 방법은 구현한 사람의 스타일에 따라 조금씩 달라진다. 아래의 동작방식은 내가 사용하기 편한 방법을 토대로 설명한 방식이다.(설명은 오름차순으로 정렬된 배열을 기준으로 한다.) 1. 초기화시작은 위 그림같이 start는 배열의 첫번째 위치, end는 배열의 마지막 위치 + 1로 초기화한다.   2. 범위 나누기초기화 이후 탐색을 시..

입력으로 주어지는 한자리 숫자들이 붙어있어 하나의 숫자로 인식되는 경우나, 숫자로 된 문자열을 계산해야 하는 경우처럼 문자열을 숫자로, 숫자를 문자열로 변환(casting) 해야하는 상황이 종종 발생한다. 이럴 때 유용하게 사용할 수 있는 함수가 stoi(), to_string()이다. stoi() // stoi(바꾸고자 하는 문자열) inline int stoi(const string& __str, size_t* __idx = 0, int __base = 10) { return __gnu_cxx::__stoa(&std::strtol, "stoi", __str.c_str(), __idx, __base); } String TO Integer의 약자로, 바꾸고자 하는 문자열을 int 자료형으로 변환한다. 해..

개요 알고리즘을 짜다보면 나올 수 없는 값들이 필요한 경우가 종종 생긴다. 10000이하의 자연수만 나오는 알고리즘에 99999라든가, 10001 이라든가 어찌되었든 나오지 않는 값을 하나 설정해 적절한 방향으로 알고리즘을 돌리게 된다(보통 방문 여부에 쓴다.) 이 때, 여러 알고리즘들을 한 번에 볼 때 알아차리기 쉽게 c++에서 만들어 놓은 "XXX_MAX" 시리즈를 사용하고자 한다. #define으로 정의된 XXX_MAX 시리즈 표 마무리하며 vs_code 같은 IDE 프로그램을 사용하게 되면 앞부분만 쳐도 추천 리스트에 뜨니 '이런게 있구나'하는 생각만 가지고 있자.

여러가지 프로그래밍 언어를 배우다 보면 문자열에 대한 의심이 많아진다. 어떤 언어는 같고, 어떤 언어는 같지 않고... 언어에 따라 달라지니 문자열 판정은 늘 헷갈리는 문제이다. 이 글은 C++에서 서로다른 변수가 같은 문자열을 가지면 같은 판정인지 실험해본 내용을 담고있다. #include #include using namespace std; int main(void) { string str = "Hello"; string str2 = "Hello"; if (str == "Hello") cout

https://www.acmicpc.net/problem/25643 25643번: 문자열 탑 쌓기 인경이는 $N$개의 문자열을 쌓아서 문자열 탑을 완성하려고 한다. 탑을 완성하기 위해서는 모든 문자열을 한 층에 하나씩 아래에서부터 순서대로 쌓아 올려야 한다. 인경이는 문자열 탑의 꼭대 www.acmicpc.net 백준 25643번 문제와 같이 입력받은 문자열의 일부만이 필요한 경우가 있다. 이 때, 문자열의 일부를 반환하는 함수 substr()을 사용하여 원하는 문자열을 얻을 수 있다. substr() // pos: 문자의 위치, count: 반환할 문자열의 길이 basic_string substr(size_type pos = 0, size_type count = npos) const; 문자열의 pos번..