슬기로운 혀니의 코딩 생활 슬기로운 혀니의 코딩 생활

■ Apriori Algorithm - Market Basket Problem의 두 가지 방식 중 frequent Itemsets를 찾는데에 가장 보편적인 알고리즘이다. 알고리즘 없이 frequent Itemsets를 찾으려 하면 브루트 포스법을 사용하여 전체를 모두 뒤져야한다. 작은 Data에서는 가능할 수 있겠지만 데이터마이닝을 사용할 정도의 Big-Data에서는 어마어마하게 비효율적일 수 있다. ※ 기본적인 처리 과정 itemset generation의 후보자 선정 -> Frequent Itemset을 선택 ※ Downward Closure Property - Any superset of an itemset X cannot have higher support than X -> if an itemse..

데이터마이닝에 대한 대학 강의를 수강하면서 기본 개념 정리를 블로그에 기록하려 한다. ■ Market Basket Problem - 쿠팡이나 쇼핑몰 웹사이트에서 흔히 볼 수 있는 "구매자가 함께 구매한 상품"과 같은 기법을 구현할 때 사용된다. ex) Customer who bought beer also bought diapers - Motivation : cross-selling - 고객의 구매 패턴, 고객이 자주 함께 구매한 아이템들에 대한 Big data가 요구된다. ★ Basic Terms Transaction : 한 사람이 한 번 샀을 때의 item 집합 Frequent Itemset : minimum support 보다 support가 크거나 같은 Itemset Support(지지도) : tr..

이진 탐색 트리에 이어 트리와 유사한 구조를 가진 Heap에 대해서 알아보자. Heap(힙) 이란? 들어간 순서에 상관없이 우선 순위를 근거로 dequeue 연산을 진행하는 우선순위 큐의 형태 Max Heap과 Min Heap 두가지 컨셉이 존재한다. 부모와 자식의 key 값은 같은 경우 허용함 완전 이진 트리의 형태 ■ Max Heap - key 값이 큰 노드가 가장 우선 순위가 높음 - 각 노드의 key 값이 자식의 key 값보다 큰 트리 - 완전 이진 트리 ■ Min Heap - key 값이 작은 노드가 가장 우선 순위가 높음 - 각 노드의 key 값이 자식의 key 값보다 작은 트리 - 완전 이진 트리 1) Heap 삽입 연산(Max Heap에서) 20 15 19 8 13 10 23을 삽입(배열의..

이진 탐색 트리를 설명하기에 앞서 트리 구조에 대해 먼저 알아보자. 트리 구조란? 하나의 루트(root) 노드를 가진다. 나머지 노드들은 부모와 자식 관계의 노드들로 간선으로 이어진 계층형 자료 구조이다. 이진 트리란? 이진 트리는 트리의 모든 차수가 2인 트리를 말한다. 차수는 노드의 서브트리 개수를 말하는데 트리 내부의 서브트리가 항상 2개인 트리를 이진 트리라고 부른다. 이진 탐색 트리란? 탐색(검색)을 효율적으로 하기 위한 트리 구조 이진 트리이며 모든 원소는 서로 다른 유일한 key를 가진다. 왼쪽 서브트리의 key값 < 루트의 key값 < 오른쪽 서브트리의 key값의 법칙을 항상 따른다. 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다. 1) 탐색 연산 탐색할 key값 x를 루트 노드의 ..

지난 시간 DFS(깊이우선탐색)에 이어 BFS(너비우선탐색)에 대해서 알아보자. BFS(너비우선탐색) 시작 정점에서 가까운 정점이 먼 정점보다 먼저 방문되도록 하는 방식 시작 정점 v를 방문 v에 인접한 모든 정점들을 방문 새롭게 방문한 정점들에 인접하면서 과거에 방문하지 않은 정점들을 모두 방문 Queue를 이용 다음 탐색을 위해서는 Queue에서 dequeue를 하고 dequeue를 한 노드에서 시작한다. 이제 G7 그래프를 가지고 BFS 알고리즘에 대해서 알아보자. 위와 같은 G7 그래프가 있다. 이전 DFS 알고리즘과 같은 그래프를 가지고 BFS 알고리즘은 어떤 경로를 따라 최단경로를 찾는지 비교하면서 살펴보자. Queue 1) 시작정점 A에서 BFS 알고리즘을 시작한다. 2) 정점 A에서 방문하..

코딩테스트를 위해 백준이나 프로그래머스를 보다보면 DFS, BFS 용어에 대해서 한 번쯤은 듣게 될 것이다. DFS 원리와 BFS 원리를 적용하면 최단 경로를 쉽게 찾을 수 있다고 하는데, 오늘은 그 원리에 대해 알아보자. DFS(깊이 우선 탐색) 하나의 정점을 방문한다. 이웃한 정점으로 갈 수 있다면 무조건 이웃 정점 하나로 방문한다.(과거에 방문하지 않은 새로운 정점) 시작점으로부터 점점 깊어지는 노드로 전진하게 된다. 방문 가능한 이웃 정점이 없다면 backtracking을 통해 경로 상 가장 최근 방문했던 정점으로 돌아가서 또다른 새로운 노드 방문을 시도 한다.(stack 이용) 반드시 오름차순에 따라 이동한다.(경로상 갈림길을 만났을 때) 새로운 이웃한 노드가 존재하면 stack에 위치한 지점을..

최단 경로 알고리즘 중 가장 많이 사용된다고 할 수 있는 다익스트라 알고리즘에 대해서 알아보자 특징 : 무방향 그래프, 방향 그래프에 모두 적용 가능하다. 가정 : 모든 간선은 음이 아닌 비용을 가진다. ■ 다익스트라 알고리즘의 Concept 시작 정점 ~ 모든 다른 정점까지의 최단 경로를 구한다. 시작 정점 v에서 정점 u까지의 최단경로 dist[u]를 구해 정점 u가 집합 S에 추가되면 정점 u에 의해 단축되는 경로가 있는지를 반복적으로 확인한다. 현재 알고 있는 dist[w]와 새로 추가된 정점 u를 거쳐가는 dist[u] + cost[u][w]를 비교해 더 단축된 작은 값을 새로운 dist[w]로 가중치를 수정한다. dist A B C D E 0 10 5 ∞ ∞ pred A B C D E A A ..

List는 크게 LinearList와 LinkedList로 분류할 수 있다. 이 중 오늘은 LinearList에 대해서 다루어 보고자 한다. LinearList는 자료구조의 가장 단순한 나열 방식으로 순서를 가진 항목들의 모임이다. 다시 말해 일반적으로 쓰는 Array 배열과 같다고 생각하면 된다. -> 장점 : 구현이 간단하다. -> 단점 : 삽입, 삭제 시 오버헤드 항목의 개수 제한으로 비효율적이다. LinearList를 구현할 기본 함수를 먼저 셋팅해 주었다. ※ 원소 삽입 중간에 원소가 삽입되면, 그 이후 원소들은 한 자리씩 자리를 뒤로 이동해서 물리적 순서를 논리적 순서와 일치시켜야 한다. ① 원소를 삽입할 빈자리를 만든다. ② 준비한 빈 자리에 원소를 삽입한다. 기존 배열 10 20 30 40..