728x90 반응형 스터디/알고리즘14 [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. 시계열 데이터의 상관성 구하기 (time-series correlation) 서로 다른 시계열 데이터의 상관성을 어떻게 알 수 있을까?그리고 두 데이터의 길이가 다르다면?? 공통적인 주의사항으로, 상관관계를 인과관계로 해석해서는 안된다는 것임을 통계학 수업에서 많이 들어봤을 것이다.1. Pearson Correlation Coefficient (PCC, Pearson's r)통계 시간에 배우는 그 피어슨-상관계수 맞다. \[ \rho_{X, \ Y} = \cfrac{\text{cov}(X, \ Y)}{\sigma_X \sigma_Y} = \cfrac{\mathbb{E}[XY] - \mathbb{E}[X] \mathbb{E}[Y]}{\sqrt{\mathbb{E}[X^2] - (\mathbb{E}[X])^2} \sqrt{\mathbb{E}[Y^2] - (\mathbb{E}[Y])^.. 2023. 2. 12. [BOJ 6549] 히스토그램에서 가장 큰 직사각형 알고리즘 분류: 자료구조, 분할정복, 세그먼트트리, 스택 비슷한 문제: BOJ 1725, 히스토그램 이중 스택을 이용한 풀이가 잘 알려져 있고, 이 때의 시간복잡도는 $O(2N) = O(N)$이다. 핵심 아이디어 (1) 히스토그램의 높이가 증가할 때 까지 스택에 인덱스를 push 한다 (2) 히스토그램의 높이가 감소한다면 (2.1) 현대 인덱스는 i, 직전의 히스토그램의 인덱스는 stack.top 일 것 이다 (2.2) 스택이 비워질 때 까지 인덱스를 pop하면서 현재 넓이를 구한다 (2.3) 이때 width = (i - top - 1), height = H[stack.top] 이 된다 (3) 스택이 비어있지 않다면, 히스토그램의 마지막 부분이 증가하다가 끝난 경우이다 (3.1) (2)의 과정을 한 번 .. 2022. 11. 23. BOJ 10835 카드게임 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 그리디 알고리즘인가? - 항상 오른쪽 카드만 버릴수 있으면 정답인가? NO 플레이 가능한 동작은 3가지이다 (1) 왼쪽 카드만 버리기 (2) 왼쪽 카드와 오른쪽 카드 모두 버리기 (3) 오른쪽 카드만 버리기 (단, 오른쪽 카드의 숫자가 작아야 하고, 이때 득점이 가능하다) 만약 카드가 1장씩 남아있다면? 위의 (1) ~ (3) 연산을 if를 통해 점수를 얻을 수 있다. .. 2022. 11. 9. [C++] vector를 이용하여 그래프를 인접리스트로 구현하기 vector adj[10]; vector *adj = new vector[MAX_V]; // 개인적으로 좋아하는 표현 vector adjList(N, vector()); https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 이 문제로 그래프를 표현하면 int N, M; cin >> N >> M; vector* adj = new vector[N + 1]; for (int i = 0; i <.. 2022. 10. 1. 이전 1 2 3 다음 728x90 반응형
