Adore__

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' 그래프의 기본 그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 말한다. 즉, 두 노드가 연결되어 있으면 그래프라고 말할 수 있다. 먼저 그래프의 종류를 한번 쭉 훑고 가보자 그래프 종류 개념 그림 유니온 파인드 그래프 문제에서는,사이클이 생성되는지 판별하는 알고리즘이다. 위상 정렬 이 알고리즘을 사용하기 위해서는 선 조건이 있다. 1) 전후관계가 있어야 한다. 2) 즉, 방향이 있는 그래프여야 한다. 3) 이를 위해서는 사이클이 없어야 한다 이 조건에서 그래프의 각 노드를 선형으로 정렬해주는 알고리즘이다. 단, 위상 정렬로 나오는 값이 유일하지 않다는 특징이 있다. ex) 수강신청 - 수1을 ..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' 4장은 정수론이다 이 부분은 손으로 직접 써보고 풀어보는 것이 더 효과적인 것 같아서 필기로 대체한다. 글씨체를 좀 예쁘게 쓰고 싶은데 어렵다하핫 1) 소수 구하기 우리가 잘 아는 '소수'를 구하는 알고리즘이다. '소수'란, 약수를 1과 자기자신 만 갖는 수를 말한다. 이를 판별하는 방법으로 가장 대표적인 것이 '에라토스테네스의 체' 이다. 구하고자 하는 범위만큼 배열을 생성한 후, 각 숫자의 배수를 지워가다보면 남은 수는 소수들 뿐이다. 이 지우는 과정때문에 시간 복잡도는 O(Nlog(logN))을 갖는다. 2) 오일러 피 오일러피 함수는 1~N까지 수에서 N과 서로소인 자연수의 개수를 말한다. P[6] = 2의 뜻..

Source - StatQuest with Josh Starmer - https://angeloyeo.github.io/2020/07/17/MLE.html 결합 확률밀도 함수란? 우선 결합확률이란 두 개의 사건이 동시에 일어날 확률을 의미한다. 서로 배반되는 두 사건 A, B가 있을 때, 두 사건이 동시에 일어나는 확률을 P(A∩B) 라고 하며 이 확률을 A, B의 결합확률이라고 정의한다. ▪️Likelihood Estimation 먼저 Likelihood와 probability를 비교해보자 확률 probability 이란, 고정된 한가지의 확률분포 안에서 내가 원하는 관측값(또는 관측 구간)이 갖는 확률을 말한다. ✔︎ Probability = P(관측값 | 확률분포) 반면 'likelihood'라는 ..

베이지안 통계학이란? : 주어진 자료(data)를 통하여 관심의 대상이 되는 모수(parameter)의 불확실성(uncertainty)을 확률로 나타내자! 즉, 과거를 기반으로 앞으로 일어날 일에 대한 가능성을 추론하는 것이다. 이름에서 보다시피 베이즈 정리와 조건부 확률을 이용한다. ▪️조건부 확률 어떤 사건이 먼저 일어났을 때, 이와 별개인 다른 사건이 함께 일어날 확률이다 ▪️베이즈 정리 이제부터 베이지안 관점에서 생각하기 위해 '확률'에 대한 개념을 다음과 같이 세팅하고 가자 확률 : 주장에 대한 신뢰도 H: Hypothesis, 어떤 사건이 발생했다는 주장 / 가설 E: Evidence, 새로운 정보 / 근거 P(H) : 사전 확률 priority / 어떤 사건이 발생했다는 주장에 대한 신뢰도 ..

https://devowen.com/260 백준 2109 / 그리디(Greedy) 알고리즘 / JAVA 오늘 설명할 문제는 백준 2109번 순회 강연이다. https://www.acmicpc.net/problem/2109 2109번: 순회강연 문제 한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,0 devowen.com 이 포스팅을 참고하여 공부하였다. 탐욕 알고리즘이란, 현재 상태에서 가장 최선의 선택지를 선택하다보면, 전체 선택지 중에 가장 최적의 선택지를 얻어낼 것이라고 가정하고 풀어가는 방법이다. 즉, 지금 상태에서 할 수 있는 최선의 길로 가다보면 내 인생에서 최고의 길로 가게 될 거라는...그런 가정..🥲 (난 이렇게 믿고 살고있는..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' Depth-First Search (DFS) 깊이 우선 탐색은 그래프의 완전 탐색 기법 중 하나이다. * 완전 탐색 기법 : 가능한 경우의 수를 모두 나열하면서 원하는 답을 찾는 방법 (그래프의 모든 노드 다 살펴볼거야~) ▪️방법 1) 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기(줄기)를 정한다. 2) 그 분기의 최대 깊이 (가장 밑에 있는 노드)까지 탐색을 마친다 3) 다른 쪽 줄기로 이동하여 반복한다. ▪️특징, 시간 복잡도 기능 특징 시간복잡도 (node 수: V / edge 수 : E) 그래프 완전 탐색 - LIFO 탐색 - 재귀 함수로 구현 - 스택 자료구조 이용 O(V+E) 우선 깊이우선 탐색은 그래..