꾸준함

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

문제 링크입니다: https://www.acmicpc.net/problem/1890번역이 살짝 아쉬운 문제였습니다.처음에는 해당 칸에 있는 숫자만큼 움직일 수 있는 경우라고 이해해서 답보다 훨씬 많은 경로를 구했습니다.문제에 해당 칸에 있는 숫자만큼 "한 방향"으로 움직일 수가 있다고 했더라면 고생하지 않았을 것 같습니다.답이 2^63 - 1까지 나올 수 있으므로 자료형을 long long으로 선언하는 것이 핵심이였습니다. /* N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 ..

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

문제 링크입니다: https://www.acmicpc.net/problem/11051이산수학 과목에서 이미 조합을 구하는 점화식을 배웠으므로 쉽게 풀 수 있었던 문제였습니다. /* 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N, K)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. */ #include #include //memset using namespace std; const int MAX = 1001; const int MOD = 10007; int N, K; //주어진 수 int cache[MAX][MAX]; int binomialCoef(void) //이항계수 { for (int i = 1; i N >> K; if (N = MAX || KN) exit(-1)..

문제 링크입니다: https://www.acmicpc.net/problem/6359다이나믹 프로그래밍 주제에 있던 문제였지만 메모이제이션을 통해 풀지는 않았습니다.동적계획법으로 푸는 것보다 제가 푼 방법이 좀 더 쉬운 방법인 것 같습니다. /*서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다.각 방에는 벌점을 많이 받은 학생들이 구금되어있다.그러던 어느날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다.게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다.그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. 같..

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

문제 링크입니다: https://www.acmicpc.net/problem/1309사자를 배치하지 않을 경우는 전 줄의 배치에 영향을 받지 않는다는 것이 핵심이였습니다. #include using namespace std; const int MAX = 100000; const int MOD = 9901; int N; int cache[3][MAX + 1]; //0: 없다, 1: 왼쪽에 있다, 2: 오른쪽에 있다 int Lion(void) { //첫 번째 줄에 사자가 없을 수도, 왼쪽에 있을 수도, 오른쪽에 있을 수도 있다 cache[0][1] = cache[1][1] = cache[2][1] = 1; for (int i = 2; i > N; if (NMAX) exit(-1); cout

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

문제 링크입니다: https://www.codewars.com/kata/factorial-decomposition/train/cpp완전탐색법을 통해 푼 문제였습니다.시간 단축을 위해 vector v를 선언하여 first에는 n 이하 자연수, second에는 지수가 저장되도록 하였습니다./* 주어진 N을 소인수 분해하시오 */ #include #include #include using namespace std; std::string decomp(int n) { //your code here string result; vector v(n + 1, make_pair(0, 0)); for (int i = 1; i

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