알고리즘
-
2481알고리즘/acmicpc 2015. 9. 1. 19:39
경로가 주어지지 않아 스스로 경로를 만들고 최단 경로를 찾아내는 문제이다. 각각의 이진수들 마다 정점으로 생각하고 그 정점과 해밍 거리가 1인 정점들을 연결해야 한다. 기존의 방법들은 간선을 배열에 저장해두기도 하는데 여기서는 정점의 최대 개수가 100000이라 n*n으로는 저장이 안될 것 같아서 정점을 방문 할 때마다 매번 간선을 확인하는 것으로 했다(정점마다 가능한 최대 간선수가 30뿐이라 시간 복잡도에 영향을 주지 않을 것 같기 때문이도 했다) 여기서 이진수를 그대로 가져 갈 것인가? 아니변 변환 할 것인가로 고민을 했는데 다행히 이진수의 최대 길이가 30이므로 int 10진수 값으로 변환했다. 정점을 표현하는데 더 쉬웠다. 특정 정점에서 해밍 거리가 1인 정점이 존재하는지 안하는지를 파악해야한다...
-
LIS를 O(nlogn)시간 내에 해결하는 방법알고리즘/자료구조 2015. 8. 27. 11:13
LIS는 수열 중에서 가장 긴 수열의 길이를 찾는 방법이다. 동적 계획법 해결 방법은 이전에 찾았던 수열의 마지막 값들 중 현재의 위치의 값보다 작으면 그 마지막 값이 가지고 있는 수열의 길이에 1을 더하는 방식이다. 조건에 해당하는 수열 중에서 가장 긴 수열을 선택해야 한다. 기존의 방법은 긴 수열을 찾는데 O(N)의 시간이 걸려 모든 배열의 값을 탐색한 후에는 전체 알고리즘 복잡도는 O(N^2)가 되었다 하지만 길이 L 인 수열의 마지막 값들 중 최소 값을 저장하는 배열을 둔다고 생각해보자 C[L] C[]배열은 순 증가하는 그래프가 될 것이다. (간단히 설명하자면 C[N]은 C[N-1]의 영향을 받을 것이고 C[N-1]은 현재 길이에서 최소의 값을 가지기 때문에...귀납적으로 설명하면 그렇다. 직감적..
-
1987알고리즘/acmicpc 2015. 8. 26. 13:19
BFS로 풀다가 메모리 초과가 떠서 DFS로 해결했다. 간단히 재귀함수를 만들어서 해결했는데 속도를 높이고 싶으면 재귀 함수를 사용하지 않고 stack을 이용해서 해결해도 좋을 것 같다. #include #include #include #include #include using namespace std; class Finder{ public: int r, c, sum; bool visited[30]; }; char map[25][25]; int R, C; long long res = 0; void dfs(Finder s, long long walk){ int r = s.r; int c = s.c; int newcost = s.sum+1; res = max(res, walk); if(r-1>=0 && !s..
-
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..