BOJ (25) 썸네일형 리스트형 [BOJ] 2472 체인점 굉장한 학생 문제랑 다익스트라의 짬뽕이다. 덕분에 코드가 장난아니게 길다.각 정점이 최대 5개의 간선을 가지니 다익스트라의 $O(ElgV)$ 시간복잡도가 $O(VlgV)$로 바뀐다. 그러면 주어진 세 정점에 대해서 다익스트라를 한번씩 돌려볼 수 있고, 모든 정점에 대해 주어진 세 정점으로부터 각 정점으로부터의 거리 $dist_i$가 나오게 된다. 거리의 범위는 크지만 대소관계만을 비교하면 되므로 등위를 정렬을 통해 다시 매겨주자. 그러면 굉장한 학생 문제처럼 모든 정점에 대해 체인점을 세울수 있음/없음을 판별할 수 있다. 그 이후 들어오는 쿼리는 $O(1)$에 처리 가능하다. 수행 시간은 다익스트라, 정렬, RMQ 등이 다 섞여서 결과적으로 $O(NlgN)$이다. 개인적으로 문제 자체도 굉장한 학생 문제.. [BOJ] 1504 특정한 최단 경로 문제: https://www.acmicpc.net/problem/1504 그냥 다익스트라 몇번 돌리면 된다. 어차피 두 정점을 반드시 지나야 하는 것이라면 시작점->1번->2번->종점 아니면 시작점->2번->1번->종점 2가지 방법 안에서 반드시 최단경로는 나오게 되어 있다. 난이도는 1.75/5. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #define INF (100000000) using namespace std; int n;vector lis[805]; vecto.. [BOJ] 1916 최소비용 구하기 문제: https://www.acmicpc.net/problem/1916 그냥 다익스트라 그 자체이다. 풀이를 설명할 필요가 있을까? 난이도는 1.5/5 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #define INF (2100000000) using namespace std; int main(){ int n,m,st,en; scanf("%d %d",&n,&m); priority_queue Q; vector lis(n+1,vector()); vector dist(n+1,INF); for(int i=0;idist[here]) continue; for(.. [BOJ] 13306 트리 문제: https://www.acmicpc.net/problem/13306 2016 KOI 중등부 3번 문제인 트리이다. 고등부 3번과 굉장히 비슷한 문제이기는 한데, 듣기로는 고등부 3번은 HLD라는 알고리즘을 써야 한다고 알고 있는데 이 문제는 상대적으로 깔끔하게 발상의 전환을 통해 문제를 해결할 수 있다. 실제로 대회장에 갔을 때도 모든 풀이는 다 생각해 놨는데 자료구조 구현을 못해서 실패했다. 웬만하면 풀이를 보기 전에 생각을 더 해봤으면 하는 좋은 문제. 내 해법은 Union-Find Tree로 알려져 있는 자료구조 (Disjoint Set)을 구현해서 문제를 역순으로 풀어 나가는 것이다. 어떤 정점과 그 정점의 부모 정점을 제거하면 그 두 트리는 분리되게 된다. 두 정점 사이에 경로가 존재하려.. [BOJ] 11052 붕어빵 판매하기 문제: https://www.acmicpc.net/problem/11052 너무 쉬워서 자세한 설명은 생략한다. 난이도는 그냥 1/5 123456789101112131415161718192021222324252627282930313233343536#include #include #include #define INF (987654321) using namespace std; int n;int cost[1005];int cache[1005][1005]; int dp(int b, int c){ if(b==0) return 0; if(c>n) return -INF; int &ret=cache[b][c]; if(ret!=-1) return ret; int ma=0; for(int i=c;i [BOJ] 9466 텀 프로젝트 문제: https://www.acmicpc.net/problem/9466 내가 사이클에 무지하게 약하다는 것을 깨닫게 해준 문제다. 문제 자체는 특별할 게 없음에도 불구하고 이렇게 헤메는 걸 보면 망한 것 같다... 처음에 시작한 정점을 따로 체크해두고 처리하면 되는 문제였는데 코드를 좀 더 깔끔하게 짜 보겠다고 괜히 엉뚱하게 푼 것 같다. 보니까 다른 사람들도 다 이런 비슷한 방식으로 푼 것 같다. 만약 이미 사이클이 처리된 정점에 도달했다면 (색깔이 다르면) 그냥 바로 0을 반환하는 것으로 시간 초과를 막았다. 나는 개인적으로 1.75/5정도는 주고 싶은데 다른 사람들은 훨씬 쉽게 푼듯. 123456789101112131415161718192021222324252627282930313233343536.. [BOJ] 1992 쿼드 트리 문제: https://www.acmicpc.net/problem/1992 매우 쉬운 분할 정복 문제이다. 그냥 전구간이 하얀색/검은색인지 체크해서 분할하고 재귀함수로 넘겨주면 된다.사실 재귀함수에 인자를 4개 줄 필요도 없고 (핵심) 모두가 검은색/하얀색인지의 판정도 $O(n^2)$으로 미리 전처리 해두면 $O(1)$로 찾을 수 있다. 그렇지만 귀찮기도 하고 굳이 그렇게 할 이유가 없기에 생략. 가장 좋은 알고리즘은 문제를 가까스로 풀 수 있는 알고리즘이다. 코드는 다음과 같다. 좀 더럽긴 하다. 난이도는 1.25/5 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #includ.. [알고리즘] 최소 스패닝 트리 최소 스패닝 트리 (Minimum Spanning Tree, MST)는 모든 정점을 연결하면서 가장 작은 가중치를 가지는 트리를 만드는 알고리즘이다. 트리를 만드는 알고리즘이므로 이 그래프는 사이클이 없는 DAG 형태여야 한다. 이 문제를 해결하는 데에는 두 가지 알고리즘이 대표적으로 사용되는데, 바로 크루스칼 알고리즘과 프림 알고리즘이다. 일단은 크루스칼 알고리즘을 설명한 뒤에 프림 알고리즘을 구현할 때가 되면 그때 와서 추가해 놓겠다.크루스칼 알고리즘 크루스칼 알고리즘은 모든 간선 중 가장 가중치가 작은 간선부터 차례로 연결시키는데, 만약 새로 연결하는 간선 때문에 사이클이 생긴다면 그 간선을 포기한다. 원리도 굉장히 간단하고 구현도 굉장히 간단하다. 근데 Greedy한 알고리즘 답게 증명은 간단하지.. 이전 1 2 3 4 다음