분류 전체보기
-
c++ priority_queue에서 comparator 선언해주는 방법알고리즘/자료구조 2015. 8. 26. 11:49
class Prove{ public : int pos, cost, time; Prove(int nposition, int ncost, int ntime){ pos = nposition; cost = ncost; time = ntime; } }; class mycomparison { public: bool operator() (const Prove& a, const Prove& b) const { return a.time > b.time; } }; priority_queue mypq; 위의 Prove class는 내가 문제를 풀기 위해 임의로 만든 것이기 떄문에 무시해도 된다.만약 int인 priorityqueue를 만들고 싶다면 priority_queue으로 선언하면 된다. 여기서 세가지 인자가 들어가는..
-
10217알고리즘/acmicpc 2015. 8. 26. 11:43
최단거리 + 제한비용 문제이다. 다익스트라로 해결하면 쉽겠지 하고 생각하다가 곰곰히 생각해보니 순수한 다익스트라 방법으로는 위 문제를 풀 때 예외가 발생한다는 것을 깨달았다. 다익스트라는 "어느 정점의 최단 경로를 확인 했다면 그 경로와 그와 인접한 정점들의 최단 경로를 연결 할 수 있다" 는 원리로 구할 수 있다 하지만 위 문제에서는 어느 정점의 최단 경로를 확인해도 그 정점과 연결된 다른 정점들과의 최단 경로를 연결 할 수 있다고 말을 할 수가 없다. 왜냐하면 제한비용이 있기 때문이다. 예를 들어 현재 A점에 오는데 두 가지 방법이 있다고 하자 경로를 (최단거리, 현재 남은 비용)이라 하겠다 (10, 5), (30, 100) 여기서 B점까지 가야한다. 그런데 B점까지 가는 방법으로는 두가지 방법이 있..
-
2638알고리즘/acmicpc 2015. 8. 24. 17:33
어떻게 외부 공기를 깔끔하게 처리할 것이냐가 위 문제를 푸는데 가장 중요한 요소이다 초등부 문제와는 다르게 위 문제는 격자 가장자리에도 치즈를 올려 둘 수 있다는 조건이 문제를 푸는데 어려운 요소였던 것 같다. 그래서 나는 애초에 치즈 격자를 1,1 부터 시작하게 한 후 바깥 공기를 찾기 위해서 0,0 부터 찾도록 만들었다. 즉 문제에서 주어진 격자 보다 2열을 더 추가해 격자를 만들고 추가한 격자를 이용해 바깥 공기를 자동으로 찾을 수 있도록 만들었다. #include #include #include #include using namespace std; int map[105][105]; int main(){ int R, C; int res=0; queue q; int clk=0; ifstream ifp..
-
1238알고리즘/acmicpc 2015. 8. 24. 15:20
파티하는 학생의 집에 까지 가는 경우와 돌아오는 경우 각각에 대해서 시간을 따로 구해야 하는것이 문제의 핵심이다. 처음에는 문제를 풀 때 각 노드 사이에 걸리는 모든 시간을 다 구해야 하나 하고 생각을 하다 파티하는 학생의 집을 출발점으로 두는것과 도착점으로 두는 것 모두 동일한 경우로 판단 할 수 있어서 다익스트라 알고리즘을 두 번 돌리는 것으로 해결했다. 각각의 노드들 마다 간선을 inflow, outflow로 arrow를 표현하니 코드가 간결해졌다. #include #include #include #include using namespace std; vector outflow[1005]; vector inflow[1005]; int in_d[1005]; int out_d[1005]; void dij..
-
9470알고리즘/acmicpc 2015. 8. 22. 16:22
topological sort를 이용하면 별로 어렵지 않은 문제... 하지만 이 문제는 꽤 많은 시간을 허비했다 알고리즘 문제를 풀 때 자신이 유지하는 자료구조의 스펙을 정확히 해야한다. 내가 위 자료구조는 어떠한 값을 입력해둘 것인가를 확실히 해두어야 후에 스스로에게 헷갈리지 않는다. 머릿 속으로만 모두 해결하려 하지 말고 자신의 자료구조를 손으로 그려보는 것이 가장 좋은 방법일 것 같다. #include #include #include #include #include using namespace std; int indeg[1005]; int order[1005]; vector orders[1005]; vector edges[1005]; int main(){ int tc; int tc_num, node..
-
2515알고리즘/acmicpc 2015. 7. 17. 13:59
옛날에는 못풀다가 컨디션 좋은날 불현듯이 아이디어가 생각나서 풀었다. 예전에 내가 풀었던 방식은 DP였긴 한데 너무 문제를 어렵게 생각해서 못풀었던 것 같다. 그때나 지금이나 원리는 비슷한데 한 끗의 차이 때문에 맞고 틀림이 결정되었다. 어차피 최대의 이윤을 내려면 전시품들이 키 순서대로 있어야 한다. 먼저 키 순대로 정렬하고 크기 차이가 S이상 나는 전시품들의 부분 집합 중에서 가장 큰 부분 집합을 구하는 것이 문제 푸는 데 핵심이다. 위 문제는 DP로 해결 할 수 있다. 키 순서대로 하나 하나씩 차근차근 풀어가면 된다. 알고리즘 순서도는 다음과 같다. 1. 내가 i 번째 그림을 체크 한다고 하자. 2. i번째 그림과 크기 차가 S이하로 나는 그림들 중(j까지라 하자)에서 지금까지 나온 가장 최고의 이..
-
2458알고리즘/acmicpc 2015. 7. 15. 20:13
초등학생들한테 이런 문제를 풀라고 하는 것도 웃기고 이것 가지고 몇시간 낑낑데는 나도 참 웃기다... 간단히 생각하면 되는데 왜 나는 이 문제를 가지고 stack이니 queue니 하면서 접근 한건지.. 비교 가능을 묻는 문제는 그래프 문제로 바꿀 수 있고 각 그래프가 연결 되었는지로 판별 가능하다. 연결 가능성은 floyd warshall 알고리즘으로 한방에 해결 가능하다. 어차피 input도 500개라 사용해도 무방하다. 그런데 나는 방향성을 가진 그래프라 적용할 수 없다고 생각해 계속 문제를 돌려서 풀었다. 양측에서의 도달가능성을 생각해주면 되는 간단한 사실을 알지 못해서 계속 이상한짓 하다가 겨우 풀었다. 아... 아직도 실력이 부족한건지 아니면 마음이 조급해서 그런건지 모르겠다 요즘 문제가 진짜 ..
-
인덱스 트리알고리즘/자료구조 2015. 7. 7. 18:05
일정 데이터 집합에 대하여 구간별로 특정한 데이터를 저장해둔 것을 인덱스 트리라 한다. 특정 값은 주로 최대값이나 최소값을 의미한다. 위 자료구조를 통해 주로 Min Max Tree를 만든다. 만드는데 시간이 상당히 오래 걸리며 한 번에 깔끔히 완성하는 것은 상당히 어렵다. BIT에서 해결하지 못했던 최대 최소 문제를 해결해줄 수 있는 알고리즘이긴 하지만... 구현하는데 시간이 오래걸리는 것은 아쉽다. int tree[20][100000]; void update(int height, int piv, int data){ if(height==18) return; if(tree[height][piv] < data){ tree[height][piv] = data; update(height+1, piv/2, da..