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:..
-
[codility] FrogRiverOne c++Coding Test/codility 2022. 4. 9. 21:08
문제 개구리가 가장 빨리 강을 건널 수 있는 나뭇잎의 위치?의 인덱스 값을 구하는 문제같다. A배열의 인덱스인 K는 시간(초)를 의미한다고 한다. 문제 해결 1. set 자료구조를 사용한다. set은 중복을 허용하지 않고, 자동으로 오름차순으로 정렬되는 특징이 있다. set 변수의 크기가 X와 같다면 목적지X에 도달한 것이다. #include #include #include #include #include int solution(int X, std::vector &A){ int len = A.size(); std::set nSet; for (int i = 0; i < len; i++) { nSet.insert(A.at(i)); if (nSet.size() == X) return i; } return -1..
-
[codility] TapeEquilibrium c++Coding Test/codility 2022. 4. 9. 19:06
문제 |(A[1] + ... + A[P-1] ) - (A[P] + ... +A[N])| 을 구하는 문제이다. 즉, A배열의 0~(P-1)번 까지 합 - 나머지 원소의 합의 절댓값을 구한다. P 값에 따른 절댓값 중 최솟값을 구하는 문제이다. P의 범위 : (0 < P < N) 문제 해결 #include #include #include #include #include int solution2(std::vector &A) { long end = std::accumulate(A.begin(), A.end(), 0); long len = A.size(); long front =0; int minimum = INT8_MAX; for (int i = 0; i < len - 1; i++) { front += A.at..