꾸준함

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

문제 링크입니다:https://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&page=show_problem&problem=1326 '프로그래밍 대회에서 배우는 알고리즘 문제해결전략' 책에서 삼분법을 소개할 때 예시로 든 문제였습니다.algospot과 BOJ가 상당히 친절한 알고리즘 사이트라는 것을 깨달았습니다. 매수를 한 사람을 함수로 표현하면 (달린 거리/달리는 평균 속도) + (자전거 탄 거리/자전거 평균 속도) 이므로 달린 거리에 대한 선형함수입니다.또한, 2등을 한 사람도 똑같이 선형함수이므로 결과인 (매수를 한 사람이 걸린 시간) - (2등을 한 사람이 걸린 시간) 또한 위로 볼록한 함수임을 알 수 있습니다.삼분 검색은 미분할 수 ..

문제 링크입니다: https://www.acmicpc.net/problem/1937'프로그래밍 대회에서 배우는 알고리즘 문제해결전략' 책에서 익힌 메모이제이션을 통해 문제를 해결했습니다.문제의 조건을 코드로 잘 옮기는 것이 관건이였습니다. /* n*n의 크기의 대나무 숲이 있다.욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다.그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_ - ) 이 판다의 사..

문제 링크입니다: https://algospot.com/judge/problem/read/RATIO불가능한 경우를 찾을 때 총 게임 뿐만 아니라 이긴 게임에도 L을 더해주는 것이 핵심이였습니다. /* 싸비는 윈도우XP 운영체제에 포함되어 있는 스파이더 카드게임을 매우 좋아한다. 처음에는 지는 경우가 있었는데, 점점 연습을 함에 따라 필승법을 발견하였고 매번 승리를 하게 되었다. 스파이더 게임을 하면 플레이어에 대한 정보가 다음과 같이 주어지는데 싸비는 이것을 보다 표시되고 있는 승률을 1 % 이상 올리기 위해선 최소한 몇 번의 연승이 필요한지 의구심이 들었다. 플레이 횟수 : N 승리 횟수 : M(Z %) 여기서 Z%의 경우 소수점을 제외한 부분의 승률이다.즉, 승률이 88.68% 일 경우 Z = 88 ..

문제 링크입니다: https://algospot.com/judge/problem/read/LOAN간단한 이분법 문제였습니다.문제의 조건 3가지를 잘 이해했다면 별 문제 없이 프로그램이 동작했을 것입니다. /* 집을 떠나 혼자 살게 된 재훈이는 회사 근처의 전세집을 알아보고 있습니다. 전세금은 N원인데, 재훈이는 이것을 연이율 P%로 대출받을 수 있습니다. 재훈이는 M개월 동안 매달 일정액 C원씩을 갚으려고 합니다. 대출의 잔금은 대출 기간 동안 다음과 같이 변화합니다. ᆞ대출의 잔금은 대출 금액 N원에서 시작합니다. ᆞ한 달이 지날 때마다 대출 잔금이 월 이자 (P/12)% 만큼 불어납니다. ᆞ이자가 추가된 다음 월 상환액 C를 대출 잔금에서 제합니다. M개월 걸려 모든 대출 금액을 갚기 위해서는 한 달..

문제 링크입니다: https://algospot.com/judge/problem/read/ROOTS미분을 알아야 풀 수 있는 문제였습니다.다항 방정식(f(x))을 미분한 함수(f`(x))의 근을 극점이라고 합니다.극점은 쉽게 말해 다항 방정식이 꺽이는 지점인데 극점과 극점 사이에 다항식의 해가 존재합니다.따라서 이 문제는 다항식을 미분하고 극점을 찾은 다음에 이분법을 이용하여 극점과 극점 사이에 있는 근들을 찾아내면서 푸는 문제였습니다.[빨간별이 극점]첫번째 극점과 마지막 극점은 비교 대상이 없으므로 근의 범위 L을 지정하고첫번째 극점과 -L 사이의 근을 찾고 마지막 극점과 +L 사이의 근을 찾았습니다. /* 실수 근만을 갖는 ax2 + bx + c = 0과 같은 형태의 단변수 다항 방정식이 주어질 때,..

문제 링크입니다: https://algospot.com/judge/problem/read/WITHDRAWAL기존의 이분법 문제와는 달리 decision 함수에 전달한 매개변수를 정하기 어려운 문제였습니다.그래서 문제를 좀 유연하게 접근하여 ((전달할 매개변수)*수강인원 - 등수)의 값을 비교하며 값을 구했습니다. /* 중략 */ #include #include #include #include using namespace std; const int MAX = 1000; int N, K; //수업 갯수, 장학금 타기 위한 최소 수업 갯수 int classmate[MAX], rating[MAX]; //수업 인원, 등수 //결정 문제: 누적 등수 average가 되도록할 수 있나? bool decision(do..

문제 링크입니다: https://algospot.com/judge/problem/read/KAKURO1http://jaimemin.tistory.com/416?category=985009과 반대로 카쿠로 퍼즐의 답이 주어졌을 때 http://jaimemin.tistory.com/416?category=985009의 입력양식을 출력해내는 문제였습니다.물론 난이도는 KAKURO2와는 비교도 안되게 쉬웠습니다.#include #include #include //memset using namespace std; const int MAX = 20; int N; int board[MAX][MAX]; vector h; //가로 (y, x, 0, 힌트) vector v; //세로 (y, x, 1, 힌트) void ho..