Codility – TapeEquilibrium

문제 https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ 정답 풀이 구간합 알고리즘을 사용할 수 있는지 확인하는 문제입니다. 구간합 알고리즘은 각 시점의 구간합을 매번 계산하는 것이 아니라, 특정 배열에 해당 구간의 합이 어떻게 되는지 미리 저장 합니다. 따라서 O(N^2)에서 O(N)으로 시간복잡도가 개선됩니다. 처음 for문에서 구간합을 미리 배열에 저장 합니다. max_difference를 int 최대 값으로 지정 합니다. 두번 째 for문이 len(A) – 1인 이유는 […]

Codility – PermMissingElem

문제 https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/ 정답 풀이 예외처리를 올바르게 할 수 있는지 파악하는 문제입니다. 배열을 순서대로 맞춰주기 위해서 정렬을 합니다. 정렬을 하였기 때문에 빠진 숫자가 아니라면, 배열의 index 위치에 (index + 1)가 있어야 합니다. 이 때 마지막 숫자까지 배열에 존재할 경우 문제의 [1..(N + 1)] 범위에서 (N + 1)이 배열에서 빠진 것이기 때문에 해당 값에 해당하는 (len(A) + […]

Codility – FrogJmp

문제 https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/ 정답 풀이 예외처리를 올바르게 할 수 있는지 파악하는 문제입니다. 총 거리(Y – X)를 개구리의 점프 거리(D)로 나눈 후, 나머지가 있을 경우에 해당 위치(Y)에 아직 못 미친 상태이기 때문에 개구리가 한번 더 점프 하도록 count + 1을 해줍니다. 팁 해당 문제는 예외 상황이 많지 않으나, 동일한 문제에서 예외 상황이 많아질 경우 까다로워 질 수 […]

Codility – OddOccurrencesInArray

문제 https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ 정답 풀이 XOR 특성을 알고 있는지 묻는 문제입니다. XOR 연산은 이진수의 동일한 자리 값이 같을 경우 0이 되고, 다를 경우 1이 됩니다. 동일한 수는 이진수가 같기 때문에, XOR 연산을 하여 0을 만들 수 있습니다. 이 특성을 중복 제거에 활용합니다. A배열의 모든 값을 XOR 연산 하면 중복되는 값은 0으로 제거되고 하나의 값만 남게 됩니다. […]

Codility – CyclicRotation

문제 https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/ 정답 풀이 해당 언어에서 제공하는 기본 함수를 활용할 수 있는지를 물어보는 문제입니다. 배열의 끝에 값을 빼서 맨 앞으로 넣는 형태입니다. 팁 Rotation을 한번도 진행하지 않았을 때 같이, 특수한 test case를 확인해 보는 것을 습관화 하면 좋겠습니다.

Codility – BinaryGap

문제 https://app.codility.com/programmers/lessons/1-iterations/binary_gap/ 정답 풀이 예외처리를 올바르게 할 수 있는지 파악하는 문제입니다. 처음 1이 나온 순간부터 다음 1이 나온 순간까지 counter에 값을 누적 시킵니다. 만약 1이 한번도 나오지 않은 경우라면 0이 나와도 개수를 세지 않습니다. 다음 1이 나왔을 때, 기존 max_gap보다 크다면 해당 값을 저장 합니다. 이후, 다시 0의 개수를 세기 위해 counter를 초기화 합니다. counter를 […]