welcome!

문제 보기https://www.acmicpc.net/problem/11657 벨만포드 알고리즘이다. 알고리즘 분류 기능을 이용해 풀수있는 가장 첫 문제이며, 벨만포드 알고리즘을 그대로 사용하면 된다.기존소스에 반례가 있었다. 출발점에서 도달 할 수 없는 정점 간에 음수 경로가 존재해도 음수사이클 존재를 판단했던 것이다. 그리고 INF 값이 너무 작았다. 500*10,000+1 이상되어야한다. 수정하였음. 등록일이 18년 2월이었으니... 1년 8개월만에 수정한거네요!` 소스보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/11657.cc

백준 5719 거의 최단경로 난이도 꽤 있다고 생각함.https://www.acmicpc.net/problem/5719 다익스트라를 이용하여 최단경로를 저장해나가는데 pred 벡터에 이전 경로를 갱신해준다.그리고 이전경로를 모두 탐색해 그 경로를 재귀적으로 접근하여 -~ 사용할 수 없는 간선으로 만든다.그리고 다시 다익스트라를 활용한다. 그러면 거의 최단경로가 나온다. 개념적으로 와닿지만, pred 를 어떻게 벡터로 만들고, ... 그리고 어떻게 삭제하는가... 에 대해서 생각하는데 시간이 많이 걸린 문제였다. 여기서 아마 구현능력과 논리력이 갈리었을거라 생각한ㄷㅏ 리저널,, 문제였는데 어렵긴 어려운것 같다. 난 제한 시간내에 못풀었다 100% ㅋㅋㅋ. 이 문제로 인해 느낀점은, pred 벡터에 targ..

백준 1766 문제집원문보기https://www.acmicpc.net/problem/1766 방법론 : 위상정렬 + 우선순위 큐 이 문제는 위상정렬 문제이지만, 스페셜 저지가 아니였다. 즉 정답이 하나라는 이야기인데, 어떻게 이런 조건을 가지게 되었는지 살펴보자. 문제를 보면 n개의 문제와 m개의 간선 정보가 나온다. "문제" (실제 문제와 문제의 예제에 나오는 문제와 헷갈리지 않게 쌍따옴표로 강조했다.) 의 난이도가 낮는 것부터 우선순위를 두고싶다고 한다.그러면서도, 동일한 난이도가 없기 때문에 스페설 져지 문제가 아닌 답이 하나로 결정될수 있었다. 큐에서 꺼낼땐 난이도 낮은것부터 꺼내었다.C++의 STL priority_queue 자료구조를 이용했다. 소스보기 https://github.com/ing..

백준 2252 줄세우기원문보기https://www.acmicpc.net/problem/2252 방법 : topological sort n명의 학생과 m 개의 2-순서쌍이 주어진다. 이 때 전체적인 키비교 수열, 즉 n-순서쌍을 생성하시오. 라는 문제이다. 이 문제는 스페셜 저지 문제인데, 정답이 여러개 존재할 수 있다는 이야기이다. 위상정렬 문제는 주어진 방향간선으로 여러 개의 정렬된 n-순서쌍이 나올수 있는 것이다.한번 살펴보면, 2번 예제는4 24 23 1 은 그래프 그룹이 두 개이므로, (4, 2, 3, 1), (4, 3, 2, 1), (4, 3, 1, 2), (3, 1, 4, 2) 등등...몇 종류가 된다. 여기까지는 약간 응용없는 위상정렬인것 같다.아직은 방법론을 배우자는 입장이니까, 포스팅 된..

백준 1005 acmcrafthttps://www.acmicpc.net/problem/1005 startcraft 게임처럼, 빌드 순서가 주어진다. n개의 건물이 있고, 빌드 순서 간선은 k개가 있다고 하자.그 n개의 건물들 중 순서도에 따라 지어가는 도중에 어떤 w 건물을 이기는게 확정된다고 한다.이때 이길 수 있는 w 건물을 짓게되는 최소시간이 몇인가? 방법론 : 위상정렬 (topological sort) + 간단한 수학 위상정렬을 할 때 입차수가 0인 임의의 u노드를 현재 그래프에서 빼주는데,이 때 남아있는 그래프에서 그 노드 u를 포함하고 있는 간선E가 연결된 나머지 노드 v에 대해 indegree를 뺴주는 것을 확실히 한다. 여기 까지는 naive한 위상정렬 알고리즘으로 구현할 수 있다. 그런데..

백준 2623 음악프로그램문제보기https://www.acmicpc.net/problem/2623 n 명의 가수와 m명의 pd가 주어진다.m 명의 각각 pd는 자신만의 방법으로 음악방송 프로그램을 짜려고한다.각 pd는 선호하는 가수들의 방송 순서를 정해놓는데, 각 pd간의 가수 방송 순서를 준수하면서 음악 방송 스케쥴을 짤 수 있는지 체크해야한다.만약 그런 스케쥴이 존재할 수 없다면, 즉 존재하지 않는다면 0을 출력하고존재할 수 있다면 그 중 하나의 방송 스케쥴을 출력하라. 방법론 : 위상정렬 (topological sort graph algorithm)위상정렬 알고리즘 보기(* 추가 예정) 소스보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1..

Codeforces 911D Inversion Counting숫자로 이루어진 집합에서 그 집합에서의 특정 두 원소 ai, aj의 위치가 i > j 일떄 ai