알고리즘을 좋아하는 나

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

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. 끝

기둥 세우는 부분을 어떻게 처리할까 고민을 했다.

1. forloop

2. recursive 한 방법

2번은 뭔가 생각을 더 해줘야 될거같아서 귀찮았다.

그래서 1번을 선택함.

1. 정렬하는거 처럼 forloop 을 작성해주고 기둥을 세워준다음, 맵을 복사

2. BFS 로 세균 옮기기

3. 안전한 부분 확인

1 -> 2 -> 3 -> 1

쭉 반복해주고,

최댓값을 출력하면 끝

알고스팟 문제와 동일해서 쉽게 풀었다.

달라진 점이라면 시작점이 0이 아니라는것과 test case 가 여러개라는것

이 부분만 잘 기억해야겠다.

분류가 다익스트라로 돼있어서 의문이 들었었다.

BFS 또는 DFS 면 되지 않을까??

질문 게시판을 가보니 BFS & Prirority queue 를 이용해서 최단거리를 구하는 것은 다익스트라다!

질문 게시판에서 솔루션은 얻었는데, 아이디어를 모르겠었다.

그래서 검색을 좀 하니까 바로 아이디어를 얻었다.

1. 도착지점에 도착할때, 가장 작은 가중치를 출력하라.

가장 작은 가중치를 출력할 때, Prioritiy queue 를 이용한다.

weight 를 기준으로 Priority queue 를 구성

2. 그러면 도착한 순간이 가장 작은 가중치를 갖게된다.

끝.

1 -> N 의 최단거리를 구하면 된다.

조건 

1. v1 를 거쳐야 된다.

2. v2 를 거쳐야 된다.

3. 양방향 그래프다.

문제를 보니 민힙을 구현한 다익스트라를 사용해야 될 것 같았다.

풀이 방법

중위 표기식을 후위 표기식으로 변경해 주면 된다.

1. 스택에 자기 자신보다 높은 우선순위를 가진 연산자가 있으면 빼서 사용한다.

2. 스택에 입력된 연산자를 push 한다.

3. 괄호가 끝나면 사용하지 않은 연산자를 다 출력한다.

4. 남은 연산자들을 출력한다.

중간 값을 출력 하면 된다.

처음 풀이는

그냥 min-heap 이던 max-heap 이던 구현한 다음에, 그 중간값을 출력했는데 틀렷다.

그래서 질문 게시판을 보니까.

중간값을 기준으로 왼쪽 오른쪽을 나누라는 거다!

그래서 나눔

이제 heap 을 직접 구현하지 않고, priority queue 를 사용한다.

그리고 이 문제를 푸는데 계속 틀렸다.

틀린 이유는 card 의 조합 개수가 1일 때 0을 출력해야 되는데,

입력 된 카드를 다 출력해서 계속 100%에서 틀렸다.

수식은 

a + b + ((a + b) + c)

위에 단계가 반복되면 결과가 나온다.

(a + b) = result 에 계속 더해주면 된다.

증명은 아직 할줄을 몰라서..

예제가 잘 돼있는 문제다.

이제 아무것도 안 보고 최대힙이나 최소힙을 짤 수 있다.