Computer Science (59) 썸네일형 리스트형 소수 구하기 : isPrime, prime number, sqrt 1. 문제 정수 n을 인자로 받아와서 그것이 소수인지 판별하는 함수를 만든다. 소수의 특성 소수는 1과 자기 자신으로만 나누어지는 수이다. 1은 소수가 아니다. 2. 풀이 1. 정수 n을 1을 제외한 모든 자연수에 대하여 나눠가며 나누어 떨어지는 수가 있는지 판별한다. 2. 짝수와 제곱근을 이용해 자료의 크기를 줄인다. 상세 설명 정수 n을 자연수를 1씩 증가시켜가며 하나씩 나눠볼텐데, 굳이 n까지 모든 수를 통해 나누어볼 필요가 없다. 이것은 2가 소수이고 짝수는 모두 2로 나누어 떨어지기 때문에 짝수를 제외시킬 수 있고, 모든 수는 제곱근의 제곱으로 나타낼 수 있으므로 굳이 제곱근 이상의 수로 나누어볼 필요가 없기 때문이다. 예를 들어서 16의 경우 sqrt(16) = 4가 된다. 즉 16 = sqr.. Prm 14 : rotatedArraySearch / binarySearch, 경우의 수 rotatedArraySearch 문제 부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다. 부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다. 입력 인자 1 : rotated number 타입을 요소로 갖는 배열 rotated[i]는 정수 인자 2 : target number 타입의 정수 출력 number 타입을 리턴해야 합니다. 주의사항 rotated에 중복된 요소는 없습니다. target이 없는 경우, -1을 리턴해야 합니다. 입출력 예시 let out.. insertionSort / 삽입정렬 풀이 삽입정렬은 카드놀이에서 새로운 카드를 받았을 때, 원래 갖고 있던 정렬된 배열에 새로운 카드를 정렬시켜 넣는 것에 비유할 수 있다. 기존 정렬된 배열의 맨 끝요소와 새로운 요소를 비교하는 방식으로 정렬을 진행한다. 예를 들어 [2, 3, 5, 7]의 배열이 있고, 추가로 [1]을 넣어준다면 7과 1을 비교해서 1이 더 작으므로 7의 index 위치에 1을 삽입하고, 7은 한칸 뒤로 미는 방식이다. 새로 넣어준 1이 정렬된 배열에서 제자리를 찾아갈 때까지 이 과정을 반복한다. 다만, 받아오는 배열은 전체가 정렬되지 않은 배열로 간주하고, 맨 첫번째 요소만 정렬된 것으로 생각하여 순차적으로 정렬과정을 진행한다. 알고리즘 구현 알고리즘 구현은 정렬되지 않은 부분을 외부 루프로, 정렬된 부분을 내부 루프로.. Prm 11 : powerSet powerSet 문제 하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다. 입력 인자 1 : str string 타입의 공백이 없는 알파벳 소문자 문자열 출력 배열(arr)을 리턴해야 합니다. arr[i]는 각 부분집합의 원소로 구성된 문자열 주의사항 arr[i]는 각 부분집합을 구성하는 원소를 연결한 문자열입니다. arr[i]는 알파벳 순서로 정렬되어야 합니다. 집합은 중복된 원소를 허용하지 않습니다. 부분집합은 빈 문자열을 포함합니다. arr은 사전식 순서(lexical order)로 정렬되어야 합니다. 입출력 예시 let output1 = powerSet('abc'); console.log(output1); // ['', 'a', 'ab', 'a.. Prm 10 : BinarySearch binarySearch 문제 오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다. 입력 인자 1 : arr number 타입을 요소로 갖는 배열 rotated[i]는 정수 인자 2 : target number 타입의 정수 출력 number 타입을 리턴해야 합니다. 주의사항 이진탐색 알고리즘(O(logN))을 사용해야 합니다. 단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다. target이 없는 경우, -1을 리턴해야 합니다. 입출력 예시 let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2); console.log(output); // --> 2 output = binarySearch.. Prm 9 : power / recursion power 문제 두 수를 입력받아 거듭제곱을 리턴해야 합니다. 입력 인자 1: base number 타입의 자연수 (base >= 2) 인자 2: exponent number 타입의 정수 (exponent >= 0) 출력 number 타입을 리턴해야 합니다. 실제 계산 결과를 1000000009로 나눈 나머지를 리턴해야 합니다. 주의사항 Math.pow, 거듭제곱 연산자 사용은 금지됩니다. 시간복잡도 O(logN)을 만족해야 합니다. 나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 1000000009로 나누려고 해서는 안 됩니다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 .. Prm 8 : LargestProductOfThree / sort largestProductOfThree 문제 정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 합니다. 입력 인자 1 : arr number 타입을 요소로 갖는 임의의 배열 출력 number 타입을 리턴해야 합니다. 주의사항 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다. 배열의 요소는 음수와 0을 포함하는 정수입니다. 배열의 길이는 3 이상입니다. 입출력 예시 let output = largestProductOfThree([2, 1, 3, 7]); console.log(output); // --> 42 (= 2 * 3 * 7) output = largestProductOfThree([-1, 2, -5, 7]); console.log(output); // -.. Prm 7 : tree DFS / recursion tree를 구성하는 Node 객체를 입력 받고, 해당 노드를 시작으로 하여 DFS(Depth First Search)를 하는 문제이다. 탐색되는 순서대로 노드의 값을 저장한 배열을 리턴하면 된다. 입력 인자 1 : node 'value', 'children' 속성을 갖는 객체 (Node) 'node.value'는 number 타입 'node.children'은 Node를 요소로 갖는 배열 출력 배열을 리턴해야 합니다. 기본 코드 나의 풀이 Ref. // 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다. // membership check(중복 확인)를 따로 하지 않습니다. 이전 1 ··· 3 4 5 6 7 8 다음
