관심이 가는 개발 보물창고

cmath cmath에는 c++에서 각종 수학 함수들을 가지고 있다. 신기하게도 min, max는 algorithm에 구현되어있다는 것을 명심하자. 제곱 구하기 #include // C++ (함수 오버로딩 = 함수 중복 정의) double pow(double x, double y); float pow(float x, float y); float pow(float x, int y); long double pow(long double x, long double y); long double pow(long double x, int y); C++에서는 함수의 이름을 pow로 통일해서 사용하면 된다. 제곱근 구하기 #include double sqrt(double x); float sqrt(float x); lo..

유클리드 호제법? 두 수의 최대 공약수를 O(lgN)만에 구하는 방법이다. 생각보다 자주 까먹으니까.. 틈틈이 시간 나면 한 번씩 봐주자. 재귀 함수 구현 int gcd(int a, int b) { if(b == 0) return a; else return gcd(b, a % b); } 반복문 구현 전제 조건 : a > b while(1) { int r = a % b; if(r == 0) return b; a = b; b = r; } 최소 공배수는? int lcm(int a, int b) { return (a / gcd(a, b)) * (b / gcd(a, b)) * gcd(a, b); } 최소 공배수에서 gcd(a, b)를 3번이나 해주는 이유는 특정 구간에서 오버플로우의 방지를 막기 위해서이다.

정렬을 하다 보면 이런 문제들이 있다. www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 나이가 증가하는 순서로 정렬을 하지만 만약에 나이가 같다면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 문제 이러한 문제처럼 먼저 들어온 사람이 먼저 출력되는 것을 아래와 같이 정리할 수 있다. 정렬되지 않은 상태에서 같은 키(나이) 값을 가진 원소의 순서가 정렬 후에도 유지가 되는가? 이러한 개념이 바로 Stable Sort 이라고 하며 안정된 정렬이라고 불린다. Stabl..