분류 전체보기
-
1946알고리즘/acmicpc 2015. 10. 16. 02:03
진짜 문제를 무지하게 꼼꼼히 읽어야 한다. 문제 잘못 이해하면 바로 틀린다. 이 문제를 풀때 나는 생각보다 빨리 서류심사 결과 또는 면접 성적으로 정렬해야 하는것을 깨달았다. 하지만 여기서 부터 꼬이기 시작했는데 서류심사 1등의 면접 성적 만큼 뒤에있는 서류 심사 순위는 모두 커버된다는 괴상한 논리를 펴기 시작했다. 서류 심사가 떨어지고 면접심사도 동시에 떨어질 수 잇는 것인데도 나는 혼자만의 논리에 빠져서 이상하게 문제를 질질 끌었다.. 예제문제부터 제대로 풀지 않았다. 누구 누구가 합격한다는 힌트만 줘도 이렇게 뻘짓은 하지 않았을 것 같다. 하지만 뭐 이건 내 실수니... 문제자체는 많이 어렵지는 않았던 것 같다. 일단 서류 순위로 정렬한다. 서류 1등은 면접과 상관없이 독보적이므로 무조건 포함될 수..
-
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 이상인 경우는 두 클라우드의 크기를 곱해서 가중치를 정리하는 방식까지. 이해하는 것은 별로 어려운 것은 아니나 이렇게 생각해낸다는 것 자체가 어려운것 ..