one Book a Day

1번은 재귀 분할정복이고 2번은 반복문 분할 정복이다. 1번 def power(n, p): if p == 0: return 1 # Call this only once, instead of two times. power_p_divided_by_2 = power(n, p // 2) if p % 2: return n * power_p_divided_by_2 * power_p_divided_by_2 else: return power_p_divided_by_2 * power_p_divided_by_2 2번 def power(a, n): ret = 1 while n > 0: if n % 2 != 0: ret *= a a *= a n //= 2 return ret

실질적으로 별찍기(프렉탈 분할정복) 을 접한건 두번째다 첫번째는 감이 잘 안왔는데 이제는 슬슬 감이온다. 1. 입력값 2. 최소단위로 분할 3. 최소문제 해결 4. 더 큰문제 정복 5. 조합 정복시 그림이 잘 안그려질때는 실질적으로 뭐가 몇개 늘어났는지. 최소단위가 몇개 늘어나는지 잘 살펴보면 된다. 그리고 최소단위를 반복, 순회하면서 반복 덧셈, 곱셈을통해 확장시켜나가면 된다. 이 문제같은 경우 가장 작은 삼각형이 다음 차수에 밑에 2개 더 붙고 그다음은 그 큰 3개의 삼각형이 밑에 2개씩 더붙는다. 즉 이전 그림의 두배씩 아래쪽 배열에 추가된다고 생각하면 된다. 또 처음 들어갔던 배열도 " " 빈칸을 추가해줘야하는데 얼마나 추가해주냐면 실질적으로 늘어나는 3칸을 세어 3칸 -> 6칸 -> 12칸 즉 ..

별찍기 같은 경우 분할 정복의 대표적 문제다. 분할 : n=3인 경우로 분할 정복 : n=3인 경우를 해결. (매개변수로 받아오는 값만 어떻게 처리해야 동일한 패턴이 나올까 고민하면됨) 병합 : n=3인 경우의 결과값을 다음 순서에 넣어 확장시키면 재귀적인 프렉탈구조를 만들수 있다. # 분할 정복 알고리즘 / 분할, 정복, 합치기. # 정복 # star 배열을 통해 새 matrix를 생성해 반환하는게 목적. # 반복문에서 3*len(star)로 별이 그려지는 모든 배열을 검사하며 len(star) # 즉 최초 n의 크기에 따라 빈칸 " "을 추가적으로 삽입하는 방식을 차용한다. # (n=9일때 3으로 나눠 몫이 1인 index = 1 요소의 가운데 ) def conquer(n): matrix=[] for..