버러범의 개발이야기

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

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

정사각형 모양의 게임판을 주어진 힌트에 알맞게 숫자(1~9)로 채워야 하는 문제이다.

비트마스크 기법을 수월하게 다룰줄 알아야하고, 게임판과 힌트에 대한 정보들을 여러가지 2차원 배열들로 표현하여 문제를 풀여야 하기 때문에 무척 까다로운 문제였다.

어떤 정수를 비트단위로 쪼개서 부분집합을 만들때 해당 정수를 -1한 값을 해당정수와 비트연산 & 하기를 반복하면 모든 부분집합을 순회할수 있다는게 흥미로웠다. 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/11.%20CombinatorialSearch/KAKURO2.cpp

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

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

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

n명의 친구들 각자가 m개의 음식중 먹을 수 있는 음식들이 입력으로 주어졌을때 한개의 음식도 먹지 못하는 친구가 발생하지 않게끔 하는 음식갯수의 최소값을 구하는 문제이다.

해결방법으로는 음식을 한개도 먹지 못하는 친구를 찾아 그 친구가 먹을 수 있는 음식을 추가하고 재귀호출 하는 방식이 있다.

이때 친구들이 문자열로 주어지기 때문에 canEat이나 eaters 같은 벡터 배열에 접근하기 어려우므로 map을 사용하여 친구들에 해당하는 문자열들을 정수형태로 바꿔서 index접근이 수월하도록 하였다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20CombinatorialSearch/ALLERGY.cpp

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

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

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

게임판과 블럭이 입력으로 주어졌을때, 불규칙하게 부분적으로 채워진 게임판에 회전가능한 블럭을 놓을수 있는 최대값을 구하는 문제이다.

먼저 게임판에 채워진 부분을 1, 비어있는 부분을 0으로 표현한다. 그리고 주어진 블럭을 90도로 회전시켜가며 가능한 모양들을 좌표 형태로 저장한다.

이제 게임판에 빈칸들을 찾아내서 블록을 놓을 수 있으면 놓고 재귀호출 한다.

만약에 빈칸에 놓을 수 있는 블록의 모양이 없다면 해당 빈칸을 막아놓고 재귀호출한다. 그렇지 않으면 재귀호출을 했을때, 해당 빈칸에서 또 블록을 놓을 수 있는지 없는지 다시 계산을 반복하는식으로 무한루프에 빠진다.

이때 (현재 게임판에 놓은 블럭수) + (남은 빈칸들을 블럭크기로 나눈값) 이 지금까지 찾은 최적해보다 작다면 현재 탐색이 최적해가 될 수 없으므로 탐색을 그만둔다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20CombinatorialSearch/BOARDCOVER2.cpp

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

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

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

원모양의 성벽이 있고 시야가 원모양인 초소들이 성벽위에 있을때 성벽을 빈틈없이 감시할 수 있는 초소 갯수의 최솟값을 구하는 문제이다.

먼저 초소위치를 라디안으로 구하고 초소에 감시 반지름과 초소위치를 활용하여 각 초소의 감시범위를 라디안으로 저장한다.

이때 주의할점은 성벽을 [0, 2*pi]범위의 선분으로 표현할 때 시작점(끝점)을 덮는 초소들을 하나씩 순회하면서 먼저 계산하고 나머지 초소들로 남은 성벽범위를 덮어보면서 답을 찾아야 한다는 것이다.

시작점(끝점)을 덮는 초소를 골라 성벽의 나머지 부분을 begin과 end로 표현하고 초소의 시야가 begin전에 시작해서 가장 크게 뻗어나가는 초소를 골라 begin를 갱신하는 방식으로 begin이 end이상이 될때까지 반복한다.

시작점(끝점)을 덮는 초소는 많아야 최대 두개이고, 두 개일때도 둘중에 ranges[i].first가 음수인것은 시야가 시작점으로부터 끝점방향으로 더 길고 ranges[i].second가 2*pi이상인것은 시야가 끝점으로부터 시작점 방향으로 더 길수 밖에 없다는 점에 유의하자.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20Greedy/MINASTIRITH.cpp

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

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

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

여러개의 문자열이 주어졌을때 그 중 두개의 문자열을 선택해 하나의 문자열로 병합하는 과정을 반복하여 최종적으로 하나의 문자열을 만든다.

두개의 문자열을 하나로 합칠때에는 각각을 문자열의 길이만큼 훑어야 한다. 여러개의 문자열을 하나로 만들기 위해 훑어야 하는 문자열 길이의 최솟값을 구하는 문제이다.

문자열의 길이가 짧은 순서대로 병합하는 그리디 알고리즘으로 문제를 해결할 수 있다.

문자열의 길이가 짧은 순서대로 값을 꺼내어 합을 구한후 다시 삽입하여 정렬하는 과정이 필요하므로 priority_queue를 사용하면 간단히 구현할 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20Greedy/STRJOIN.cpp

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

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