이언배 연구노트

job assignment problem 을 생각해보자.총 n 개의 job 이 있고, set $A$ 만큼의 지원자가 있다고 하자.$A$ 중에서 $A_i$ 가 $i$ 번째 직종에 지원 가능하다고 했을 때, $A_1$ 부터 $A_n$ 까지 각각 한명씩 매칭시킨 $x_1$ 부터 $x_n$ 을 찾을 수 있다.이게 대표적인 system of distinct representatives 문제. Definition.A matching: a set of pairwise non-incident edges (independent edges): vertex가 안겹치는 edge 들의 set.matching covers the vertices: matching 에 포함되는 edge 들에 닿은 vertex 들.perfect m..

NAVER web crawling 결과로 도무지 파악할 수 없었던 인허가 데이터를NAVER API 를 활용해 하나하나 쿼리해본 결과를 csv로 저장해뒀다. 이제 이 결과물을 PostGRES 로 옮겨서 SQL로 다시 한 번 매칭해볼 것이다. 폴더에 저장된 csv 들을 불러들여 PostGRES로 이동시키는 건 간단하다. import pandas as pdfrom sqlalchemy import create_engine #Dataframe -> SQL 에는 sqlalchemy 를 불러오자from glob import glob# csv 파일들 불러오기filenames = glob('./폴더이름이뭐에요/*.csv') #glob 함수에서 '*.csv' 는 모든 csv 파일을 불러준다. 이 결과물은 'text의 리스..

6.4. List coloring and Brooks' TheoremDefinitionlist assignment (L): a function on $V(G)$ such that $L(v)$ 가 $v$에게 'acceptable' 한 색상 set이다. $v$ 가 가질 수 있는 색상의 리스트 매핑L-coloring: $f(v) \in L(v)$ for all $v$. 모든 $v$ 가 가질 수 있는 색상 리스트 L 내에서 적절히 골라갈 수 있다.k-choosable : L-coloring whenever $|L(v)| \geq k$ for all $v$. 색상 리스트가 모두 $k$개 이상인 상태에서 L-coloring 이 가능.list chromatic number / choice number / choosa..

Definitionwalk: sequence $v_1v_2...v_k$  of vertices and a sequence of edges $v_iv_{i+1} \in E(G)$. edge 로 건너건너Closed walk: $v_1 =v+k$. 어찌되었건 건너건너 돌아옴trail: all edges are distinct. Edge 안겹치고 건너건너closed trail: Edge 안겹치고 건너건너 돌아옴path: all vertices are distinct. Vertex 안겹치고 건너건너Cycle: closed walk 인데 vertex 안겹치고 건너건너 돌아옴.Length of the walk: k-1 G is connected: all pairs $u, v \in V(G)$, there is a p..

Definition.Graph G: a pair (V, E)V(G): a set of verticesE(G): a multiset of edges$|G| = |V(G)|$: the order of G: order 은 vertex 갯수$e(G) = |E(G)|$: the size of G: size 는 edge 갯수Loop: an edge of size 1graph 가 simple 하다: loop 나 multiple edge가 없다 u 와 v 가 adjacent: $uv \in E(G)$. 둘 사이 edge가 있다v 와 e가 incident: $v \in e$, edge 중 하나에 포함된다e 와 e'가 incident: $e \cap e' \neq \emptyset$ e랑 e' 는 공통의 vertex를 가..

Edge present 'conflict'6.1 Chromatic number and bounds on itDefinitionk-coloring: vertex labeling $f: V(G) \rightarrow S$ where $|S| = k$. 각 vertex마다 k개 중에 하나로 labelingk-coloring f is proper: $f(x) \neq f(y)$ when $xy \in E(G)$. 붙어있는 애들끼리는 다른 색으로 labelling하는 fk-colorable: proper k-coloring 이 있음The chromatic number $\chi(G)$: minimum k such that G is k-colorable. proper coloring 가능하게 만드는 최소 색상 갯수..

이번에 해야할 태스크는 크게 1. PostGRES 에서 Third Place 정보를 불러온다2. Python 으로 Third Place 를 검색한 NAVER API 결과물을 JSON 형태로 얻는다3. 기존 검색 결과와 일치 여부를 확인한다4. 데이터베이스에 저장한다 로 이루어져있다. 여기서 고민해야할 부분은 3번과 4번.JSON 에서 정보를 추출하는 건 python 이 편할 것 같지만,추출한 정보와 기존 정보의 비교 및 저장을Python - csv 로 할지, Python - Postgres - Database 의 형태로 할지가 고민이다.내가 편하고 다루기 좋은 건 csv지만, 용량이 너무 아깝고, 시간도 느리다.Database 는 부가적인 작업이 필요 없지만 업데이트가 까다로운 경우가 있다. 그래, 기왕..

진짜 되도록이면 하나하나 map.naver.com/ 으로 쿼리하는 짓은 하고싶지 않다...그래도 NAVER API 는 공식적으로 제공해주는 데이터니까 조금 낫지 않을까?최소한, 정제되어있는 형태의 무언갈 주지 않을까...? 하는 기대에 NAVER API 를 무턱대고 시작해보았다. 1. NAVER Developers 에 가입하기네이버 개발자 센터 - NAVER Developers NAVER Developers네이버 오픈 API들을 활용해 개발자들이 다양한 애플리케이션을 개발할 수 있도록 API 가이드와 SDK를 제공합니다. 제공중인 오픈 API에는 네이버 로그인, 검색, 단축URL, 캡차를 비롯 기계번역, 음developers.naver.com로 접근해서 API 신청에 필요한 정보를 얻으려고 했다.며칠 걸..