백준 2637 : 장난감조립 https://www.acmicpc.net/problem/2637 위상정렬(Topological Sort) 를 활용한 문제.단순히 indegree를 사용해서 순서만 설정해주는 것이 아니라정해진 순서대로 진행하면서 상위 부품의 비용을 업그레이드 시켜주어야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77#include #include #include #inc.. 더보기 백준 4386 : 별자리 만들기 https://www.acmicpc.net/problem/4386 MST 문제에 있어 입력정보에 애초에 간선에 대한 정보와 가중치가 주어진다면 쉽지만꼭 간선에 대한 정보가 주어지지 않을 수도 있다.노드에 대한 정보가 주어지고 그 정보를 토대로 간선 후보를 추출해야 한다. 이 문제의 경우 간선 후보가 될 수 있는 최대 경우의 수가 100*100으로 최대 10만번 연산밖에 안되기때문에간선 후보를 모든 행성이 연결된 것으로 할 수 있다.먼저 별에대한 입력정보를 받고 별을 n^2 연산으로 간선을 만들고 Kruskal 알고리즘 적용한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 .. 더보기 백준 13418 : 학교 탐방하기 https://www.acmicpc.net/problem/13418 Kruskal 알고리즘을 이용한 풀이단 최소 스패닝 트리 뿐만 아니라 최대 스패닝트리도 동시에 구현해주어야 한다.Sort() 를 오름차순과 내림차순 두번 구현하는 것 보다 그냥 오름차순으로 한번 sort해주고 최대 스패닝트리를 구할때 reverse_iterator 를 이용해 Unionfind 하여 시간을 단축시킬 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 .. 더보기 백준 1197 : 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 MST 기본문제. UnionfindfindRoot 할때 메모이제이션하는것 잊지말자.현재 노드에서 재귀적으로 갈 수 잇는 최대 root를 바로 vRoot에 저장하면속도를 훨씬 줄일 수 있다. Kruskal은 항상 작은 비용이 드는 간선부터 확인해보되간선이 연결하고 있는 두 노드 i 와 j 가 이미 연결되어있나 확인하고연결이 안되어있을때 연결시켜준다. 연결여부 확인은 서로의 루트노드를 재귀적으로 따라가서 그 결과루트노드가 같은지 여부를 확인하는 것이다. 연결해주는 것은 서로의 루트노드에 상하관계를 만들어주는 것이다.j 의 최상단 루트의 루트를 i 의 최상단루트로 처리한다.따라서 현재 i 와 j 를 포함한 모든 노드들의 최상단 루트는 i 의 최.. 더보기 백준 16398 : 행성 연결 https://www.acmicpc.net/problem/16398 Kruskal 알고리즘과 UnionFind에 대한 개념을 알고있으면 쉽게 풀수 있는 문제였다.(물론 학교 시험때는 못풀었지만..) 수업때 최소비용신장트리(MST) 개념에 대해 배웟는데몇일만 더 빨리 배웠었으면.. 아무튼 간단하게 요약하자면MST 란 그래프의 노드를 간선으로 연결함에 있어 각 간선마다 다른 비용이 든다.이때 그 비용을 최소화 시켜야 한다. 1. 간선 연결은 spanning tree 구조이다. -> 즉 n개의 노드가 있으면 간선(edge)은 n-1개로 모든 노드를 연결 시켜야 하며 -> 이때 n-1개로 구성한 노드는 Cycle이 돌지 않아야 한다. MST를 풀기 위한 대표적인 알고리즘은 Kruskal 과 Prim이 있는데이문.. 더보기 백준 11581 : 구호물자 https://www.acmicpc.net/problem/11581 Cycle이 존재하는지 묻는 문제이다.그래프의 시작점은 1부터 시작해서 n까지 도착하는 것이고모든 그래프를 탐색하면서 도중에 Cycle이 돌면 안된다. Cycle이 도는지 검사하는 것은 여러가지 방법이 있지만이 문제에서는 이미 그래프가 주어졌고 그래프의 노드를 모두 탐색하는 것이므로DFS를 사용한다. Stack을 이용한 DFS도중에 만약 이미 visited한 점을 만났다면 그것이이전에 되돌아가서 visited 체크된것인지 아니면 이미 방문해서 visited가 된것인지 확인해야 한다. 만약 Stack에 이미 visited 체크된 노드가 존재한다면 이미 방문한 노드이기 때문에 cycle이 발생한다.만약 visited 체크된 노드이지만 Sta.. 더보기 백준 16397 : 탈출 https://www.acmicpc.net/problem/16397이번에 우리학교 코딩대회에 나갔다.. 복수전공 시작하고 아직 학교 수업은 자료구조를 듣는 터라알고리즘에 관한 지식은 구글링하며 독학하며 주워들은 것 밖에 없다. ABC 세문제 밖에 못풀었는데D와 K 2문제는 풀 수 있었을 것 같은데 아쉽게 계속 시간초과가 났다. (이 두 문제만 풀었어도..)어쨌든 반성하는 의미에서 시험장에서는 못풀었지만 더 공부하며 나머지 문제를 다 풀어보려한다. D번 문제였던 탈출은 시험장에서 계속 DFS밖에 생각이 안났다. 그것도 평소 DFS를 재귀로만 구현해서문제를 풀어봤던지라 스택으로 짜는 것은 아무생각이 안들었음. 이 문제를 시험 다다음날 구글에 검색해보았는데 BFS로 풀었다고 한 순간 머리가 띵해졌다.생각해보니.. 더보기 DFS (깊이우선탐색) DFS(깊이 우선 탐색)알고리즘 문제에서 BFS(너비 우선 탐색)과 더불어 굉장히 많이쓰이는 기법.그래프에서 더 이상 나아갈 길이 보이지 않을 때까지 한 루트를 깊숙히 탐색하는 방법으로더 이상 나아갈 길이 없을 때 이전 노드로 돌아가 끝까지 탐색. 1번 정점에서 출발했을 때 방문 순서는 1-2-4-8-5-6-3-7 이 된다.5번 정점에서 는 더이상 방문할 곳이 없으므로 이전 노드인 8번으로 되돌아가서 다음 후보지인 6번으로 이동한다.이처럼 현재 노드에서 갈 수 있는 지점까지 방문하고 갈 수 없으면 되돌아가는 방식. Memoization을 이용한 Backtracking에응용될 수 있다. 크게 DFS를 구현할 때1. 재귀호출2. 스택두 가지를 이용하여 구현할 수 있다.다음은 위의 그림 예제를 c++로 구현해.. 더보기 이전 1 2 3 4 5 6 다음