알고리즘
-
2437알고리즘/acmicpc 2015. 10. 9. 19:47
이것도 스스로 못풀고 인터넷에 있는 풀이를 보고 풀었는데 정말 어떻게 이걸 생각해냈는지 대단하다는 느낌이 들면서도 간단한 풀이를 생각하지 못한 스스로에게 반성하게 되었다. 이건 dp문제로도 볼 수 있다. 먼저 추들을 정렬한다. 그리고 k는 1~N 사이에 있는 수로 가정하자 나는 1~k번까지의 추들을 통해서 최대 M까지의 무게를 만들 수 있다 치자(만약 못 만든다면 그전에 끝내버리면 된다) 이제 나는 k+1번째 추를 추가하고 싶다. 그런데 k+1번째 추의 무게가 M+1이 아니고 1을 더해서(1을 더하는 이유는 앞에서 내가 1부터 만들어 낼 수 있기 때문이다) M+1보다 크다면 나는 죽었다 깨어나도 주어진 추들의 조합으로 M+1을 만들 수 없다. 왜냐면 k+1보다 뒤에 있는 추들은 k+1보다 무거운 추들이기..
-
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를 사..
-
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..