[TIL] 05.26 개발일지

📙  공부한 것

- 알고리즘

- 1541 잃어버린 괄호 (X 풀지못함)

- 1934 최소공배수  (X)

 

🔍 시도해본 것

 

잃어버린 괄호

30-70-(20+40)-(10+100+30)-35 같은 식이 있을때, 덧셈은 더해줘야한다는 생각은 떠올랐다.

하지만 입력을 어떻게 받아서 처리해줘야할지 몰랐다. 아무래도 문자열 처리 부분이 많이 약한 것 같다.

 

 

최소공배수 

최대 공약수 : 두 자연수의 공통 약수 중 가장 큰 수를 의미ex ) 72와 30의 최대공약수는 6이다.

 

최소 공배수 : 최소 공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미

= 두 자연수의 곱 / 최대 공약수

 

 

 

 

💡 알고 된 점

 

잃어버린 괄호

처음 StringTokenizer 클래스를 이용해서, 입력을 받고 구분자를 "-" 부호로 해줘야했다.

그 다음으로, +부분만을 따로 덧셈을 해줘야한다음, (이 부분도 구분자 사용)

덧셈한 결과들을 전부 빼주면 끝 이었다. 

주의할점은 첫번째 숫자는 양수이므로, 이부분은 따로 처리해주어야한다.

혹은

 

문자형 배열형태로, "-"기호를 구분자로해서, 담을 수도 있다.

 

 

최소 공배수

유클리드 호제법 알고리즘 시간복잡도 O(logN)

두 자연수 a,b에 대해, a를 b로(a>b) 나눈 나머지를 r이라하면, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.

이 성질을 따라서, b를 r로 나눈 나머지 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약 수이다.  (재귀형태로 구현.)

 

최소 공배수는 두 수의 곱 / 최대 공약수로 구할 수 있다.

 

최대공약수는, 유클리드 호재법을 재귀함수 형태로 만들어 최대공약수와 공배수를 구할 수 있다.