분류 전체보기
-
2465알고리즘/acmicpc 2015. 9. 8. 17:24
Segment Tree를 공부한 후 풀지 못했던 문제들을 쏙쏙 해결하고 있다. 정보가 계속 업데이트 되며 거기서 특정한 값을 구해야 할 때 사용하기 유용한 자료구조이다. 줄세우기 문제 또한 그렇다. 문제를 풀기 위한 전체적인 알고리즘은 주어진 키를 정렬 한 후 문제에서 주어진 수열의 맨 뒤 하나씩 확인한다. 현재의 정렬에서 주어진 값에 해당하는 index를 고르고(배열은 0부터 시작한다 그러면 앞에 주어진 값 만큼이 자신보다 작은게 있는게 확실해지므로) 선택한 키 값은 정렬에서 뺀다 그렇게하면 식이 하나밖에 성립되지 않을 것이다. 여기서 문제는 뒤에서 중간에 있는 것들을 선택하기 때문에 배열 자체가 계속 작아진다는 것이다. 이것을 해결하기 위해 어떻게할까 생각을 많이 했었는데 segment tree를 사..
-
Segment Tree알고리즘/자료구조 2015. 9. 7. 16:34
옛날에 min max Tree를 공부 할 때 배열 특정 구간 내에서의 최대값과 최소값을 미리 저장해두어 범위가 주어 질 때 O(logN)시간내에 해결 했었는데 이렇게 구간 내의 특정 값을 저장해두는 방식을 Segment Tree라고 하나 보다. 범위가 주어지면 위 배열을 이용해서 해결하면 된다. 만약 3~6사이의 범위에 대해 구하라고 하면 이렇게 풀면 된다. 사실 이건 생각하는 것은 책 한번 보면 어렵지 않은데 이걸 어떻게 구현 할 것인가가 문제이다. 예전에는 이차원 배열 사용하며 메모리 낭비도 심하고 코드도 지저분하게 풀었는데 코드포스에 깔끔한 구현이 있어 참조해본다 void build(int id = 1, int l=0, int r=n){ if(r-l=y)return 0; if(x
-
SQRT Decomposition알고리즘/자료구조 2015. 9. 5. 20:39
만약 알고리즘 문제에서 해당 배열의 특정 구간(L, R)에서 최소값을 구하라는 문제가 나왔다면 가장 일반적으로 생각 할 수 있는 방법은 L, R 구간을 모두 탐색해보는 방법일 것이다. 하지만 테스트 케이스의 개수가 많고 배열의 크기가 크다면 시간이 오래 걸릴 것이다. 여기서 사용 할 수 있는 방법이 sqrt decomposition이다. 크기 N인 배열을 sqrt(N)으로 쪼개서 최소값을 저장하는 배열(sqrt 배열)을 미리 만들어 둔 후 주어진 구간의 최소값 찾을 때는 구간 내에 포함된 sqrt배열에 해당하는 최소값과 그 이외의 부분들의 값을 비교해서 해결 할 수 있다 현재는 최소값을 구하는데 사용했는데 이것 말고도 다양한 정보를 저장하는데 사용 할 수 있을 것 같다
-
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인 정점이 존재하는지 안하는지를 파악해야한다...
-
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..