알고리즘/acmicpc
-
2616알고리즘/acmicpc 2015. 10. 3. 00:34
이런 문제가 2003년 초등부 올림피아드에 나왔으니 내가 당시 초등학교 6학년이었으니까,, 감히 이런걸 푼다고 상상도 했을까... 이런 문제를 푸는 괴물들도 있었겠지. 나는 이걸 대학생이 되어서야 풀게 되었다. 이 문제는 DP문제이다. 어떻게 DP를 구현하느냐에 따라서 해결 방법이 천차 만별이다. 총 세개의 기관차를 쓰는게 이 문제를 푸는데 핵심이다. 처음에는 각 구간별로 n개의 소형기관차를 썼을 때 최대 값을 구하는 함수를 사용했다. 하지만 이건 배열을 여러번 탐색해야해서(O(N^n)) 시간초과가 뜬다. 어떻게 해야할지 고민하다가 세개의 기관차를 사용하는 것에서 방법을 찾았다. 먼저 현재 위치에서 소형차기관차를 연결했을 때 태울 수 있는 승객을 저장하는 배열을 만든후 d[0][50000]에 넣어둔다. ..
-
2463알고리즘/acmicpc 2015. 9. 29. 14:05
내가 직접 푼 문제는 아니고 게시판의 글을 참조해서 풀었는데 정말 감탄할만한 방법으로 풀었다... 기본적으로 이 문제는 MST의 형태를 가진 문제이다. 여기서 MST는 최소 스패닝 트리가 아니라 최대 스패닝 트리이다. 문제가 요구하는 조건이 다르다보니 기존 방식으로 트리를 형성해야 문제를 풀 수 있다. 문제를 푸는 핵심은 각각의 클라우드 사이를 연결 시키기 전에 형성된 에지들을 제외하고는 모든 에지들의 가중치를 더해야 한다는 점. 기존에 형성된 에지들의 가중치를 pastCost에 넣어서 정리하는 깔끔함이 놀라웠다... 게다가 이미 두 클라우드의 크기가 2 이상인 경우는 두 클라우드의 크기를 곱해서 가중치를 정리하는 방식까지. 이해하는 것은 별로 어려운 것은 아니나 이렇게 생각해낸다는 것 자체가 어려운것 ..
-
2465알고리즘/acmicpc 2015. 9. 8. 17:24
Segment Tree를 공부한 후 풀지 못했던 문제들을 쏙쏙 해결하고 있다. 정보가 계속 업데이트 되며 거기서 특정한 값을 구해야 할 때 사용하기 유용한 자료구조이다. 줄세우기 문제 또한 그렇다. 문제를 풀기 위한 전체적인 알고리즘은 주어진 키를 정렬 한 후 문제에서 주어진 수열의 맨 뒤 하나씩 확인한다. 현재의 정렬에서 주어진 값에 해당하는 index를 고르고(배열은 0부터 시작한다 그러면 앞에 주어진 값 만큼이 자신보다 작은게 있는게 확실해지므로) 선택한 키 값은 정렬에서 뺀다 그렇게하면 식이 하나밖에 성립되지 않을 것이다. 여기서 문제는 뒤에서 중간에 있는 것들을 선택하기 때문에 배열 자체가 계속 작아진다는 것이다. 이것을 해결하기 위해 어떻게할까 생각을 많이 했었는데 segment tree를 사..
-
2457알고리즘/acmicpc 2015. 9. 4. 11:37
월과 일로 표현되어있는 날짜 단위를 하나로 통합한 후에 문제를 풀어야 한다. 나는 월/일을 모두 일로 바꿔서 계산했다. 이게 가장 쉬운 방법인것 같다. 나머지는 회의실 배정 문제와 비슷하다. 현재 꽃이 지기 전에 먼저 피어있는 꽃 들중에서 가장 늦게 지는 꽃을 고르면 된다. 여기서는 범위가 주어진다는 점 (3/1~11/30)과 문제의 조건에서 꽃이 지는 날은 꽃이 폈다고 볼 수 없다는 조건에 유의해서 문제를 풀면된다 O(N)에 해결하기 위해 sorting한 후 알고리즘을 적용했다. #include #include #include #include using namespace std; int days[13]={0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; str..
-
2481알고리즘/acmicpc 2015. 9. 1. 19:39
경로가 주어지지 않아 스스로 경로를 만들고 최단 경로를 찾아내는 문제이다. 각각의 이진수들 마다 정점으로 생각하고 그 정점과 해밍 거리가 1인 정점들을 연결해야 한다. 기존의 방법들은 간선을 배열에 저장해두기도 하는데 여기서는 정점의 최대 개수가 100000이라 n*n으로는 저장이 안될 것 같아서 정점을 방문 할 때마다 매번 간선을 확인하는 것으로 했다(정점마다 가능한 최대 간선수가 30뿐이라 시간 복잡도에 영향을 주지 않을 것 같기 때문이도 했다) 여기서 이진수를 그대로 가져 갈 것인가? 아니변 변환 할 것인가로 고민을 했는데 다행히 이진수의 최대 길이가 30이므로 int 10진수 값으로 변환했다. 정점을 표현하는데 더 쉬웠다. 특정 정점에서 해밍 거리가 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..
-
10217알고리즘/acmicpc 2015. 8. 26. 11:43
최단거리 + 제한비용 문제이다. 다익스트라로 해결하면 쉽겠지 하고 생각하다가 곰곰히 생각해보니 순수한 다익스트라 방법으로는 위 문제를 풀 때 예외가 발생한다는 것을 깨달았다. 다익스트라는 "어느 정점의 최단 경로를 확인 했다면 그 경로와 그와 인접한 정점들의 최단 경로를 연결 할 수 있다" 는 원리로 구할 수 있다 하지만 위 문제에서는 어느 정점의 최단 경로를 확인해도 그 정점과 연결된 다른 정점들과의 최단 경로를 연결 할 수 있다고 말을 할 수가 없다. 왜냐하면 제한비용이 있기 때문이다. 예를 들어 현재 A점에 오는데 두 가지 방법이 있다고 하자 경로를 (최단거리, 현재 남은 비용)이라 하겠다 (10, 5), (30, 100) 여기서 B점까지 가야한다. 그런데 B점까지 가는 방법으로는 두가지 방법이 있..