분류 전체보기
-
2590알고리즘/acmicpc 2015. 10. 15. 11:34
처음에는 엄청 어려운 문제인줄 알았다... 색종이가 판의 경계에도 놓일 수 있다면 이건 정말 어려운 문제고 초딩용으로는 전혀 적합하지 않은 문제라 생각했다.. 그런데 문제를 꼼꼼히 읽어보니 하나의 색종이는 하나의 판에만 놓일 수 있다는 조건을 확인했다. 그러면 문제가 정말 쉬워진다. 색종이 큰 것 부터 탐색하고 남는 것들을 채워나가는 식으로 하면 된다. 이런 문제는 코드를 깔끔이 짜는것이 관건이다. 잘못하다간 자신도 코드를 알아보지 못하는 경우가 있기 때문이다. 반드시 수기 작업에서 변수명까지 선언해준 후 컴퓨터로 옮기도록 하자 #include int main(){ int d[7]; for(int i=1; i0; cur--){ while(d[cur]!=0){ res++; int rem = 36 - cur..
-
1931알고리즘/acmicpc 2015. 10. 14. 20:40
mergesort를 직접 구현해서 풀어보려고했는데 stack overflow문제가 계속 났었다. 나는 무한루프 때문인가 생각했는데 알고보니 함수 내에 지역변수를 너무 크게 잡은 메모리 초과가 원인이었다. recursion 할 때 stack 메모리에 어떻게 쌓이는지 다시 한 번 복습하는 기분이었다. 해결방법은 지역변수를 크게 안잡고 전역 변수로 두면 된다. 어차피 한 번의 recursive한 함수가 한 번만 접근하니까. 여기서 여러개의 thread돌리는 것이 아니기 때문에 공유 문제는 걱정 안해도 된다. #include using namespace std; struct course{ int start, end; }; course c[100005]; course tmp[100005]; int mySort(i..
-
11000알고리즘/acmicpc 2015. 10. 11. 15:00
최소 강의실의 개수를 구하는 문제. 먼저 수업들을 시작 시간을 기준으로 다시 정렬을 해두자. class[] 그리고 현재 강의실중 가장 수업이 빨리 끝나는 강의실을 관리하는 자료구조를 가지고 있다고 하자. (우선순위 큐를 이용해서 관리하는게 좋다) 정렬된 배열 class[] 에 있는 i번째 수업을 내가 추가하고자 한다면 현재 강의실 중에서 가장 수업이 빨리 끝나는 강의실에 추가하는 것이 최적의 경우일 것이다. 만약 i번째 수업의 시작시간이 가장 수업이 빨리 끝나는 강의실의 끝나는 시간보다 더 일찍 시작한다면, i번째 수업은 반드시 강의실을 추가해서 들을 수밖에 없다. 다른 강의실들은 가장 수업이 빨리 끝나는 강의실보다 더 늦게 끝날 것이 분명하기 때문이다. 우선순위큐와 정렬을 적당히 활용해서 풀면 쉽게 풀..
-
2405알고리즘/acmicpc 2015. 10. 9. 20:39
상당한 아이디어를 요구하는 것 같은 문제이나 실제로 푸는 방법은 간단하다. N이 최대 1000이기 때문에 가능한 모양 순열 123, 132, 213, 231, 312, 321 의 가정답을 나열한 다음 원래 주어진 모양 순열에서 가정답으로 바꿀 때 각각의 최소 횟수를 구해 전체 최소 횟수를 구할 수 있다. 각 모양은 최소 한 번 이상 나타난다는 조건으로 문제 풀이에 살짝 힌트를 주었다. 최소 횟수를 구하는 것은 간단하다. 여기서는 3가지 모양 밖에 없다는 사실을 잘 이용하자. #include #include using namespace std; int data[100005]; int res_arr[100005]; int d[4]; int main(){ int N, ret; scanf("%d", &N); r..
-
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 이상인 경우는 두 클라우드의 크기를 곱해서 가중치를 정리하는 방식까지. 이해하는 것은 별로 어려운 것은 아니나 이렇게 생각해낸다는 것 자체가 어려운것 ..