버러범의 개발이야기

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

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

MP3에 들어있는 노래수와 노래들의 재생시간, 선호하는 노래, 특정 노래후에 다음노래가 나올확률(2차원 배열)등이 주어졌을때 K분30초 후에 선호하는 노래가 나오고 있을 확률을 구하는 문제이다.

일단 K의 범위가 [1, 1000000]이기 때문에 cache공간 문제 때문에 재귀적이 DP로는 해결할수 없을것 같았고, 평범한 반복적DP도 시간복잡도 문제때문에 사용하기 힘들어 보였다.

해답으로는 행렬 거듭제곱을 이용한 동적 계획법이 있었다.

start(time, song) = 재생을 시작한지 time분 후에 song번 노래가 재생을 시작할 확률이라하자

start(time-3)부터 start(time)까지를 포함하는 크기 4*N의 열벡터 C(time)를 정의하고 C(time+1)=W*C(time)인 W를 구하여 k만큼 거듭제곱한 후 C(0)와 곱해주면 원하는 답을 얻을수 있다.

하지만 이러한 행렬들을 관리하기 위해서는 여러가지 메서드들을 직접 정의하고 연산자들도 오버로딩 해줘야 했기 때문에 무척 까다로운 문제였다. 또한 k의 범위가 무척 크기 때문에 거듭제곱의 횟수또한 줄이기 위해 분할정복을 사용하였다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/9.%20DP-Technic/GENIUS.cpp

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

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

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

입력으로 예산과 초밥의 종류 수, 각 초밥에 가격과 선호도가 주어졌을때, 예산에 맞게 초밥을 갯수 상관없이 구매하여 구할 수 있는 최대 선호도를 출력하는 문제이다.

초밥을 종류별로 탐색하면서 (예산 - 탐색중인 초밥의 가격)을 예산으로 하는 DP를 이용하여 문제를 풀수있다.

이때 주의할 점은 예산의 범위가([1,10^9]) 너무 커서 메모이제이션을 위한 배열을 예산크기만큼 선언하기 힘들다는것이다.

DP에서 (예산 - 탐색중인 초밥의 가격)을 이용한다 했을때 (탐색중인 초밥의 가격+1)만큼의 배열만 있으면 슬라이딩윈도를 사용하여 문제를 풀기 충분할거 같다.

따라서 기존에 사용하던 재귀적인 DP가아니라 슬라이딩윈도를 사용할수있는 반복적DP를 사용하였다.

(초밥의 최대 가격이 20000원이여서 여전히 배열선언하기 부담스럽지만 문제에서 주어진 조건인 가격은 100의 배수라는 점을 이용해서 배열의 크기를 200+1까지 줄여나갈 수 있다.)

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/9.%20DP-Technic/SUSHI.cpp

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

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

algospot 문제링크: https://www.algospot.com/judge/problem/read/BLOCKGAME

일정부분 채워져있는 게임판이 입력으로 주어졌을때 L자모양의 3칸짜리 블록으로 주어진 게임판을 채울수 있는 경우의 수를 구하는 문제입니다.

주어진 게임판에 알맞은 모양으로 블록을 놓고 그 모양의 게임판을 재귀호출하는 방법으로 완전탐색을 이용해 문제를 풀수있습니다.

이때 주의할점은 블록을 놓는 순서에 따라 똑같은 경우를 중복해서 셀수있다는 것입니다.

이를 방지하기 위해서 좌측에서 우측으로 상단에서 하단으로 순서대로 탐색합니다.

탐색중 빈칸을 만나면 블록의 각 모양을 대입하고 놓을수 있으면 놓고 재귀호출합니다.

이문제의 까다로운 점은 L자 모양의 블록을 90도 돌려가면서 나올수 있는 여러가지 모양의 블록을 두개의 2차원배열로 표현하여 하나씩 대입해봐야 된다는 겁니다.

하지만 경우의 수가 4가지 밖에 안되기때문에 충분히 수동으로 입력가능합니다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/6.%20brute-force/BOARDCOVER.cpp

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

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

algospot 문제 링크 : https://www.algospot.com/judge/problem/read/PICNIC

입력으로 학생수와 친구쌍이 주어졌을때 친구쌍으로만 짝꿍을 만들수 있는 경우의 수를 구하는문제입니다.

재귀호출을 이용해 완전탐색으로 문제를 풀 수 있습니다.

이때 주의할점은 실질적으로 같은 답을 중복으로 세는 경우가 있을수 있다는 것입니다.

예를들어 0,1과 2,3 이 각각 친구일때 (2,3), (0,1) or (1,0), (2,3) or (0,1), (2,3)등을 중복해서 셀수 있습니다.

이를 방지하기 위해서는 각 단계에서 남아 잇는 학생들 중 가장 번호가 빠른 학생의 짝을 먼저 찾아 주면 됩니다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/6.%20brute-force/PICNIC.cpp

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

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