728x90 반응형 전체 글261 [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. [논문리뷰] Deep Graph Infomax (DGI) Deep Graph Infomax (DGI) [ICLR 2019]AbstractDGI는 node representation을 unsupervised manner로 얻는 일반적인 방법론이다.DGI는 patch representation과 graph summary의 mutual information을 최대화하는 방법으로 학습한다.patch representation은 관심이 되는 node의 subgraph의 summary를 얻기 때문에 node-wise task로 downstream하여 적용할 수 있다.과거의 GCN기반 unsupervised 방법과 달리, DGI는 random walk에만 의존하지 않기 때문에 transductive와 inductive learning setup 모두 적용할 수 있다.1. .. 2024. 6. 18. [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. 단순선형회귀 (Simple Linear Regression Model) Simple Linear Regression (단순 선형회귀)Model Definition and Assumptions$n$개의 관측된 데이터 $(x_1, y_1), \dots, (x_n, y_n)$에 대하여 $x$와 $y$가 어떻게 연관되어있는지 알고싶다.특별히, 선형적 관계에 있는 모형을 설계할 수 있다.\[ y_i = \beta_0 + \beta_1 x_i + \epsilon_i \quad \epsilon_i \sim N(0, \sigma^2) \]$y$를 $x$에 따른 확률변수로 생각하여 다음과 같이 모형을 설계한다.\[ Y_i \sim N(\beta_0 + \beta_1 x_i, \sigma^2) \]※ $x$는 predictor/explanatory/independent variable로 불린.. 2024. 6. 2. 일원분류 분산분석 (One-Factor ANOVA) One-Factor Analysis of Variance (ANOVA)Analysis of Variance (ANOVA)모집단이 2개의 경우 모평균(또는 모비율)을 비교하는 방법을 다루었다.이제 모집단이 3개 이상인 경우에 대해 생각해보자.기본적인 아이디어는 통계적 분석(statistical analysis)이 같은지 확인하는 것이다. 여러개의 모집단에서 추출된 독립 표본의 집합을 completely randomized design(완전임의배치법)이라 한다.그리고 분산분석(analysis of variance, ANOVA)라는 통계적 방법론을 이용한다. 모집단이 2개인 경우, pair인지 independent인지 구분하여 검정하였다.모집단이 3개 이상인 경우에도 비슷한 방식으로 구분한다.첫번째는 bloc.. 2024. 6. 1. 이전 1 2 3 4 5 6 7 ··· 44 다음 728x90 반응형
