tagalgorithm
Codility Lesson 5 — PassingCarsTask description 연이은 차량 배열 A가 주어지고 이 차량(?)들은 값을 0s/1s을 가짐. 0은 동쪽으로 이동하는 차량, 1은 서쪽으로 이동하는 차량 교차해 지나간 차량의 쌍의 수 찾기 (단 쌍을 이루는 첫번째 차량은 0 이어야 함) How I did solve 글로 풀어서 작성이 안될거 같아서 그림으로 대체 … 결국 반대 방향으로 가는 차량이 나타났을 때, 동일한 방향으로 가는 차량의 수만큼과 교차하므로 각 차량을 순회하면서 교차한 수 = 교차한 수 + 같은 방향으로 가는 차량 수 를 누산하면 된다. 단,
Codility Lesson 4 — MissingIntegerTask description 주어진 수열에서 누락된 가장 작은 양의 정수 찾기 주어진 배열은 중복이 가능하고 음수도 포함되어 있다. How I did solve 전에는 양의 정수, 고유값들로 주어진 순열 중 누락분을 구하는 문제였어서 합을 통해 풀었으나, 이번에는 일단 중복이 발생되어 있고 음수도 끼어 있어서 hashmap을 이용해서 풀어보기로 했고 의외로 금방 풀어냈음. Solved Code function solution(A) { const hashMap = {}; A = A.sort( (a,b) => a -
Codility Lesson 4 — MaxCountersTask description 정수 N과 1 ~ N + 1까지의 값을 원소로 가지는 배열 A가 주어짐 배열 A를 순회하면서 해당 값들이 나오는 수를 카운트 배열 A를 순회하는 중에 발견된 값이 N + 1일 경우 모든 값에 대한 카운트를 가장 높은 카운트 수로 일괄 변경 즉, N = 5 A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4 이러한 N과 A 배열이 주어졌다면, A[2]까지 순회 했을 때 3은 1번, 4는 2번 카운트 되었으므로 (0, 0, 1, 2,
Codility Lesson 4 — FrogRiverOneTask description 시간별 개구리의 위치 정보를 담고있는 배열 A(배열 인덱스가 초단위 시간, 값이 위치), 강의 끝 위치 X가 주어졌을 때 모든 위치를 거치게되는 가장 빠른 시간 찾기 모든 위치를 거치지 못한다면 -1을 반환 How I did solve 각 위치당 시간 정보를 가진 새로운 배열이 필요 각 위치를 배열의 index로 사용 X 길이 만큼의 배열 생성 각 위치에 시간 기록 이미 기록된 위치에는 재작성하지 않아야 함 배열에 모든 요소가 값이 있다면 가장 높은 값을 반환 그렇지 않으면 -1 반환
Codility Lesson — PermCheckTask description 주어진 배열이 순열이면 1 그렇지 않으면 0을 반환 How I did solve 순열이라면, 1 + (N), 2 + (N-1), 3 + (N-2)이 모두 같은 값을 가질 것으로 가정 주어진 배열을 오름차순으로 정렬 후, 순차적으로 더한 값을 비교해가면 누락된 숫자가 있는 경우 해당 합에서 차이가 발생할 것이므로 O(n/2)로 해결 가능할 것으로 추측 Solved Code function solution(A) { const arr = A.sort( (a, b) => a - b )
Codility Lesson 3 — tapeEquilibriumTask description |(A[0] + … + A[P-1]) - (A[P] + … + A[N-1])| 최소값 찾기 How I did solve 배열의 전체 합 sumOfTatal을 구함 A의 요소를 탐색해가며 탐색한 요소들의 합을 구하면 A[0] + … + A[P-1] 탐색한 요소들의 합을 전체 합에서 빼면 A[P] + … + A[N−1] 둘의 차이 중 최소값을 반환 Solved Code function solution(A) { const sumOfTotal = A.reduce( (acc, entry)
Codility Lesson 3 — PermMissingElmTask description 주어진 순열에서 누락된 요소 찾기 How I did solve 1 ~ (N + 1) 까지의 순열이 있다고 할 때, 단 1개의 요소만이 누락되어 있다면 누락되지 않은 순열의 합과 현재 순열의 합의 차이가 곧 누락된 요소 1 ~ N 까지의 합 (1 + N) * N / 2 1 ~ (N+1)까지의 합 (2 + N) * (N + 1) / 2 Solved Code function solution(A) { let sumNonMissing = (A.length + 2) * (A.length +
Codility Lesson 3 — FrogJumpTask description 위치 X에서 Y까지 최소 점프 횟수를 계산합니다. How I did solve position X에서 position Y로 이동하는데 한 번에 D 만큼 이동한다면, 총 이동거리 (Y - X) = n * 1회 이동거리(D) 소수점은 1회 이동을 해야 하므로 올림 처리 Solved Code function solution(X, Y, D) { return Math.ceil((Y - X) / D) } Retrospective 이 문제는 고민할 필요도 없이 바로 풀이가 도출 됨… 혹시 다른
알고리즘 연습을 다시 시작했다.최근 Codility를 통해 알고리즘 문제를 다시 풀어보기 시작했다. (알고리즘을 다시 들여다보게 된 계기는 쉿…) Codility 문제를 풀어보다보니 내가 그 동안 얼마나 레퍼런스 문서에 의존해 왔는지를 뼈저리게 체감하고 생각하는 계기가 된 듯하다. Array에 어떤 메서드가 있었는지, 어떻게 사용했었는지 기억을 계속 더듬어야만 했고 정규 표현식의 특수 문자를 (특히 '?' 라던가… '?=' 같은 것들) 어떻게 작성했었었는지 문서를 보지 않고 작성하려니 여간 어려운게 아니더라. 물론 문서를 참고해서 문제를 해결하는게 잘못된 것도
Codility Lesson 2 — CyclicRotationTask description 주어진 수만큼 배열을 오른쪽으로 이동 How I did solve 주어진 값이 A = [3, 8, 9, 7, 6] , K = 3 일 경우 결과는 [9, 7, 6, 3, 8] 즉, 3만큼 오른쪽으로 이동시킬 경우 뒤에서 3개 요소를 앞으로, 나머지를 그 뒤에 나열시키는 새로운 배열 반환. 이를 위해서는 array.length - 3부터 마지막 요소까지를 slice ,나머지를 slice slice된 배열을 접합 K가 배열 길이를 넘어설 경우 n회의 cycle을 돌아 제자리가 되므로 K를