그리디 알고리즘으로 O(N)으로 최적화 (미제)

우선순위 큐를 정렬하는 방법을 알아야 한다 삽입과 삭제는 O(logN)의 시간이 걸린다 문제: https://www.acmicpc.net/problem/11286 https://github.com/surinoel/boj/blob/master/11286.cpp

심화 정렬문제 문제: https://www.acmicpc.net/problem/1431 https://github.com/surinoel/boj/blob/master/1431.cpp

가장자리에 치즈는 존재하지 않는 점을 이용해서 벽을 bfs로 구할 수 있다 문제: https://www.acmicpc.net/problem/2638 https://github.com/surinoel/boj/blob/master/2638.cpp

N 제한이 큰 경우라 규칙을 찾아서 O(N)에 끝내야한다 먼저 차례대로 레벨을 번호대로 부여한다 그리고 순서쌍을 탐색하면서 갑은 +1 을은 -1로 레벨을 업데이트한다 그리고 레벨이 겹치지 않는다면 정상적으로 순서가 나오게 된다 문제: https://www.acmicpc.net/problem/14864 https://github.com/surinoel/boj/blob/master/14864.cpp

위상정렬의 대표적인 문제 [참고] https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html [참고] https://blog.naver.com/ndb796/221236874984 위상정렬은 먼저 DAG(Directed Acyclic Graph)을 기반으로 하는 알고리즘이다. DAG는 방향 그래프와 비사이클 그래프를 모두 만족하는 그래프다. 따라서 순서가 정해진 그래프로, 순서를 지키며 정렬하는 알고리즘이 위상정렬이다. 탐색을 하면서 가장 중요한 요소는 자신 전에 존재하는 노드들(차수) 그리고 자신 다음의 노드 총 2가지다. 그래서 차수가 0인 것을 먼저 큐에 넣고 탐색을 진행한다. 그리고 그와 연결된 차수를 하나씩 지워나가면서 차수가 ..