일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- union-find
- 그리디
- Algospot
- 분할정복
- DP
- 유니온파인드
- stack
- 백준
- 완전탐색
- 분리집합
- 이분탐색
- 알고스팟
- 알고리즘문제해결전략
- 스택
- DFS
- 종만북
- 너비우선탐색
- 백트래킹
- 동적계획법
- 재귀
- acm
- Greedy
- 세그먼트트리
- priority_queue
- BOJ
- backtracking
- BFS
- 문자열
- 다이나믹프로그래밍
- 누적합
- Today
- Total
목록분류 전체보기 (105)
DAMPER's blog
Finding similar items ex. - pages with similar words - Customers who purchased similar products - Images with similar features - Recommendations and search Problem definition 고차원 데이터 points x1, x2, .... , xn이 주어진다. distance fuction d(x1, x2) 가 주어진다. 이는 x1과 x2 사이의 거리를 나타낸다. d(xi, xj)가 s보다 작은 모든 pair of data points(xi, xj)를 찾아보자. Naive solution : O(N^2) N은 data points의 크기를 나타낸다. LSH를 사용하면 O(N)만에 가..
A pirori algorithm 2-pass 접근법으로 메인 메모리 사용을 줄일 수 있다. Key Idea : Monotonicity 만약 아이템 셋 I가 적어도 s번 등장한다면, 집합 I의 모든 부분집합 J 또한 s번 이상 등장한다. 만약 아이템 i가 s 미만으로 등장한다면 i를 포함안 아이템 부분집합이 s 번 미만으로 등장한다. A-priori algorithm 구성 1. pass-1 : 모든 transaction을 1회 읽으면서 메인 메모리에 각각의 아이템의 등장횟수를 저장한다. item수만큼의 메모리 저장 공간이 필요하다. items that appear >= s times are frequent items 2. pass-2 : 모든 transaction을 다시 읽으면서 각각의 아이템의 등장횟수..
연관 규칙 찾기 많은 transaction이 존재한다고 하자. 각 transaction에는 아이템들의 부분집합이 있을 때 연관규칙을 찾아보자. Q1 : transaction들에서 빈번하게 등장하는 아이템 부분집합을 찾자 Support 란? 부분집합 I를 모두 포함하는 transaction의 수 또는 부분집합 I를 모두 포함하는 transaction의 비율 다음 표는 각 transaction에 해당하는 Item들을 나타낸 표이다. Transaction ID Items 1 Bread, Coke, Milk 2 Beer, Bread 3 Beer, Coke, Diaper, Milk 4 Beer, Bread, Diaper, Milk 5 Coke, Diaper, Milk 위 표에 따르면 부분집합 {Beer, Brea..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/VqBbA/btrKzEyZMvk/3d9V0DFKrg57zbIwpQ20j1/img.png)
https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=299409119 Do it! 알고리즘 코딩 테스트 : 파이썬 편 네이버, 카카오, 삼성, 라인 등 주요 IT 기업의 시험에 나오는 알고리즘 내용이 모두 담겨 있다. 책에 수록된 알고리즘 문제 100개는 모두 최신 기출 유형을 반영하고 있어서 이 책의 문제만 다 풀 www.aladin.co.kr 좋은 기회가 되어 이지스퍼블리싱의 'Do it! 알고리즘 코딩 테스트 파이썬 편(김종관)' 의 서평단을 하게 되었습니다. 기회를 주신 이지스퍼블리싱 관계자님께 감사 말씀을 전합니다. 현재 IT관련학과 4학년이기도 하고, 알고리즘 관련 동아리에서 튜터로 활동한 경험을 바탕으로 책을 학습자의 입장과 지도자의 입장에서 바라보려고..
https://www.acmicpc.net/problem/7869 7869번: 두 원 첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다. www.acmicpc.net 문제 설명 두 원이 주어졌을 때, 두 원이 교차하는 영역의 넓이를 소수점 셋째자리까지 구하면 된다. solve 문제에서 제시하는 조건은 각 원의 중심 좌표와 반지름이다. 코사인 법칙을 활용해 문제를 해결할 수 있다. 먼저 두 원의 위치를 파악한다. 두 원의 중심을 잇는 선분을 긋고 이 선분의 길이를 d라고 하자. 1. 두 원이 멀리 떨어져 교차하는 영역이 없는 경우. ( d > r1 + r2) 2. 두 원이 외접하는 경우 ( d = r1 + r2) 3. 두 원이 ..
https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 설명 문제 제목처럼 플로이드-워셜 알고리즘을 한 뒤, 경로 추적을 통해 i -> j 로 가는 최소비용의 경로를 출력하는 문제이다. solution 먼저 플로이드-워셜 알고리즘을 통해 최소비용 테이블은 만든다. i에서 j로 가는 비용을 i -> k -> j 비용으로 갱신할 때, 추적 테이블에 i -> j 갈 때 k를 거쳐간다고 저장한다. 1 2 3 4 5 6 7 8 9 10 11 12 13..