반응형 분할정복8 백준 19587번 객실 배치 - C++(cpp) 풀이 1. N층짜리 건물에 객실을 배치하는 방법의 수를 점화식으로 나타낸다. 2. 점화식을 행렬의 곱으로 나타낸다. 3. 분할정복을 이용하여 행렬의 거듭제곱을 계산한다. 1. N층짜리 건물에 객실을 배치하는 방법의 수를 점화식으로 나타낸다. T(n) = N층짜리 건물에 객실을 배치하는 방법의 수 T(n) = A(n) + B(n) + C(n) A(n) = n층은 비워두는 경우의 수 B(n) = n층은 1호실을 채우는 경우의 수 C(n) = n층은 2호실을 채우는 경우의 수 n번째 층의 상태에 따라 n-1번째 층의 상태를 결정하는 경우가 달라진다. n번째 층이 비어있다면: n-1번째 층은 비울수도, 1호실만 채울수도, 2호실만 채울수도 있다. n번째 층의 1호실을 채웠다면: n-1번째 층은 비우거나 2호실만 채울.. 2022. 2. 23. 백준 10830번 행렬 제곱 - 스위프트(Swift) 풀이 1. 분할 정복으로 해결한다. 2. B % 2 = 0인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * multiplyMatrix(B/2) 3. B % 2 = 1인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * multiplyMatrix(B/2) * A 4. 메모이제이션을 통해 연산 횟수를 줄인다. 5. 초기 행렬에 1000이 있는 경우를 조심한다. 1. 분할 정복으로 해결한다. 진짜로 B제곱을 하면 B가 10^12로 엄청 크기 때문에 당연히 시간 초과가 난다. 대신 유명한 알고리즘인 분할 정복을 이용한 거듭제곱을 사용한다. 2. B % 2 = 0인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * mu.. 2022. 1. 22. 백준 2630번 색종이 만들기 - 스위프트(Swift) 풀이 + 그림 설명 그림부터 너무 분할 정복처럼 생긴 분할 정복 문제. 1. 색종이를 4개로 쪼갠다. 2. 재귀적으로 4개의 조각에 대해 각각 하얀색과 파란색의 개수를 센다. 3. 4개 조각에서 구한 하얀색과 파란색의 개수를 더해 전체 개수를 구한다. 4. 만약 4개 조각이 모두 같은 색인 경우, 같은 색이 4개 있는 것이 아니라 큰 하나의 색종이인 것을 조심한다. 1. 색종이를 4개로 쪼갠다. 모두 같은 색이면 더 이상 자르지 말라고 했다. 하지만 생각을 달리해서 일단 자른 다음에, 모두 같은색이면 다시 붙일 것이다..! 2. 재귀적으로 4개의 조각에 대해 각각 하얀색과 파란색의 개수를 센다. 다음과 같은 함수를 정의했다. 전체 종이에서 (row, col)이 왼쪽 꼭짓점이고, 크기가 size인 조각 내의 (하얀색 수, 파.. 2022. 1. 16. 이전 1 2 다음 반응형
