버러범의 개발이야기

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

조세푸스를 포함해서 병사들이 원형으로 앉아 순서대로 죽는다.

첫번째 병사가 처음으로 죽으면, 시계방향으로 k번째 사람이 죽기를 반복하다가 조세푸스를 포함한 병사 하나만 살아 남았을때 죽는것을 멈춘다고 한다.

이렇게 조세푸스가 마지막 두명중 하나가 되기 위해서는 조세푸스는 첫번째 병사로부터 몇자리 떨어진 곳에 있어야 하는지 구하는 문제이다.

이 문제를 풀려면 요소들을 순회하면서 삭제하는 작업을 반복적으로 해야한다.

이때 우리는 다양한 곳에서 요소를 추가/삭제할때 상수시간복잡도를 가지는 연결리스트( list )를 활용할 수 있다.

배열( vector, int[] )의 경우 맨 뒤 이외의 위치에서 원소 추가/삭제를 수행할때 선형시간복잡도를 가진다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/18.%20linearDS/JOSEPHUS.cpp

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

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

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

상자마다 인형이 담겨있는 갯수가 각각 다르게 주어졌을때, 아이들k명에게 똑같은 갯수의 인형을 남는 인형 없이 나누어 주려 한다.

주문을 할때 'h번 상자부터 t번 상자까지 다 주세요'(h<=t)라고만 할 수있다.

한번 만 주문할 수 있는 경우 가능한 주문 방법,

한 상자가 주문에 중복으로 포함 되지 않게끔 여러번 주문 할수 있는 경우 최대 주문 횟수, 이렇게 두가지를 구하는 문제이다.

h에서 t까지 구입했을때 남기지 않고 나눠줄 수 있는 경우는 (psum[t]-psum[h-1])%k==0인 경우다.

한번 만 주문할 수 있는 경우 가능한 주문방법 = 나머지가 같은 것들끼리 묶고, 각 묶음에서 두개를 뽑는 조합의 경우

0번부터 i번까지의 상자가 있고, 여러번 주문 할때 최대 주문 횟수를 maxBuys(i)라 할때

maxBuys(i) = max( maxBuys(i-1), maxBuys(j)+1) (이때 j는 psum[i]==psum[j]인 i보다 작은 최댓값)

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/17.%20partial%20sum/CHRISTMAS.cpp

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

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

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

집과 치킨가게의 좌표가 N*N배열 형태로 주어진다.

m개의 치킨집을 남기고 구할 수 있는 각 집에서 가장 가까운 치킨 집과의 거리 합의 최솟값을 구하는 문제이다. 

집들과 치킨집들의 좌표를 각각의 벡터로 관리해준다.

좌표로 주어진 치킨집들중에 m개의 치킨집을 남겨야되는 작업은 재귀를 통해서 치킨집을 전체 순회하면서 구할 수 있다.

현재 치킨집을 남기는 경우와 폐업시키는 경우를 각각 재귀호출해서 더 작은 값을 반환 하는 쪽의 도시 치킨 거리를 반환한다.

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

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

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

배낭에 담을 수 있는 무게가 제한 되있고, 각 물건들의 가치와 무게가 주어진다.

이때 배낭에 담을 수 있는 물건들의 가치의 최댓값을 구하는 문제이다.

주어진 물건들을 차례대로 순회하면서 담을지 안담을지를 결정한다. 담았을 경우 현재 배낭에 무게에 담고자 하는 물건의 무게를 추가하여 다음 물건을 결정하는 재귀를 호출하고, 안담았을 경우 현재배낭에 무게 그대로 다음 물건을 결정하는 재귀를 호출한다. 이 두 재귀중 큰 값을 반환하는 경우의 값을 return하면 된다.

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

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

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

각 학기마다 열리는 전공과목을 선수과목과 학기당 들을 수 있는 최대 과목수를 고려하여 알맞게 수강했을때

졸업요건을 충족시키는 최소 이수 학기를 구하는 문제이다. 

현재 학기와 이제까지 들은 과목들이 주어졌을때 앞으로 들어야 하는 최소 학기를 반환하는 함수를 만들고

메모이제이션을 사용하는 다이나믹 프로그래밍기법을 이용하면 문제를 풀 수 있다.

이때 각 과목의 선수과목과 각 학기에 열리는 과목들을 비트마스크 기법을 사용하여 표현한 것에 주목하자.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/16.%20bitmask/GRADUATION.cpp

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

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

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