728x90 반응형 수학3 [Python] 최고의 집합 최고의 집합문제 출처: 프로그래머스난이도: level 3참고: 없음input size: $1 \le n \le 10^4$, $1 \le s \le 10^8$(주관) 자료구조: 없음(주관) 알고리즘: 수학(주관) 예상 시간복잡도: $O(n)$합이 $s$인 $n$개의 자연수 집합을 구하고, 그 중 원소의 합이 최대인 집합을 오름차순으로 정렬한다. STEP 1. 관찰과 직관프로그래머스에 주어진 예시가 $n=2$라서 와닿지는 않는다.왜냐면 $n=2$인 경우에 너무 쉽게 찾을 수 있다.$a_1 = x, x_2 = s-x$라 하면 곱 $f(x) = x(s-x)$이고 이차함수의 최댓값은 $x=s/2$인 지점이다.물론 정수이므로 $a_1 = \lfloor s/2 \rfloor$, $a_2 = s-a_1$으로 간단히 찾.. 2024. 7. 2. [Python] 두 원 사이의 정수 쌍 (math 없이 풀어보자!) 두 원 사이의 정수 쌍을 math 없이 풀어보자문제 출처: 프로그래머스난이도: level 2참고: 없음input size: $1 \le r_1 (주관) 자료구조: 없음(주관) 알고리즘: 수학, 반복문(주관) 예상 시간복잡도: $O(r_1 + r_2)$ 또는 $O(r \sqrt{r})$"질문하기"에도 다 math 모듈을 이용한 풀이가 힌트로 나와있었다.원래 코딩테스트는 외부 라이브러리를 사용하지 못하기 때문에, 다른 방법을 찾아보았다."진짜 다른 의도는 없는데 이런게 어렵나여..?" 글을 참고하여 math 없이 풀수 있는 힌트를 얻었다.자료형이 중요한 C/C++/java 에서도 overflow만 주의하면 충분히 정수형으로도 풀 수 있을 것 같다.long long이 $2^{63}-1 \approx 2^3 \.. 2024. 6. 19. [선형대수학] LU-Decompositions linear system(연립방정식)을 풀 때, 가우스 소거법과 가우스-조르당 소거법 2가지 방법을 통해 문제를 풀 수 있었다. [Review]가우스 소거법: 기본행연산을 통해 행사다리꼴(row echelon form)로 만드는 알고리즘가우스-조르당 소거법: 기본행연산을 통해 기약행사다리꼴(reduced row echelon form)로 만드는 알고리즘행사다리꼴: leading 1 아래의 모든 수가 0인 행렬기약행사다리꼴: leading 1 위 아래 모든 수가 0인 행렬위의 소거법의 경우 small-scale에서는 괜찮을지 모르나, 실제 large-scale에서 컴퓨터의 연산을 사용해도 roundoff error, memory usage, speed 면에서 효과적이지 못하다.$n$개의 미지수를 포함하는.. 2023. 2. 7. 이전 1 다음 728x90 반응형
