분류 전체보기 검색 결과

해당 글 203건

[재귀] 연산자 끼워넣기 (2) 15658

연산자 끼워넣기 (2) (boj.kr/15658) 문제 해설 및 주의사항 1.연산자 끼워넣기와 비슷하다. 2. 달라진 점은, 연산자의 개수가 딱 맞게 떨어지지는 않는다는 점이다. 해설 적용한 레시피 / 방법론 + 접근법 풀이 1. 위의 이전문제와 풀이는 아예 동일하다. 2. 재귀함수의 기저사례가 연산자의 개수와는 관계없기 때문이다. 풀이코드 #include #include using namespace std; // 15658 연산자 끼워넣기 (2) int n; int A[12]; pair solve(int index, int sum, int plus, int minus, int mul, int div){ // 기저사례 : index 가 끝에 도달하면 return if(index == n){ return ..
ps/브루트 포스 2021. 10. 16. 18:59

[재귀] 14888 연산자 끼워넣기

연산자 끼워넣기 (boj.kr/14888) 문제 해설 및 주의사항 1. 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다 2. 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 3. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다. 해설 적용한 레시피 / 방법론 + 접근법 1 풀이 1. 브루트 포스가 가능한가? - N 이 11개, 연산자가 10개 가 최대이다. 그러므로, 10! 개. 브루트 포스가 가능한 경우의..
ps/브루트 포스 2021. 10. 16. 12:49

하노이탑 이동 순서 (boj.kr/11729)

하노이탑 이동 순서 (boj.kr/11729) 문제 해설 및 주의사항 - 하노이 탑의 최소 이동 순서를 출력하는 프로그램을 작성하자. - 첫 번째 장대에 쌓인 원판의 개수 N 이 주어진다. 해설 적용한 레시피 / 방법론 + 접근법 풀이 1. 규칙을 찾아보자. - m 개의 원판을 3번째 장대로 옮긴다고 해보자. 그렇다면, 1. 먼저 위의 m - 1개의 원판을 2번째 장대로 옮기고 ( a_(m-1) ) 2. 남은 1개의 원판을 3번째 장대로 옮기고 ( + 1) 3. 2번째 장대의 m - 1 개 원판을 3번째 장대로 옮긴다. ( a_(m-1) ) 최단 이동 횟수의 점화식은 a_n = 2a_(n - 1) + 1 이 될 것이다. 2. 함수의 구현 - 재귀를 호출 할 때 달라지는 것은 무엇일까 a. 목적지 장대 (..
ps/분할 정복 2021. 10. 14. 23:07

종이의 개수 (boj.kr/1780)

종이의 개수 (boj.kr/1780) 문제 해설 및 주의사항 N x N 종이의 각칸에는 -1 0 1 이 저장되어 있다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고(divide), 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. -1로 만 채워진 종이. 0으로만. 1로만 채워진 종이의 개수를 구해내자. 해설 적용한 레시피 / 방법론 + 접근법 풀이 1. 브루트 포스? - N 의 최대 크기는 3^7 = 2,187개 이다. 정사각형 최대 크기는 4,782,969. 전체 정사각형에서, 종이에 써있는 수가 같은 수 임을 알기 위해 반복하는 최대 갯수는 N / 9 * 9 (1번째 분할) + N / 81 * 9 (2번째 분..
ps/분할 정복 2021. 10. 14. 22:09