버러범의 개발이야기

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