꾸준함

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

문제 링크입니다: 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..

문제 링크입니다: https://algospot.com/judge/problem/read/CANADATRIP이번에도 이분법을 이용하여 푸는 문제였습니다.표지판을 일일히 나열하면 언젠가는 찾을 수 있겠지만 표지판의 개수가 (2^31 - 1)개일수도 있기 때문에 이분법을 이용하여 풀어야 시간 안에 동작합니다. /* 중략 */ #include #include using namespace std; const int MAX = 5000; const int drive = 8030000; //총 주행 거리 int N, K; //도시의 수, K번째 표지판 //도시까지의 거리, markStart미터 전부터 표지판 시작, interval미터마다 표지판 int length[MAX], markStart[MAX], interv..

문제 링크입니다: https://algospot.com/judge/problem/read/ARCTIChttp://jaimemin.tistory.com/421?category=985009와 유사하게 이분법을 사용하여 푸는 문제였습니다.한가지 흠이라면 ARCTIC은 북극이므로 제목을 북극기지로 지었어야했다는 점입니다. /* 남극에는 N 개의 탐사 기지가 있습니다.남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. ..

문제 링크입니다: https://algospot.com/judge/problem/read/DARPA답이 자연수로 표현 가능하더라도 소수 둘째자리까지 표현하는 것이 포인트이기 때문에 iomanip 헤더파일을 추가하고cout test_case; if (test_case 50) exit(-1); for (int i = 0; i > cameraNum >> installNum; for (int j = 0; j > coord; location.push_back(coord); } sort(location.begin(), location.end..

문제 링크입니다: https://algospot.com/judge/problem/read/KAKURO2상당히 흥미로운 문제였습니다.(물론 엄청 어려웠습니다...)책을 보면 볼수록 비트연산의 중요성을 깨닫고 있습니다. /* 카쿠로는 흔히 십자말풀이 수학 버전이라고 불리는 논리 퍼즐이다. 카쿠로는 위와 같이 생긴 정사각형의 게임판을 가지고 하는 퍼즐로, 이 게임판의 각 칸은 흰 칸이거나, 검은 칸이거나, 힌트 칸이다. (힌트 칸은, 대각선으로 갈라져 있고 숫자가 씌여 있는 칸을 말한다) 모든 흰 칸에 적절히 숫자를 채워 넣어 규칙을 만족시키는 것이 이 게임의 목표이다. 카쿠로의 규칙은 다음과 같다. 1. 모든 흰 칸에는 1 부터 9 까지의 정수를 써넣어야 한다. 2. 세로로 연속한 흰 칸들의 수를 모두 더하..