예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하) 문제 5*5 크기의 알파벳 격자를 가지고 하는 게임. 게임의 목적은 상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것입니다. 각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수도 있습니다. 주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 문제를 풀어 봅시다. 입력 1 1 PRETTY 출력 True 풀이 간단한 방법 생각 완전 탐색 문제 분할 첫 글자 찾기 => 다음 글자를 주변에서 찾기 기저 사례 선택 더 이상의 탐색 없이 간단히 답을 낼 수 있는 경우 처음 주어진 위치가 원하는 단어의 첫 글자가 아닌 경우 실패 1에 해당하지 않고 원하는 단어가 1글자인 경우 성공 둘의 순서는 바뀌..

문제 : 알고리즘 문제 해결 전략 [록페스티벌] p6 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다. 이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?..

https://www.acmicpc.net/problem/2839 나의 답 # 백준 2839번 : 설탕 배달 # 2020-02-01 num = int(input()) count = 0 while num>=3 : if not(num%5) : # 5의 배수이면 count+= num/5 break else : count+=1 num-=3 if num==1 or num==2: count = -1 else : count += 0 print(int(count)) 분석 다이나믹 알고리즘 앞선 2문제의 영향으로 처음에는 모든 경우의 수를 찾아볼까 생각했다. 하지만 이전 문제와 달리 수의 범위가 확연히 커진데다가 연산의 시간이 너무 오래걸릴 것 같아서 이러한 방식은 아닐 거라고 결론 내렸다. 경우의 수 (특징 찾기) 그..

문제 : 백준 9095번 _ 1,2,3 더하기 https://www.acmicpc.net/problem/9095 나의 답 # 백준 9095번: 1,2,3 더하기 # 2020-02-01 case = int(input()) # 입력받기 num = [] def cpt_num(n): if n>3: # 3보다 크면 return cpt_num(n-3) + cpt_num(n-2) + cpt_num(n-1) elif n==3: # 3이면 return 4 elif n==2: # 2이면 return 2 elif n==1: # 1이면 return 1 while case : case-=1 num.append(int(input())) for n in num: print(cpt_num(n)) 어제 배웠던 다이나믹 프로그래밍을 활..

https://www.acmicpc.net/problem/1463 나의 답 연산의 우선순위를 매겼음 1빼기 1빼고 2나누기 이러한 가정을 예제 계산만으로 확정한대서 문제가 있었지 않나 싶다. 연산에 우선순위를 두는 것은 의미가 없음 다른 답 (2020-04-19 수정) 동적 계획법(Dynamic programming)을 이용하는 방법 동적 계획법은 어떤 문제의 답을 메모리에 저장해두었다가 다시 값을 구해야할 때 중복계산이 필요없게 가져다 쓰는 기법이다. x = int(input()) count = 0 minimum = [x] def cal(x): # 주어진 행렬의 모든 수 각각에 대해서 -1, 3으로 나누기, 2로 나누기의 3가지 연산을 모..