버러범의 개발이야기

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

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

두 수열이 주어졌을때, 모두의 부분 수열이 되는 수열 중 가장 긴 것(LCS)을 찾는 문제이다.

두 수열을 순회하면서 두 수열중 하나가 다음 문자로 넘어가거나, 두 수열을 가르키는 문자가 서로 같으면 LCS에 추가하고 둘다 다음 문자로 넘어가는 재귀 호출을 하면서 가장 큰 값을 리턴하는 경우를 찾는다.

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

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

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

N자리 숫자가 주어졌을때, K개의 숫자를 지워서 얻을 수 있는 가장 큰 수를 구하는 문제이다.

문제 유형은 그리디였지만 덱을 이용하면 문제를 쉽게 풀 수 있어서 자료구조의 중요성을 더 깨닫게 되었다.

먼저 주어진 숫자들을 순회하면서 현재 숫자가 덱에 있는 숫자보다 크면 덱에 있는 숫자들을 꺼내고 해당 숫자를 넣는다. 얼핏보면 스택구조를 이용해서도 문제를 풀 수 있을거 같지만 마지막에 삭제하고 남은 숫자들을 출력하는 과정에서 스택으로 치면 맨 밑에 있는 숫자부터 출력 해야하기 때문에 덱 구조가 더 문제에 적합하다.

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

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

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

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

도시락의 갯수와 각 도시락마다 데우는시간, 먹는 시간을 입력으로 주어지고, 한번에 하나의 도시락을 데울 수 있으며 데운 도시락은 기다리지 않고 바로 먹는다고 했을 때, 필요한 총 식사시간을 구하는 문제이다.

모든 도시락은 무조건 1번씩 다 데워져야 되기 때문에 데우는 시간은 똑같다.

문제는 먹는시간인데 먹는시간이 오래걸리는 순서대로 데워서 바로 먹는 그리디 알고리즘을 이용하면 문제를 해결할 수 있다. 

정당성 증명으로는 최적해중에 먹는 시간이 오래걸리는 도시락을 비교적 덜걸리는 도시락보다 더 늦게 먹는 경우가 있다고 가정하자. 이때 두 도시락의 데우는 순서를 바꾸면 최적해 이하의 시간이 걸린다. 따라서 먹는 시간이 오래걸리는 순서대로 데워서 먹는 그리디 알고리즘의 정당성이 성립한다.

부분 구조 증명 또한 첫번째 도시락을 정했을 때, 나머지 도시락들에 대한 시간도 최소화 해야하므로 성립한다.

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

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

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