나만의 작은 도서관

최대공약수(GCD), 최소공배수(LCM) 구하는 법최대공약수(GCD, Greatest Common Divisor)는 두 자연수의 공통된 약수 중에서 가장 큰 수를 의미하며, 최소공배수(LCM, Least Common Muliple)는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.  최대공약수는 두 자연수를 나누어 떨어지게 하는 최댓값을 찾으면 되며, 최소공배수는 두 자연수를 곱하고 GCD만큼 나눠주면 된다. 이를 코드로 구현하면 다음과 같다.// 시간복잡도 O(N)int gcd(int a, int b){ int res = 0; for(int i = 1; i   N개의 자연수의 최대공약수를 구하고 싶은 경우2개의 자연수에 대한 최대공약수가 아닌 N개의 자연수에 대한 최대공약수를 구하고 ..

소수 판별법소수는 양의 약수를 2개만 가지는 자연수, 즉 1과 자기자신으로만 나누어 떨어지는 자연수를 의미한다(1 제외). 임의의 수 N이 소수인지 판별하기 위해선 2~N-1까지의 수들로 N이 나누어 떨어지지 않는 지 확인하면 된다. 코드로 구현하면 다음과 같다.// 시간복잡도 O(N)bool isPrime(int num){ for(int i = 2; i  최적화를 할 수는 없을까?위 코드는 최적화가 가능하다. 2 이상의 자연수 N에 대해서 N의 약수는 짝이 반드시 존재하고, 짝이 되는 약수 중 작은 쪽에 속하는 약수는 √ N을 초과할 수 없기 때문에 num까지가 아닌 √ N이하의 자연수까지만 루프를 돌면 된다. 따라서 코드에 적용하면 다음과 같다.// 시간복잡도 O(√N)bool isPrime(i..

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 프로그램을 사용하게 되면 앞부분만 쳐도 추천 리스트에 뜨니 '이런게 있구나'하는 생각만 가지고 있자.