알고리즘
-
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..
-
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하느냐 문제가 있었는데 각 간선들을 출발 위치에 대해서 오름 차순으로 정리한 후 범위를 지정해주어서 해결했다. (지금 생각하면 간단하지만 여기까지 생각해내는 것도 참 힘들었다....
-
1795알고리즘/acmicpc 2015. 7. 1. 16:13
이 문제는 딱 보면 어떻게 해결해야 할지 감이 안잡히는데 그래프를 사용하라 하면 어느정도 문제푸는 방법을 깨닫는다 이 문제에서 힌트는 암호들이 정렬되어 있다는 것이다. 사용하는 문자들의 알파벳 정렬을 그래프의 간선으로 설정해서 표현하고 DFS를 통해서 풀면 된다. 기존 DFS랑 다른 점은 한 번 방문한 점을 또 방문 할 수 있다는 점인데 그 노드에서 빠져 나올 때 방문하지 않은 걸로 바꾸면 풀 수 있다. #include #include #include #include using namespace std; int map[26][26]; vector v; int L, C; bool test(char t){ if(t == 'a' || t=='e' || t=='i' || t=='o' || t=='u') retu..
-
union find알고리즘/자료구조 2015. 6. 27. 11:04
알고리즘 문제를 풀다 보면 노드들 간의 집합이 존재하는 경우가 있다. 이때 해야할 일이 크게 두 가지 있다.1. 두 노드가 같은 집합에 포함되어 있는지, 다른 집합에 있는지 확인하는 작업2. 두 집합을 병합하는 작업 사람마다 위 과정을 처리하는 방법이 모두 다르고 시간복잡도도 다르다.나 또한 무식하게 문제를 풀때는 O(n^2)이렇게 풀기도 했다. 하지만 위 작업을 최적화한 자료구조로 union find가 있다.(양교수님께서 알려주신 내용인데 당시에는 학점받기에 급급해 제대로 공부하지 못했다.) 그림파일 올리려고 했는데 귀찮아서 못올리겠다http://blog.secmem.org/521좋은 블로그가 있으니 여기를 참고하길.. void init(int n){ for(int i = 1; i