전체 글
-
인덱스 트리알고리즘/자료구조 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
-
1197알고리즘/acmicpc 2015. 6. 27. 10:53
반성해야하는 문제다 너무 문제에 성급하게 접근했다. 최소스패닝트리는 kruskal이든 prim이든 둘 중 하나를 이용해서 풀면된다. 나는 kruskal을 사용했는데 여기서 각각의 클라우드를 병합하는 과정에서 실수가 있었다. 이것은 union find라는 자료구조를 이용해서 해결해야하는데 나는 두 노드중 발견된 것들을 제외한 것만 본다고 했으니 당연히 틀릴 수밖에 없다. (아마 이 글을 읽는 사람은 뭔말인지 모를 것이다 나만 이해할 수 있는 문장..) 프림알고리즘을 사용했으면 틀리지 않았을 것 같다... #include #include #include using namespace std; int height[100001]; int par[100001]; struct Node{ int con_a, con_b..
-
2268알고리즘/acmicpc 2015. 6. 26. 11:54
집가기 전에 하나 풀고 가겠다고 성급하게 덤볐다가 쓸데없이 두 번 틀린 문제다. 펜윅트리를 다시 정의해서 풀면 된다. update를 이전 값에서 차이값을 갱신해주면 된다. #include #define MaxVal 1049577 int tree[MaxVal]; int data[MaxVal]; int read(int idx) { int sum = 0; while(idx > 0){ sum += tree[idx]; idx -= (idx & -idx); } return sum; } void update(int idx, int val) { while(idx