[Algorithm] 🦘외발 뛰기

0. 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗...

종만북algospot동적계획법algospot

<종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++

먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다. 2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로 길이가 2인 경우이다. a와 c는 본질적으로 동일 하기 때문에 tiling(n)=1xtiling(n-1) + 1xtilin...

Tiling종만북algorithmalgospotdynamicprogrammingTiling

[알고리즘]Algospot_FANMEETING

출처 : 가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포...

카라츠바algorithmalgospot분할정복algorithm

[알고리즘] - BOGGLE 게임

메모리와 시간초과를 고려하지 않고, 무작정 풀어보았다. find_word 함수를 통하여 보드판에서 word 의 첫번째 알파벳과 일치하는 지점에서 finding 함수를 통하여 재귀가 시작 된다. 역시나 결과는 시간초과이다. 시간초과를 해결하기 위해 동적 계획법을 활용하였다. memset 함수를 통해 3차원 배열의 cache 를 초기화 하고, 각각의 단어를 찾는 과정에서 중복되는 과정을 제거하였...

algospotalgorithmDPcppDP

[Algospot] PICNIC

문제 처음에 중복을 해결해주지 않아 무시무시한 수가 나왔다. 책에서는 isFriend[x][y] = 1; isFriend[y][x] = 1; 다음과 같이 했지만 이럴 경우 짝(1,2)와 짝(2,1) 을 다른 경우로 취급하기에 한번만 값을 넣었다. 또한 [(1,2), (3,4)], [(3,4), (1,2)] 처럼 중복이 되므로 결과를 (전체학생수/2)!로 나누어 주어야한다...

algospotalgospot