크래프톤정글 2주차; TIL 2 - 백준 곱셈 문제, 괄호의 값 문제

2022-11-05

곱셈 백준 1629번 파이썬

출처: https://velog.io/@grace0st/곱셈-백준-1629번-파이썬

왜?

(AxB)%C = (A%C) * (B%C) % C을 이용했으나
(AxA^B-1)%C = (A%C) * (A^B-1%C) % C 처럼 공식을 세웠고,
A^B-1 = A * A^B-2 라고 생각해서
B자리에 B-1을 넣는 재귀 함수를 만들었다.
메모리 초과로 실패.

어떻게?

분할정복으로 해결하는데,

나머지 분배 법칙
(AxB)%C = (A%C) *(B%C) % C
지수법칙
A^m+n = A^m x A^n

을 이용한다!
지수법칙을 따를 때, 참고 블로그처럼 A^11 = A^5 * A^5 * A 이렇게 사용해야하지,
내가 한 것처럼 A^11 = A * A^11-1 이렇게 해버리면 비효율적임…

2022-11-06

괄호의 값 백준 2504번 파이썬

출처: https://hongcoding.tistory.com/114

왜?

옳지 않은 괄호일 때 0을 도출하는 것까지는 이전 ‘괄호’ 문제에서 해봐서 할 수 있었으나,
내가 어려웠던 것은 어떻게 이것이 더하기고 곱하기인지를 구분해줘야 하는지였다.
정답 코드처럼 answer와 temp 변수를 선언하고 이걸로 뭔갈(?) 해야 할 것 같았지만 이후 논리를 생각해내는데 실패함.

어떻게?

정답 코드는 맞지 않는 괄호일 때 0을 도출하는 것과 합 계산을 동시에 한다.
나는 맞는 괄호인지를 먼저 검사하고 0이 아닐 때만 합 계산을 하도록 했는데, 비효율적이다.
쨌든 일단 여는 괄호가 들어올 때 곱셈으로 먼저 계산해놓고,
닫는 괄호가 들어올 때 이전 괄호가 상응하는 여는 괄호인지 아닌지 확인하는 절차를 거친다는 것이 핵심임.