처음에는 이걸 어떻게 풀지? 라는 생각이 들었던 문제. map의 크기가 작아서 브루트 포스로 걍 다 막아보면 된다. 재귀를 통해서 막을 수도 있을 것같지만, 나는 for문 3개를 돌려(...) 직접 다 막아보았다. time error가 나는 거 아닐까? 라는 생각이 들었지만 맵의 최대크기가 64이므로, 그럴 일은 없을 것같다. (모두 다 빈칸이라고 해도 64개중에 3개를 고르는 경우의 수는 64*63*62이므로 1억을 넘지않는다.) 그리고 바이러스를 퍼트리는 함수를 결정해야하는데 나는 dfs를 통해서 퍼트리는 것으로 구현하였다. 3개를 막고, 바이러스 퍼트리고, 숫자를 센 뒤, 초기화 하는 과정을 거쳤다. 처음 입력받을 때부터, 맵을 표현하는 배열을 두 개 만들었다. 하나는 계속해서 바꿔갈 맵을 또 다른..

algorithm에 있는 sort함수를 사용해서 구현하는 문제. 그 중에서 비교함수, cmp는 문제 조건에 맞춰서 작성해 주어야 한다. 그 전에 헷갈리는 return 값 부터 생각해보자. 비교 함수를 설정할때 cmp(a,b)의 return 값이 true 라면 cmp(a,b)에서 a가 먼저온다. cmp함수는 이렇게 구현하였는데, 채로 거르듯 조건마다 하나씩 걸러준다. 1. 길이 순으로 거르자. 1 2 3 4 5 //길이순으로 길이가 짧은 것부터 먼저 오도록 한다 if(alengthblength) return false; //길이가 같다면 if(alength==blength){ cs 2. 문자열 자리수의 합으로 거르자 1 2 3 4 5 6 7 8 9 10 11 12 for(int i=0;i='0' && (i..

그냥 구현하면 되는 거여서 엄청 쉬울줄 알았지만, 입력이 백만개나 되고, 생각보다 까다로웠던 문제(정답 비율이 27퍼인데는 이유가 있다) 구현은 그냥 그대로 했다. 배열에 수들을 입력받고, STL에 있는 sort 함수로 정렬을 해주었다. 그리고 현재 위치와 다음 위치에 있는 수가 같으면 count를 1 증가시켰고, 수가 다르면 count를 1로 다시 초기화하는 과정을 진행하였다. 여기서 시행착오가 많았는데 count를 초기화 하기 전에 지금 까지 나온 수 갯수중에 가장 많이 나온 것과 비교해주는 과정을 거쳐야 한다. 또 arr에 들어올 수 있는 수가 -2^62 부터 2^62까지 이므로 long long int로 구현해야 한다. 구현하는 종류의 문제이므로 설명보다는 소스코드에 있는 주석을 읽는 것이 나을 ..

정렬하기의 기본적인 문제. stable 하게 2번 정렬해서 사용할 수 도있고, 그냥 cmp함수를 사용하는 것도 가능하다. 두가지 방법 모두 풀어보았는데 vector을 사용해서 푸는 것이 구현하기 좀 더 간편해서 그렇게 해결하였다. sort 함수는 STL에 있는 걸 가져다가 썼고, cmp는 직접 구현해서 사용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 bool cmp(pair &a,pair &b) { if(a.firsta.second){ return true; } } return false; } Colored by Color Scripter cs 일단 첫번째 인자끼리 비교하였고, 둘이 같다면 두번째 인자를 비교하는 것으로 마무리하였다. 다른 경우는 생각해 볼 필요가 없는게, 완전히 동일한..

다른 정렬하기 문제와 다르게 입력이 최대 1천만번까지 주어진다. 일반적인 정렬 알고리즘이 최소 nlogn이므로 일반적인 정렬 알고리즘으로는 제한시간(3초)안에 계산 할 수 없다. 처음에는 sort 함수부터 bubble sort, quick sort, merge sort 까지 다 사용해봤지만,,, 계속 시간초과가 나오고 있었다. 이 문제에서 포인트는 주어지는 모든 수가 10000 이하라는 점이다. 배열을 사용해서 정렬하면, 공간복잡도는 조금 커지겠지만(그래봐야 10000밖에 안된다), 시간복잡도는 O(n+k)가 되므로 3초 안에 들어올 수 있다. 알고리즘 1. 크기가 10000인 배열을 하나 만들고 수가 입력될 때마다 해당 인덱스에 있는 값을 1씩 늘린다. 2. 인덱스가 각 숫자라고 생각할 수 있으므로 1..

에라토스테네체를 통해 소수가 아닌 수를 다 걸러내고 작은 소수 부터 나눠가면서 소인수분해를 진행한다. 에라토스테네스의 채란 ? 채로 거르듯이 범위내에서 소수가 아닌 수를 골라내는 방법으로 소수를 찾는다. 모든 수로 나눠보는 것보다 훨씬 빠르다. (모든 수로 나눌경우 O(N) = N^2, 에라토스테네스의 채를 사용할 경우 O(N)=N log(logN). 사실상 log(logN)는 1과 비슷하므로(n이 백만이라고 쳐도 1이 조금 안된다!), 엄청나게 빠른 알고리즘이다. 1 2 3 4 5 6 for(int i=2;ia; int arr[10000001]; // your code goes here for(int i=1;i

배열로 입력받아서 for문을 두번 돌면서 gcd 쌍의 합을 구하면 되는 문제. 두 수의 gcd를 구하는 방법으로 유클리드 호제법을 사용하였다. 1 2 3 4 5 6 7 8 9 int gcd(int a,int b) { while(b!=0){ int r=a%b; a=b; b=r; } return a; } cs 재귀 호출이 싫어서 이렇게 구현했지만, 재귀로도 유클리드 호제법을 구현할 수 있다. 1 2 3 4 5 6 7 8 9 int gcd(int a,int b) { while(b!=0){ int r=a%b; a=b; b=r; } return a; } cs 이것을 기반으로 gcd라는 함수를 만들어서, 배열의 각 원소를 돌면서 gcd 연산을 해주었다. 주석처리를 해서 이해하는데 문제가 없을것같다. 1 2 3 4 ..

0부터 n까지 정수 k개를 더해서 그 합이 n이 되는 경우의 수. dp를 사용하고, 점화식을 생각해보자. 정수 k개를 더해서 그 합이 n이 되는 경우는 정수 k-1개를 더해서 그 합이 n-L(0