버러범의 개발이야기

알고스팟 링크: https://algospot.com/judge/problem/read/POTION

마법약 한개를 만드는데 필요한 재료들의 양이 주어질때, 재료들의 비율들을 맞춰서 1개이상의 마법약을 만드는데 필요한 각 재료들의 최솟값을 구하는 문제이다.

먼저 put/recipe가 최대인 값을 X라 할때, X이상의 마법약을 만들어야 한다.

하지만 해당 재료 뿐 아니라 다른 재료들의 양도 정수로 맞춰야 하므로 X이상이고 recipe들과의 곱이 항상 정수인 유리수 a/b(b는 recipe들의 최대공약수)만큼의 마법약을 만들면 된다.

코드원본: https://github.com/sbl133/JongmanBook/blob/main/14.%20NumberTheory/POTION.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스팟 문제 링크: https://algospot.com/judge/problem/read/PASS486

[lo, hi] 범위 정수중에 n개의 약수를 가지는 정수의 갯수를 구하는 문제이다.

먼저 에라토스테네스의 체를 이용하여 해당 정수(index)가 가지는 소인수의 최솟값을 저장하는 배열(minFactor)을 만든다.

minFactor를 이용하면 해당 정수(index)를 소인수분해 했을때 제일작은 소인수가 몇승인지를 저장하는 배열(minFactorPower)와 해당 정수(index)가 가지는 약수의 갯수를 저장하는 배열(factor)를 생성할 수 있다.

factor는 해당 정수(index)의 가장 작은 소인수가 p이고, 이 소인수가 a번 출현 한다면(index를 소인수 분해 했을때 p의 지수가 a이면) factor[n] = factor[n/p] * (a+1)/a로 표현 할 수 있다.

코드원본: https://github.com/sbl133/JongmanBook/blob/main/14.%20NumberTheory/PASS486.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스팟 문제 링크: https://algospot.com/judge/problem/read/FOSSIL

볼록 다각형을 이루는 점들의 좌표가 반시계 방향으로 각각 두개 주어질때, 두 볼록 다각형이 이루는 교집합 다각형의 세로 길이 최댓값을 구하는 문제이다.

두 볼록 다각형의 교집합 다각형은 볼록 다각형이고 이는 삼분법을 이용하여 x좌표를 탐색하면 정답을 찾을 수 있다는것을 이미한다.

교집합 다각형을 추상화 하는 방법은 일단 각각의 볼록 다각형들의 오목 부분과 볼록부분을 나눠서 두 볼록 다각형 구분없이 저장한다.

그 다음 x좌표에 따른 교집합 다각형의 세로 길이를 구할때마다 x좌표에 해당하는 위로 볼록 부분중 작은 쪽, 오목 부분중 큰 쪽의 y좌표 차이를 확인하면 된다.

이제 x좌표에 따른 교집합 다각형의 세로 길이를 구할 수 있고 삼분법을 이용하면 적절한 답을 추적할 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/13.%20NumericalAnalysis/RATIO.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스팟 문제 링크: https://algospot.com/judge/problem/read/RATIO

N번의 게임을 해서 M게임을 승리했을때 승률을 1%올리려면 해야하는 최소 게임 수를 구하는 문제이다.

문제 조건에 의해 20억 게임을 넘게하면 더 이상 게임을 할 수 없으므로 hi값을 20억으로, lo값을 1로 하는 이분법을 실행하면 된다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/13.%20NumericalAnalysis/RATIO.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스파ㅅ 문제 링크: https://www.algospot.com/judge/problem/read/WITHDRAWAL

각 과목의 수강인원과 본인의 중간고사 등수가 주어지고, k개의 과목만을 남겨놓고 수강철회를 할 수 있다.

이때 얻을 수 있는 최소누적등수를 구하는 문제이다.

직관적으로 보면 r[i]/c[i]가 높은 순으로 수강철회를 하는 그리디 방식을 취하면 될것 같지만, 값을 몇번만 대입해봐도 이런 방식으로는 원하는 값을 얻을 수 없다는걸 알 수 있다.

해결책으로는 이분법을 사용하여 누적등수를 대입해가면서 sum(해당누적등수*c[i] - r[i])가 0이상인지 확인하는 방식으로 누적등수의 범위를 좁혀가면 된다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/12.%20DecisonProblem/WITHDRAWAL.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/CANADATRIP

각 도시마다 도시에 도착하기 거리 m전에 g간격으로 표지판들이 나열되어있다. 각 도시들의 갯수와 위치가 주어지고 도시들마다의 m과 g가 주어질때 k번째 표지판의 위치를 찾는 문제이다.

전체 거리가 8030000이기 때문에 완전탐색에는 무리가 있다.

해결 방법으로는 출발점부터 도착점까지 각각을 lo와 hi로 설정하고 이분법을 이용하여 중간지점까지 갔을때 지나친 표지판의 갯수를 계산하는 것이다.

만약 계산한 표지판의 갯수가 k보다 적으면 lo를 높이고 많으면 hi를 낮추면 된다.

표지판의 갯수를 셀때는 출발점부터 해당지점까지와 각 도시들의 표지판이 놓여져 있는 영역들의 겹치는 부분을 계산해서 g로 나누고 +1 해주면 된다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/12.%20DecisonProblem/CANADATRIP.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/ARCTIC

기지들의 위치가 좌표형태로 주어진다. 무전기가 거리 D안에서 통신 가능하고 각 기지국들이 간접적으로 연락할 수 있다고 할때 모든 기지들이 통신할 수 있는 최소 D를 찾는 문제이다.

최적화 문제이지만 D가 가질 수 있는 최대 최소를 시작으로 이분법을 사용하여 범위를 줄여나가면 최적해 D를 찾을 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/12.%20DecisonProblem/ARCTIC.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1

BOJ 문제 링크: https://www.acmicpc.net/problem/14503

로봇 청소기가 청소할 방에 벽과 청소가 안되있는곳을 각각1, 0으로 표현한 2차원 배열이 주워진다.

조건에 맞게 로봇청소기가 움직였을때 청소한 칸의 갯수를 출력하는 문제이다.

문제에 주어진 경우들을 switch문으로 나누어서 재귀호출하는 형식으로 문제를 해결할 수 있었다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314503.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!