기록하지 않았다면 잃어버릴 시간들

새로운 것을 배우는게 즐거운 개발자입니다.

알고리즘/Codility

요약 A배열의 연속된 정수 집합을 slice라고 할때 가장 작은 평균을 갖는 slice의 시작위치를 반환 아이디어 수학적 지식을 요구하는 문제 1. a (a+b+c)/3을 만족한다. 5. 원소가 2개 또는 3개인 케이스만 확인을 한다. 코드 int solution(vector &A) { // write your code in C++14 (g++ 6.2.0) double minAvg = (A[0] + A[1]) / 2.0; double Avg = 0; int sol = 0; for (int i = 2; i < A.size(); i++) { Avg = (A[i - 2] + A[i - 1] + A[i]) / 3.0..

2021. 8. 24.

알고리즘/Codility

요약 DNA 관련 문제입니다. DNA를 이루는 뉴클리오타이드 염색체 A, C, G, T가 들어 있는 문자열 S가 주어지고 이 염색체는 각각 1, 2, 3, 4와 매칭이 됩니다. 그리고 S.size() 미만의 정수가 들어 있는 P와 Q가 주어집니다. 문자열 S에서 P와 Q 사이에 있는 염색체중 가장 작은 값을 가지는 정수를 구해서 각 케이스마다 정수를 벡터에 차례로 모아서 반환하면 됩니다. 예를 들어 S = "CAGCCTA"이고 P[0] =2, P[1] = 5, P[2] = 0 / Q[0] = 4, Q[1] = 5, Q[2] = 6라고하면 P[0] ~ Q[0]는 2~4사이의 문자열인 GCC인데요 여기서 G는 3 C는 2이기때문에 2가 반환이 되어야합니다. P[1] ~ Q[1]은 5~5인 T는 4입니다. 아..

2021. 8. 22.

알고리즘/Codility

요약 정수 A와 B사이에서 K가 몇번 나누어지는지 반환하는 문제입니다. 아이디어 B가 K로 나누어 떨어지는 수 - A가 K로 나누어 떨어지는 수를 하면 됩니다. 다만 고려할점은 A가 K로 나누어 떨어질때 나머지 없이 나누어 떨어지는지만 생각하면 되는데요. 문제의 예시에 보이는 것 처럼 6 11 2 가 주어진다고 했을때 11/2는 5이고 6/2는 3이기때문에 아이디어대로 하면 정답은 2가 되어야하지만 실제로 11과 6 사이에는 10 8 6 총 3개가 있기 때문이죠 코드 int solution(int A, int B, int K) { // write your code in C++14 (g++ 6.2.0) int a = A%K != 0 ? A/K : A/K -1; int b = B/K; return b-a; }

2021. 8. 21.

알고리즘/Codility

요약 벡터 A를 input받아 벡터 A가 1부터 시작하여 1씩 증가하는 등차수열을 이루고 있다면 1반환 아니라면 0반환을 하는 문제입니다. 아이디어 4_3문제랑 비슷한데 원소가 등차수열을 이루면 1반환 아닐 경우 0반환이라는 점에서 고려할 점이 많이 없어보이네요. 1. 정렬 후 앞 원소부터 비교를 해나가기 시작하면 됩니다. 코드 #include int solution(vector &A) { // write your code in C++14 (g++ 6.2.0) int sol = 1; sort(A.begin(), A.end()); for (auto element : A) { if (element == sol) sol++; else return 0; } return 1; } 결과는 이전문제를 푸셨다면 어렵지..

2021. 8. 21.

알고리즘/Codility

요약 문제의 타이틀 그대로 잃어버린 정수를 찾는 문제입니다. 정수 원자들이 있는 벡터 A를 input받아서 등차수열을 이루는 도중 빠진 정수를 찾거나 모두 등차수열을 이루게 된다면 원자와 중복되지 않는 가장 작은 양의 정수를 output하는 문제입니다. 문제에서 예시로 나와 있는 부분입니다. 원소의 정수 중복이 포함 된다는 점에서 등차수열이라는 단어가 안맞을 수 있지만 이해를 위해 1씩 증가하는 등차수열으로 보겠습니다. A = [1,3,6,4,1,2] 일경우에는 1 1 2 3 4 6으로 5가빠져서 5를 반환해야합니다. A = [1,2,3]인 경우 1 2 3을 이루므로 가장 작은 양의 정수 4를 반환합니다 A = [-1,-3]인경우 모두 음의 정수이기때문에 가장 작은 양의 정수 1을 반환합니다. 아이디어 ..

2021. 8. 21.

알고리즘/Codility

요약 배열의 크기를 나타내는 정수 N과 배열의 원소를 바꿀 벡터 A를 입력으로 주어짐 0으로 초기화 되어 있는 N크기의 벡터를 벡터 A에 있는 숫자번째를 1씩 증가시키고 N+1일때는 N크기의 벡터중 가장 큰 수로 모두 초기화를 시켜야 함 아이디어 1. N크기의 벡터를 만든 후 A벡터를 돌며 문제의 조건대로 원소들을 증가시킨다. 2. 이때 N+1을 만났을때 바로 모든 원소들을 초기화 시키면 시간복잡도가 O(N*M)이 될 수 있음 3. 모든 원소를 초기화시키지 않고 개별 원소들을 방문마다 초기화를 시키고 마지막에 초기화 되지 않은 원소들만 다시 초기화 하면됨 코드 vector solution(int N, vector &A) { // write your code in C++14 (g++ 6.2.0) vecto..

2021. 8. 21.

알고리즘/Codility

요약 개구리가 강 건너편으로 이동을 하려하는데 이동해야하는 거리는 X이고 낙엽이 떨어지는 곳을 나타낸 벡터 A이다. 벡터 A에는 1초마다 낙엽이 떨어지는 곳을 나타낸다. X까지 낙엽이 모두 있어야 개구리가 건널 수 있다. X와 벡터 A와 정수 X를 input으로 받아서 몇초만에 목표지점에 도착하는지 정수로 output해야한다. 도달할 수 없는 경우 -1 예를 들어 X = 5 A[0] = 1 개구리 -> oxxxx 강건너편 A[1] = 3 oxoxx A[2] = 1 oxoxx A[3] = 4 oxoox A[4] = 2 oooox A[5] = 3 oooox A[6] = 5 ooooo A[7] = 4 ooooo 라고하면 6초만에 강 건너편으로 도달 할 수 있게 된다. 아이디어 A벡터에서 다른 공간으로 낙엽이 ..

2021. 8. 20.