알고리즘을 좋아하는 나

quick select 라는게 있어서 공부하고 사용했다.

1. quick select 함수 실행

2. pivot = partition

3. partition 에서는 pivot 을 기준으로 작은값과 큰 값을 나눈다.

4. pivot 을 정하면 그 것은 고정이 된다.

5. pivot 을 확인해서 값 출력

1. 한 바퀴 돌린다.

2. 한 바퀴 더 돌리면서는 업데이트 될 때마다, 무한대로 설정한다.

3. 그걸로 출력

다익스트라 알고리즘과 차이점

1. 음수 가중치가 있어도 작동이 된다.

2. 음수 사이클을 체크할 수 있다.

내가 작성한 코드의 worst time complexity 예상 O(V^2*E)

작동방식

1. distance 를 모두 임의의 값으로 체운다.

2. edge 에 가중치들을 넣는다.

3. vertex 만큼 forloop 을 하나 돌린다.

4. 그 안에서 연결된 edge 를 다 체크해준다.

5. cnt 가 N 이 된다는 것은 update 가 된다는 뜻 ( 음수 사이클 )

1. 입력값이 1 2 면 [1][2] = -1 [2][1] = 1

2. Floyd-Warshall 실행

3. 그대로 출력

아이디어만 있다면 간단한 문제

기존 floyd-warshall 알고리즘과 동일하게

1. i > j 를 갱신하고 싶다.

2. 어떻게 하지?

3. i > k > j 가 되는경우

끝.

i -> j 를 갈 때,

i -> k -> j 를 가는게 더 짧으면 업데이트 한다.

floyd-warshall 의 아이디어다.

O(V^3)

다음 문제때, 조금 더 자세히 살펴보면서 증명까지 가능하면 해보겠다.

이분 매칭을 2번 작동하면 된다.

글을 작성하다 날려서 더 길게 적고싶지 않다.

1. facebook 의 dectron

여러 객체들을 분석해주는 오픈소스 코드

여러 가지의 논문이나 알고리즘을 사용한다고 설명한다.

https://github.com/facebookresearch/Detectron

2. vr 100달러로 구현?

https://github.com/relativty/Relativ

아두이노를 사용하는거 같음

3. awesome 컴퓨터 사이언스

https://github.com/anu0012/awesome-computer-science-opportunities

4. 리액트 초기 설정?

https://github.com/facebook/create-react-app

awesome~~ 가 많다.

이번에는 자료가 많이 필요한 경우가 많았나봐요.

이분 매칭 문제를 엄청 오랜만에 풀어봤다.

https://en.wikipedia.org/wiki/Matching_(graph_theory)

http://koosaga.com/18

http://1ambda.github.io/algorithm/algorithm-part2-5/

위 링크에 많은 설명이 있고, 읽지는 않았다.

이 문제를 풀이한 방법은 아주 기초적인 DFS 를 이용한 O(V * E) 이다.

오늘은 시간이 없어서 이론보다는 구현을 목적으로 공부했다.

풀이 방법

1. 사람을 한명씩 dfs 로 연결할 수 있는 일을 잡는다.

2. 이미 연결돼있는 선이라면 그 선에 연결된 사람이 다른 일을 잡을 수 있는지 확인한다.

3. 반복

4. 끝