[TIL #42] 42일차 오늘의 공부 (2023.04.19 수)

 

 

TIL 2023.04.19 🐣

오늘 공부한 내용 👩🏻‍💻

알고리즘

- 백준 10610 : 입력받은 문자를 조합해서 30의 배수가 되는 가장 큰 수를 구하는 문제이다.

그리디 문제인데 배수판정법을 알아야 풀 수 있는 문제이다.

 

30의 배수가 되는 수는 일단 3의 배수이면서 10의 배수여야한다.

때문에 10의 배수이기 때문에 1의 자리수가 0이어야하고, 3의 배수여야하기 때문에 모든 자리수의 합이 3의 배수여야한다.

👉 모든 자리수의 합이 3의 배수여야하는 이유는 3의 배수판정법을 따르기 때문이다.

 

배수 판정법

모든 수는 자기 자신의 배수이다.

0은 모든 수의 배수이다.

2의 배수 판정법 : 일의 자리의 수가 0, 2, 4, 6, 8 (짝수)이다.

3의 배수 판정법 : 모든 자리의 수의 합이 3의 배수이다.

4의 배수 판정법 : 마지막 두자리의 수가 00이거나 4의 배수이다.

5의 배수 판정법 : 일의 자리의 수가 0, 5이다.

6의 배수 판정법 : 2의 배수이면서 동시에 3의 배수이다. (모든 자리수의 합이 3의 배수가 되는 짝수이다.)

7의 배수 판정법 : 일의 자리를 2배 한 것을 나머지 수에서 빼면 결과가 0 또는 7의 배수가 나오는 수

8의 배수 판정법 : 마지막 세자리의 수가 00이거나 8의 배수이다.

9의 배수 판정법 : 모든 자리 수의 합이 9의 배수이다.

10의 배수 판정법 : 일의 자리의 수가 0이다.

참고 : https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95

 

- 그리고 그리디에 익숙해지기 위해서 그리디 문제 총 6개를 풀었다.

어려웠던 내용 😵

배수판정법을 처음 접해봐서 이해가 안갔는데 알고리즘 풀려면 수학 지식이 필요하다는 걸 또 배우고 갑니다..

궁금한 내용/부족한 내용 🧐

느낀 점 🥳