꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/CHRISTMASH에서 T까지 구입했을 때 남기지 않고 어린이들에게 나눠줄 수 있는지 여부는 K로 나누어지는지 여부와 같다는 것이 핵심인 문제였습니다.즉, psum[i]=∑(i번째 인형상자) % K 이다. #include #include #include #include //memset using namespace std; const int MAX = 100000; //D[]의 부분 합 배열 psum[]과 k가 주어질 때, 몇 가지 방법으로 살 수 있는지 반환 //psum[]의 첫 번째 원소 전에 0을 삽입했다고 가정 int waysToBuy(const vector &psum, int K) { const int MOD..

부분합을 이용하여 합이 0에 가장 가까운 구간의 합을 구하는 프로그램입니다. /* 합이 0에 가장 가까운 구간의 값 구하기 */ #include #include #include #include using namespace std; const int MAX = 987654321; int compare(const void *num1,const void *num2) //ascending { return (*(int*)num1 - *(int*)num2); } int rangeValue(const vector &v) { int psum[50]; psum[0] = v[0]; //부분합 구하고 for (int i = 1; i < v.size(); i++) psum[i] = psum[i - 1] + v[i]; //부분..

문제 링크입니다: https://algospot.com/judge/problem/read/GRADUATION비트마스크를 이용해 풀면 배열을 사용했을 때보다 훨씬 빠르게 풀리는 문제였습니다.비트마스크를 사용하면 배열의 단점인 삽입, 삭제 실행시간을 확실히 줄일 수 있습니다.예를 들어 과목을 삭제할 때는 canTake &= ~(1 50) exit(-1); for (int j = 0; j > majorNum >> required >> semesterNum >..

문제 링크입니다: https://algospot.com/judge/problem/read/NERDS(신발 사이즈, 타이핑 속도)를 이차원 평면에 표시하고 너드인 그룹들과 너드가 아닌 그룹들 사이에 직선을 그을 수 있다면 이론이 성립함을 알 수 있습니다.다시 말해서 너드인 그룹 전부를 포함하는 볼록 다각형과 너드가 아닌 그룹 전부를 포함하는 볼록 다각형 사이에 교차 지점이 없을 경우 이론이 성립하고 교차지점이 있다면 이론이 성립하지 않습니다.볼록 다각형을 구하기 위해 선물 포장 알고리즘( https://en.wikipedia.org/wiki/Gift_wrapping_algorithm)을 사용했습니다. /*알고스팟에서 매년 진행하는 프로그래밍 대회가 가까워지고 있다.올해는 열기가 특히 뜨거워, 참가 신청자의..

문제 링크입니다: https://algospot.com/judge/problem/read/TREASURE진심으로 고등학교 수학 문제집을 다시 펼쳐봐야겠다고 다짐하게 했던 문제였습니다.볼록 다각형은 여러 반평면의 교집합으로 구할 수 있습니다.볼록 다각형의 각 변을 반시계 방향으로 순회하면서, 각 변을 포함하는 직선의 왼쪽 반평면들을 모두 모으면 이들의 교집합은 해당 볼록 다각형이 됩니다.따라서 주어진 직사각형의 변들을 직선으로 간주하고 각각 주어진 다각형을 자른다고 생각했을 때 왼쪽에 있는 부분(반평면)을 반환한 뒤 그들의 교집합을 구하면 답을 구할 수 있습니다.(이 때 자르는 순서는 반시계방향) 반평면의 꼭지점을 얻는 방법은 다음과 같습니다.1. 다각형의 꼭지점 중 직선의 왼쪽에 있는 점들은 모두 결과 ..

문제 링크입니다: https://algospot.com/judge/problem/read/PINBALL우선 문제를 간단하게 만들기 위해 공의 반지름이 1이기 때문에 공을 점으로 바꾸고 장애물의 반지름을 각각 1 증가시켰습니다.공의 궤적을 시간 time에 대해 f(time)=here+time*dir로 표현했습니다. 여기서 here는 현 위치를 벡터로 표현한 것이고 dir은 공이 향하는 방향을 벡터로 표현한 것입니다.중심이 center이고 반지름이 radius인 장애물과 교차하는 시간은 (center-f(t))*(center-f(t))=radius*radius로 표현할 수 있습니다.위 이차방정식의 해를 근의 공식을 이용하여 구하였고 이를 통해 부딪히는 장애물 번호를 순차적으로 출력했습니다. 아래는 공이 장애..

문제 링크입니다: https://algospot.com/judge/problem/read/POTION직관적인 방법을 사용하면 이중 루프를 돌리기 때문에 실행시간이 느리지만 유클리드 알고리즘을 이용하여 최대공약수를 이용하면 훨씬 빠른 시간 내에 프로그램이 작동합니다.또한 put[i]/recipe[i]를 직접 구하는 대신 ceil(put[i]*b, recipe[i])의 최대값을 구하는 것이 관건이였습니다. #include #include #include using namespace std; //마법의 약 레시피와 이미 넣은 재료의 양이 주어질 때, 더 넣을 재료의 양을 구한다 //직관적인 방법 /* vector solveSimulation(const vector &recipe, vector put) { in..

문제 링크입니다: https://algospot.com/judge/problem/read/PASS486완전탐색법과 에라토스테네스의 체, 총 두가지 방법으로 풀어봤습니다.완전탐색법은 http://jaimemin.tistory.com/440?category=988050와 비슷하게 풀었습니다.'만취한 상범' 문제에서는 한번 지나갈 때마다 문을 여닫았지만 이 문제에서는 약수의 갯수를 추가했습니다.에라토스테네스의 체를 이용한 방법은 소인수분해했을 때 약수의 갯수 = Π(i번째 지수+1) 공식을 이용하여 풀었습니다.예를 들자면 100= 2^2 * 5^2입니다. 따라서 약수의 갯수는 3 * 3 = 9 입니다.100의 최소 약수인 2를 나누면 50 = 2 * 5^2 이므로 약수의 갯수는 2 * 3 = 6 입니다.100..

에라토스테네스의 체를 이용한 소인수 분해 코드입니다. /* 에라토스테네스의 체를 이용한 빠른 소인수 분해 */ #include #include #include using namespace std; const int MAX = 1000000; int N; //소인수분해하고자 하는 수 //minFactor[i]=i의 가장 작은 소인수(i가 소수인 경우 자기 자신) int minFactor[MAX]; //에라토스테네스의 체를 수행하면서 소인수분해를 위한 정보 저장 void eratosthenes(void) { //1은 항상 예외 처리 minFactor[0] = minFactor[1] = -1; //모든 숫자를 처음에는 소수로 표시 for (int i = 2; i N) { cout

문제 링크입니다: https://algospot.com/judge/problem/read/FOSSILhttp://jaimemin.tistory.com/442?category=985009와 같이 삼분법을 통해 푸는 문제였습니다.두 개의 볼록 껍질(다각형)의 교집합 다각형의 꼭지점을 일일이 구하는 대신 주어진 두 다각형의 범위 내를 수직선으로 잘라 보고 잘리는 부분의 최대 길이를 찾았습니다.다행히도 두 개의 볼록 다각형의 교집합은 무조건 볼록 다각형입니다.해당 교집합을 중심으로 위 껍질과 아래 껍질로 나누면 오목 함수와 볼록 함수 모양이 나오고 특정 위치에서 이 다각형을 잘랐을 때 잘리는 부분의 길이를 나타내는 함수가 (오목 함수-볼록 함수)이므로 삼분법을 적용할 수 있는 오목 함수임을 알 수 있습니다. #..