(8/3) 9일차 - 분할정복과 귀납적 알고리즘설계 문제

모의고사를 제외한다면 수업으로는 마지막 날이었습니다. 총 10문제였습니다.

https://bas.ioikorea.cc/problems/list

2022 여름학교 처음반

 

1. 쿼드 트리     O

예전 백준에서 같은 문제를 풀어본 적이 있습니다. 재귀적으로 왼쪽 위, 오른쪽 아래 좌표를 가지고 4조각으로 나누면서 주어진 좌표 안의 모든 점이 0 또는 1로 통일된다면 출력하고 return 해줍니다. 

 

2. 곱셈     O

곱하는 값들의 범위가 10^18이기 때문에 단순 곱셈은 오버플로우가 발생합니다. 이를 해결해주기 위해 곱셈을 재귀적으로 더 작은 수의 곱셈으로 나누어 주어야 합니다.

if b%2 == 0  --> a*b = a*k+a*k (b = 2k)

if b%2 == 1  --> a*b = a*k+a*k+a  (b = 2k+1)

의 형태로 재귀적으로 나누어주면 됩니다. 뒤에 모듈러 연산도 붙기 때문에 오버플로우가 발생하지 않습니다.

 

3. 곱셈곱셈    O

2번하고 비슷합니다. 

if b%2 == 0 --> a^b = a^k * a^k (b = 2k)

if b%2 == 0 --> a^b = a^k * a^k * a (b = 2k+1)

 

4. 비밀번호 찾기   X

카라츠바 & 교수님이 설명해주셨던 다항식 계산 알고리즘 이용

아직 해결하지 못함. 작성중

 

5. 프로선수    X

아직 해결하지 못함. 작성중

 

6. 가장 가까운 두 점    O

교수님께서 강의시간에 설명하셨던 가장 가까운 두 점을 찾는 최적 알고리즘을 사용하면 됩니다. 처음 입력을 받았을 때 n개의 정점을 x 좌표에 의해 정렬합니다. 재귀적으로 n/2 점으로 구성된 두 집합으로 나누고 두 집합에서 각각 가장 가까운 두 점을 찾고 y좌표를 기준으로 정렬합니다. 정렬된 두 집합을 머지소트의 합병과정처럼 합병하고 처리를 해주면 됩니다.

 

7. Hotter Colder    X

Centroid Decomposition의 개념 이용

아직 해결하지 못함. 작성중

 

8. 유능한 코치    X

머지소트 트리 이용

아직 해결하지 못함. 작성중

 

9. 애플파이    X

DnC Optimization

아직 해결하지 못함. 작성중

 

10. 점수     X

DnC Optimization

아직 해결하지 못함. 작성중