버러범의 개발이야기

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

F= A * 신발 사이즈 + B * 분당 타이핑 속도 인 F가 있고 사람마다 신발사이즈와 분당 타이핑 속도가 주어졌을때 F가 일정 점수 이상인 사람을 너드로 추측한다고 하자.

사람마다 너드인지 여부와 신발 사이즈, 분당 타이핑 속도 이렇게 3가지 속성이 주어졌을때, 이 사람들의 너드 여부를 정확하게 추측할 수 있는 F= A * 신발 사이즈 + B * 분당 타이핑 속도 가 존재하는지를 예측 문제이다.

먼저 (신발 사이즈, 분당 타이핑 속도)를 (x,y)좌표로해서 점을 찍어보자.

이때 너드인 사람에 대해서 A*x + b*y >=T 가 성립해야 하므로 너드인점들과 너드가 아닌 점들을 나눌수 있는 직선이 존재해야 한다.

이것을 좀더 해결하기 쉽게 바꾸자면 너드인 점들로 이뤄진 볼록 다각형과 너드가 아닌점들로 이뤄진 볼록 다각형에 겹치는 부분이 있는지를 계산하면 된다.

그러기 위해서는 먼저 너드인 점과 너드가 아닌 점들을 각각 포함하는 볼록 다각형 두개를 만든다.

어느 한 다각형이 다른 다각형에 포함되거나, 두 다각형에 서로 닿는 두 변이 존재하는지를 확인한다.

포함여부를 확인할때는 어느 한 다각형의 꼭짓점 하나가 다른 다각형안에 있는지를 보면 되는데, 이것은 꼭짓점에서 반직선을 그어 다각형의 변과 교차하는 점을 확인하면 된다.

교하는 점의 갯수가 홀수면 꼭짓점은 다른 다각형 안에있고 짝수면 밖에있다. 

이때 주의할 점은 반직선이 다각형의 꼭짓점을 지날때인데 이것을 처리하기 위해서 반직선을 살짝 올린다는 개념으로 가로지르는지를 확인할때 부등호를 생략한다.

그러면 다각형의 꼭짓점 기준 위에 선분은 교차하고 아래 선분은 교차하지 않는것으로 처리되어 정상작동하게 된다.

코드원본: https://github.com/sbl133/JongmanBook/blob/main/15.%20ComputationalGeometry/NERD.cpp

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

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

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

하나의 다각형과 하나의 직사각형에 교집합인 교집합 다각형의 넓이를 구하는 문제이다.

먼저 다각형을 직사각형의 각변을 포함하는 직선으로 잘랐을때, 해당 직선 왼쪽에 있는 다각형의 꼭짓점들, 직선과 다각형의 교차점들을 모두 저장한다.

직사각형 각각의 변들에 따라 이 작업을 총 4번 반복하면 교집합 다각형의 꼭짓점만을 저장할 수 있다.

다각형의 점들 p0, p1, p2, ... p(n-1)이 반시계 순서대로 배열되면 벡터p(i)와 벡터p((i+1)%n)의 외적을 모두(i=0부터 n-1까지) 합해서 2로 나누면 다각형의 넓이를 구할 수 있다.

코드원본: https://github.com/sbl133/JongmanBook/blob/main/15.%20ComputationalGeometry/TREASURE.cpp

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

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

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

공의 처음 위치와 진행방향과 원형태의 장애물들이 주어졌을때 공이 몇번 장애물에서 튕겨졌는지 순서대로 출력하는 문제이다.

공의 크기를 고려하는 대신에 장애물들의 반지름을 1씩 늘려서 문제를 해결 해보자

공이 처음위치 p에서 1초에 d만큼 굴러간다 하면 f(t) = p+td로 표현할 수 있다. 그럼 중심이 c이고 반지름이 r인 장애물과 교차하는 시간은 다음 식을 이용해 구할 수 있다.

|c-f(t)| = r       양변을 제곱하여 전개하면(dot를 내적이라 하면)

d(dot)dt^2 + 2(p-c)(dot)dt + c(dot)c+p(dot)p-2(c(dot)p)-r^2=0

이때 t는 항상 양수여야 하고 실근이 두개 반환될 때에는 둘중 작은값이 장애물과 부딪히는 시간이라는것은 직관적으로 알 수 있다.

t를 통해 구한 충돌지점(contact)을 이용하여 -dir을 contact-center에 사영시키고 해당 벡터를 d`라고 하자

2(dir+d`)-dir = dir+2d`이 충돌지점에서 장애물에 부딪힌 후 공의 진행방향이다.

코드원본: https://github.com/sbl133/JongmanBook/blob/main/15.%20ComputationalGeometry/PINBALL.cpp

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

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

알고스팟 링크: 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