Coding Test/codility
-
[codility] MinAbsSum c++Coding Test/codility 2022. 9. 23. 21:15
문제 문제 해결 각 원소로 만들 수 있는 합의 개수 구하고, 그 합들을 이용해 전체 합에서 가장 작은 수가 구해질 때 까지 빼나간다. 1. A행렬의 원소를 모두 양수로 전환한다. A원소에 1 or -1 곱한 뒤 합을 구하는 거라 A의 원소가 양수여도 상관없다. 2. 양수로 변환된 A행렬의 원소의 합을 구하고 최댓값도 구한다. 최댓값을 구하는 이유는 각 원소의 개수를 구하는 것이고, 전체 합을 구하는 이유는 답의 가장 최악의 경우는 전체 합이기 때문 3. 각 원소마다 돌면서 가능한 부분 합들을 구한다. 이전에 가능한 부분합이 있었다면, 단순히 현재 원소의 개수를 넣어준다. 처음 만들어진 부분합이라면, 재사용한 것을 표기하기 위해 -1 한다. 4. 부분 합들을 전체합의 절반까지 계산하면서 전체 합에서 2배만..
-
[Codility] NumberSolitaire c++Coding Test/codility 2022. 9. 16. 19:19
문제 N개의 연속된 정사각형으로 구성된 보드에서 게임이 진행된다. 0번 정사각형의 조약돌을 N-1 정사각형으로 이동시켜야 하는 게임이다. 각 차례마다, 주사위를 던지고 주사위 윗면의 숫자 K를 고려한다. 그런 다음 현재 I에 서 있는 조약돌을 I + K로 이동시킨다. I + K가 존재하지 않으면 유효한 인덱스를 얻을 때까지 주사위를 다시 던진다. 게임이 끝난 후(조약돌이 N-1 로 이동했을 때), 이동한 모든 사각형에 쓰여진 숫자의 합을 구한다. 결론, A[0] → A[N-1] 로 이동할 때의 배열 원소의 최대 합을 구하는 문제이다. 문제 해결 int solution(vector &A) { vector temp(A.size(), -1); temp[0] = A[0]; for(unsigned int i = ..
-
[Codility] GenomicRangeQuery c++Coding Test/codility 2022. 8. 11. 15:00
문제 DNA서열은 A, C, G, T 로 구성 되어 있고 1, 2, 3, 4 로 표현된다. string으로 DNA 서열이 주어진다. 배열 P ,Q 의 K번째 값으로 string s의 K(P) ~ K(Q)번째 원소들 중 서열이 제일 먼저인 DNA 인덱스를 저장한다. 문제 해결 2중 for문을 사용하면 시간 복잡도 테스트를 통과하지 못해서 2중 for문을 사용하지 않게 코드를 짜보았다. // you can use includes, for example: #include vector solution(string &S, vector &P, vector &Q) { vector result; for (int i = 0; i < P.size(); i++) { int index = Q[i] - P[i]; string ..
-
[codility] MaxCounters c++Coding Test/codility 2022. 4. 10. 10:01
문제 문제 풀이 #include #include #include int solution(std::vector &A) { sort(A.begin(), A.end()); int index = A.size() - 1; if (A.at(index) < 0) return 1; int min = 1; for (int i = 0; i < index + 1; i++) { if (min == A[i]) min++; } return min; } #define MaxCounters #ifdef MaxCounters int main() { std::vector nVec = { 1,3,6,4,1,2}; std::cout
-
[codility] MaxCounters c++Coding Test/codility 2022. 4. 10. 09:21
문제 배열 A가 주어진다. A의 원소들은 +1 count 되는 배열의 인덱스를 의미한다. A[0] = 3 -> (0, 0, 1, 0, 0) : 3번째 자리 +1 A[1] = 4 -> (0, 0, 1, 1, 0) : 4번째 자리 +1 A[2] = 4 -> (0, 0, 1, 2, 0) : 4번째 자리 +1 -> 여기서 max count 발생 A[3] = 6 -> (2, 2, 2, 2, 2) : max counters = 6 -> 모든 원소 값을 원소의 최댓값인 2로 설정 A[4] = 1 -> (3, 2, 2, 2, 2) : 1번째 자리 +1 A[5] = 4 -> (3, 2, 2, 3, 2) : 4번째 자리 +1 A[6] = 4 -> (3, 2, 2, 4, 2) : 4번째 자리 +1 최종 return 값 = ..
-
[codility] PermCheck c++Coding Test/codility 2022. 4. 9. 21:32
문제 permutation(순열) 인지 체크하는 문제이다. 문제 해결 처음에 생각한 풀이는 75%가 나왔다. 1. A배열의 합 구하기 2. A배열의 크기로 A.size() 일 때 순열의 합 구하기 3. 1,2 비교하기 #include #include #include #include #include int solution3(std::vector &A) { int len = A.size()+1; long sumP = len * (len + 1) / 2; long sumA = std::accumulate(A.begin(), A.end(), 0); if (sumP != sumA) return 0; return 1; } #define PermCheck #ifdef PermCheck int main() { std:..