알고리즘/acmicpc
-
4307알고리즘/acmicpc 2015. 10. 17. 22:58
처음에는 '와 이 문제 장난아니다. 어떻게 풀어야되냐, 감이안온다 ㄷㄷ' 라 생각했는데 자세히 생각해보니 매우 간단한 문제임을 발견했다. 두 개미가 부딪히면 다른 방향으로 이동한다. 이건 둘이 교차한다는 의미랑 같다. 어차피 충돌하면 한 개미는 왼쪽으로 이동하고 다른 개미는 오른쪽으로 이동한다. 그러면 이건 교차한다고 봐도 무방하다. 결국 막대기를 벗어나는 개미들 중에 가장 오랜 시간이 걸리는 애를 고르면 되는 문제.. #include int main(){ int tc; scanf("%d", &tc); while(tc--){ int len, n, loc, min=0, max=0; scanf("%d %d", &len, &n); while(n--){ scanf("%d", &loc); int cur_min, ..
-
1577알고리즘/acmicpc 2015. 10. 16. 22:17
아 도로문제 ㅠㅠ 예전부터 이상하게 틀리던 문젠데 오늘 풀었는데 또 틀렸다. 대체 뭐가 문제인가 해서 친구한테 물어봤더니 장애물 저장방식에 문제가 있다고 했다... 사실 이문제는 별로 어려운 문제는 아닌데말이다... 내 실수는 0 0 0 1 1 0 1 1 이면 0 0 에서 1 0 은 장애물이 없는데 장애물이 있는것으로 인식한다는 것이다... 괜히 인접행렬 형태로 간소화해서 풀어보겠다고 했다가 틀렸다. 기하학 문제에선 여러가지 경우를 동시에 생각했어야 하는데 크으... 생각하지 못했다. 반성할 부분이다. #include using namespace std; struct obstacle{ int ax, ay; int bx, by; }; long long map[105][105]; obstacle obs[10..
-
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보다 무거운 추들이기..