728x90 반응형 Python15 [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. [Python] 도넛과 막대 그래프 [프로그래머스] 도넛과 막대 그래프문제 출처: 프로그래머스난이도: level 2참고: 2024 KAKAO WINTER INTERNSHIPinput size: $1 \le V, \ E \le 10^6$(주관) 자료구조: 그래프, 리스트(주관) 알고리즘: 그래프, 차수(degree) 개념(주관) 예상 시간복잡도: $O(V+E) = O(10^6)$오랜만에 코테 준비로 프로그래머스 접속했는데, 문제가 굉장히 많아졌다.2년전에 코테 준비할 때 거의 다 푼 것같은데 그새 못푼 문제가 많이 쌓였다. 처음 이 문제를 봤을때 수없이 많은 루프에 정신이 나갔다.처음에 BFS/DFS로 모든 노드를 순회하면서 그래프의 특징을 찾으려 하다가(예: 탐색을 마친 그래프의 노드 개수가 n개고 edge 개수가 n-1이면 막대그래프로 .. 2024. 6. 17. Python의 round는 사사오입? 오사오입? 초등학교와 중학교에서 배운 반올림은 5이상에서 올리고, 5미만에서 버린다. 사사오입이라고도 부른다.파이썬에서 반올림은 `round` 함수가 있는데, 사사오입이 아니라 오사오입이다. (banker's rounding이라고도 한다)※ 올림과 버림은 음수로 오면 헷갈리기 쉽다. 수학적으로 각각 ceil과 floor이다.※ 반올림의 수학적 표현은 floor(x+0.5) 이다. 이게 무엇인가 하면, 5미만은 버림, 5초과에서 올린다. 5의 경우 앞자리가 짝수면 버리고, 홀수면 올린다.예를 들면, 2.5의 경우 5의 앞자리가 2인 짝수로 버린다. 즉 round(2.5)=2 이다.3.5의 경우, 5의 앞자리가 3인 홀수로 올린다. 즉 round(3.5)=3 이다. 음수의 경우, 절댓값에 반올림을 적용하고, 다시 음수.. 2023. 10. 1. [Clustering] K-means Clustering in Python (K-means 알고리즘) Setup# Start from importing necessary packages.import warningsimport numpy as npimport matplotlib.pyplot as pltimport matplotlib.cm as cmfrom IPython.display import displayfrom sklearn import metrics # for evaluationsfrom sklearn.datasets import make_blobs, make_circles # for generating experimental datafrom sklearn.preprocessing import StandardScaler # for feature scalingfrom sklearn.cluster im.. 2023. 5. 20. [Ensemble] Random Forests in Python (scikit-learn) Setupbagging과 random forest를 실습하기 위해 필요한 라이브러리를 import하자.# To support both python 2 and python 3from __future__ import division, print_function, unicode_literals# Common importsimport numpy as npimport os# to make this notebook's output stable across runsnp.random.seed(42)# To plot pretty figures%matplotlib inlineimport matplotlib as mplimport matplotlib.pyplot as pltfrom matplotlib.colors impor.. 2023. 5. 13. 이전 1 2 3 다음 728x90 반응형
