알고리즘/acmicpc
-
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개라 사용해도 무방하다. 그런데 나는 방향성을 가진 그래프라 적용할 수 없다고 생각해 계속 문제를 돌려서 풀었다. 양측에서의 도달가능성을 생각해주면 되는 간단한 사실을 알지 못해서 계속 이상한짓 하다가 겨우 풀었다. 아... 아직도 실력이 부족한건지 아니면 마음이 조급해서 그런건지 모르겠다 요즘 문제가 진짜 ..
-
1365알고리즘/acmicpc 2015. 7. 7. 18:01
전선이 꼬이지 않으려면 몇개의 전깃줄을 제거하면 되느냐는 문제는 LIS의 변형 문제와 같다. 연결되어있는 전선들 각각에 수치들을 준다면 하나도 꼬이지 않은 형태는 연결된 전선들이 증가하는 순열의 모양새와 같을 것이다. 이 순열들 중에서 가장 긴 순열을 찾으면 잘라내야하는 전선의 수도 자동적으로 알수있다. (잘라내야하는 전선의 수 = 총 전선의 수 - 가장 긴 순열에 포함된 전선의 수) LIS 는 기본적으로 dp를 이용해서 해결하는데 어떻게 푸느냐에 따라서 시간 복잡도가 다르다 예전에 for문을 두번 돌린 O(n^2)로 풀다가 조금 더 개선된 방법인 우선순위 큐를 사용했었지만 여기서는 우선순위큐로도 시간초과가 떴다 꽤 고민했지만 찾을수 없어 LIS 알고리즘을 인터넷으로 참고해보니 인덱스 트리를 사용하는 방..
-
7578알고리즘/acmicpc 2015. 7. 6. 18:15
문제를 푸는것 자체는 별로 어렵지 않았다. 부분합 문제를 변형한 형태이기 때문에 그 점을 잘 파악해서 풀면 된다. 가장 왼쪽에 있는 기기 부터 전선을 하나씩 이어가며 교차점의 수를 늘려간다. 교차점의 수를 찾는 방법은 가장 오른쪽으로 떨어진 지점까지 현결된 전선의 개수와 현재의 위치에서 기계와 연결된 지점 까지의 전선 개수를 빼면 된다. 가장 오른쪽으로 떨어진 점 까지의 연결된 전선의 개수는 교차 가능성이 있는 전선들이고 연결된 지점의 왼쪽에 있는 전선의 개수는 교차 가능성이 없는 전선들이기 때문에 둘의 차는 해당 지점에서 전선을 연결 했을 때 교점과 같다. 알고리즘은 쉽게 생각했는데 내가 틀렸던 이유는 교차점의 수가 int의 범위를 넘을 수 있다는 것을 생각하지 못했기 때문이다... 이미 틀려버린 3 ..
-
1753알고리즘/acmicpc 2015. 7. 1. 19:41
너무나 당연하게 알고있을 거라 생각했던 다익스트라.... 나는 다익스트라 알고리즘이 우선순위을 사용해야 한다는 것을 깜빡하고 있었다. 이 문제는 맨 처음에는 메모리 초과를 어떻게 해결할 것이냐로 속을 썩였었는데 메모리 초과를 해결 한 후에는 나의 다익스트라 알고리즘의 문제때문에 한동안 애를 먹었다.. 먼저 메모리 초과를 해결하는 방법부터 설명하면 정점의 개수가 20000개이기 때문에 20000*20000의 배열은 만들 수 없다. 그러므로 간선들만의 집합을 만들어두어야 한다. 이때 특정 정점에서 나오는 간선을 어떻게 indexing하느냐 문제가 있었는데 각 간선들을 출발 위치에 대해서 오름 차순으로 정리한 후 범위를 지정해주어서 해결했다. (지금 생각하면 간단하지만 여기까지 생각해내는 것도 참 힘들었다....