정리하기 위한 블로그 정리하기 위한 블로그

하둡의 내부 설계까지는 아니더라도 사용자 입장에서 인지해야 할 핵심 개념에 대해 정리하고,실제로 어떤 효용을 주는지까지 정리해본다. 1. HDFSHadoop Distributed File System (분산 파일 시스템) 전통적인 파일 시스템과 유사한 계층을 가지지만, 실제 데이터가 저장되는 물리 머신(노드)은 여러 대로 분산되어 있음.여러 대로 분산하여 구성할 수 있기 때문에 대량의 데이터를 저장할 수 있음. 동적으로 새로운 노드를 추가할 수도 있음. (단일 서버 스토리지에는 한계가 있는데 빅데이터를 어떻게 저장하지? -> 분산 저장하자) 주요 컴포넌트는 네임노드, 데이터노드가 있음.네임노드는 메타데이터를 관리하는 중앙서버 역할데이터노드는 실제 데이터를 저장하는 노드. 파일을 일정 크기(기본 128MB..

정의1. 컷 : 그래프를 2개의 서로 다른 집합으로 나누는 것.가중치가 없는 그래프 - 자른 간선의 개수가 cut의 비용.가중치가 있는 그래프 - 가중치의 합이 cut의 비용. 2. 유량 각 간선은 용량을 가지고 있고, 해당 간선으로 얼마나 많은 유량이 흐를 수 있는지이다.용량 - 각 간선에 할당된 유량은 그 간선의 용량을 초과할 수 없다.유량 보존 - 출발점과 도착점을 제외한 모든 정점에서는 들어오는 유량과 나가는 유량이 같다. 3. 최대 유량 최소 컷 정리 (MFMC) 최대 유량 - 네트워크 출발점에서 도착점으로 보낼 수 있는 가장 큰 유량최소 컷 - 간선을 가장 적게 자를 때 혹은 간선의 가중치 합이 가장 적을 때 용량의 최소합 핵심 - 정점 A와 B를 분리시키는 최소 컷의 비용은 A에서 B로 흐를..

1. DFS 스패닝 트리 DFS 탐색하면서 탐색 순서에 따른 간선 분류와 만들어지는 트리 트리 간선 : 스패닝 트리에 포함되는 간선순방향 간선 : 선조에서 자손으로 연결되는 간선이지만 트리간선이 아닌 간선역방향 간선 : 자손에서 선조로 연결되는 간선 2. 절단점 찾기정의절단점 : 무향그래프에서 어떤 점의 인접한 간선을 모두 지웠을 때 컴포넌트가 두 개 이상으로 나눠지는 점  기차역, 라우터 등 절단점이 있으면 해당 점이 고장나면 전체 망이 고장난다. 절단점 찾는 방법 : DFS 스패닝 트리에서 어떤 정점 u의 서브트리 중에 u의 선조로 가는 역방향 간선이 하나라도 존재하지 않으면 절단점이 된다.-> 그럼 u의 1,2,3 서브트리 중 1이 선조로 가고 2가 1로 3이 2로 가면 u는 절단점인가? -> 아니..

트라이문자열 집합을 트리 형태로 저장하는 자료구조다.각 노드에 26개의 알파벳 노드를 배열로 저장한다. int toNumber(char ch) { return ch - ‘A’; }struct TrieNode { TrieNode* children[26]; bool terminal; TrieNode() : terminal(false) { memset(children, 0, sizeof(children)); } ~TrieNode() { // destructor 소멸자 for(int i=0; i insert(key + 1); // key+1은 내 다음 문자의 포인터 가르킴 } } TrieNode* find(const char* key) { // ke..

여러 최적화 방법이 있겠지만 내가 배운 최적화 3가지 작성 1. find에서 수장 지정하면서 재귀당연하게 사용하고 있는 방법 int find(int x) { return u[x] u[x] 에 내가 찾은 수장을 지정하면서 복귀한다.  2. 합치는 연산 uni 최적화트리의 높이를 저장하는 rank 배열을 하나 더 만들고 트리가 낮은 집합을 큰 집합 아래로 가게 한다만약 크기가 같다면 rank를 +1 한다 이러면 find 시에 최악에 O(n)을 피할 수 있음 if(rank[u] > rank[v]) swap(u, v);parent[u] = v;if (rank[u] == rank[v]) ++rank[v];  3. 집합의 크기를 음수로 저장하기 유니온파인드 -1로 두고 수장은 음수 이면서 집합의 크기를 담기 ..

세그먼트 트리세그먼트 트리 = 구간의 어떤 결과를 트리 노드에 저장해놓는 자료구조 형태 세그먼트 트리 = 구간 트리 =  꽉 찬 이진 트리-> 배열로 표현하는 것이 효율적이다.-> i번째 노드의 왼쪽, 오른쪽 자손은 각각 2*i, 2*i +1이 된다  다양한 형태의 문제를 세그 트리로 풀어나갈 수 있다.구간의 최소값, 구간의 최대값, 구간 합, 구간의 최소치 두개, 정렬된 배열에서 구간의 최대 출현 빈도 구간의 최대 출현 빈도는 노드를 다음과 같이 응용 가능하다.단순히 왼쪽, 오른쪽 자식의 결과 중 최대값을 취해서 만들 수 있으면 좋겠지만왼 : {1,1,1,2,2} , 오 : {2,2,3,3,3} 이면 합치는 데에 정보가 더 필요하다.각 구간의 양쪽 끝 구간의 숫자와 빈도를 같이 저장하여 합치는 데에 사..

1. 새로운 디렉토리에서 가상환경을 생성python3 -m venv myenv myenv는 내가 정하고 싶은 이름  2. 생성된 가상환경을 활성화합니다.source myenv/bin/activate 활성화 하게되면 터미널 커맨드라인 앞에 (myenv) 와 같이 가상환경 이름이 붙는다.

Back Propagation을 이해해보자.Back Propagation 오차역전법우리가 관심있는 것은 각 w (weight) 에 대한 L (Loss) 의 편도함수를 전부 구하는 것이다.이때 naive 하게 일일이 각 w 에 대한 L 편미분을 일일이 구하는 것은 가능하지만 계산 비용이 무척 많이 들게 된다. 그래서 쉽게 계산하기 위해 나온 방법이 Back Propagation키 포인트는 다음 두 가지가 있음.1. w에 대한 L의 편미분은 델타값 (편미분 값인데 계산이 용이하도록 치환한 값) 과 연관되어 있음2. 각 층의 델타값은 내 다음 층의 델타값으로 구할 수 있음. 즉 l+1 -> l  구하는 방법은 다음과 같다.1. Foward Propagation으로 각 층의 출력을 모두 계산한다.2. 가장 마지..