코테
[알고리즘] 소수 판별식 (에라토스테네스의 체)
1. num 사이의 숫자를 모두 나눠서 확인하는 방법 function isPrime(num) { for(let i = 2; num > i; i++) { if(num % i === 0) { return false; } } return num > 1; } 2. num 제곱근 까지만 확인 하는 방법 function isPrime(num) { let sqrt = parseInt(Math.sqrt(num)); // num에 제곱근 후 소수점 버림 if (num === 1) { return false; } if (num === 2) { return true; } if (num % 2 === 0) { return false; } // 1, 2에 대한 경우의 수와 2의 배수는 미리 걸러냄 for (let i = 3; ..
![[알고리즘] Algorithm with Math / 정규표현식](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdYI5s9%2Fbtq97N48BkN%2FAlwK2g8MIk4ueabeCRHKzk%2Fimg.png)
[알고리즘] Algorithm with Math / 정규표현식
컴퓨터가 단순하게 연산하기 때문에, 기본적인 컴퓨터 과학과 수학은 통하는 부분이 있습니다. 그러므로 수학을 학습하는 것은 프로그래밍의 기본을 탄탄히 하는 일입니다. 그러므로 수학은 프로그래밍에 많은 도움이 됩니다. 알고리즘 파트에서 다루는 수학은 중학교 수준의 수학입니다. 알고리즘 테스트(코딩 테스트)를 해결하는데 필요한 최소한의 수학을 다룹니다. 프로그래밍을 위한 최소한의 수학이기 때문에 학습해야만 하는 내용입니다. 알고리즘 문제에서 자주 다루는 최소한의 수학만 익혀, 적재적소에 활용할 수 있는 능력을 기르는 것이 가장 큰 목표입니다. 최근 코딩 테스트에 등장하는 알고리즘 문제는 단순히 "너 이 알고리즘 알아?"라고 물어보지 않습니다. 요즘 출제되는 문제는 "특정 방법을 사용해서 풀어 볼래?"라고 물어..
![[알고리즘] Time Complexity / greedy Algorithm / implementation](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fdm0sjg%2Fbtq9Y5lf9ug%2FFwFge5LRqUgHwiORZSv4M0%2Fimg.png)
[알고리즘] Time Complexity / greedy Algorithm / implementation
알고리즘은 문제를 해결하는 최선의 선택입니다. 1. 문제를 이해하고 2. 전략을 세우고 (수도코드, 흐름의 그림, 페어에게 설명) 3. 이에 따라 코드 작성으로 문제 해결 개발자로서 만나게 될 대부분의 개발 태스크는 알고리즘 문제만큼 어렵지 않습니다. 그러나 새로운 문제에 봉착했을 때, 전략과 알고리즘을 구상하여 실제로 코드로 구현해 보는 경험은 매우 중요합니다. 많은 기업에서 주니어 개발자를 채용할 때에, 알고리즘 풀이를 통해 지원자의 역량을 가늠합니다. 알고리즘 풀이를 통해 지원자의 로직과 문제해결 방식을 확인하고, 이를 통해 개발자다운 사고방식을 보게 된다고 합니다. 1. Time Complexity 알고리즘 문제를 풀때 해결하는것도 가장 중요하지만 효율적인 알고리즘을 찾는 것 또한 중요합니다. 효..
Toy 문제 11
문제 하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다. 입력 인자 1 : str string 타입의 공백이 없는 알파벳 소문자 문자열 출력 배열(arr)을 리턴해야 합니다. arr[i]는 각 부분집합의 원소로 구성된 문자열 주의사항 arr[i]는 각 부분집합을 구성하는 원소를 연결한 문자열입니다. arr[i]는 알파벳 순서로 정렬되어야 합니다. 집합은 중복된 원소를 허용하지 않습니다. 부분집합은 빈 문자열을 포함합니다. arr은 사전식 순서(lexical order)로 정렬되어야 합니다. 입출력 예시 let output1 = powerSet('abc'); console.log(output1); // ['', 'a', 'ab', 'abc', 'ac'..
Toy 문제 10
문제 오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다. 입력 인자 1 : arr number 타입을 요소로 갖는 배열 arr[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([4, 5, 6, 9], 10..
Toy 문제 9
문제 두 수를 입력받아 거듭제곱을 리턴해야 합니다. number 타입을 리턴해야 합니다. 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 합니다. 주의사항 Math.pow, 거듭제곱 연산자 사용은 금지됩니다. 시간복잡도 O(logN)을 만족해야 합니다. 나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 됩니다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다. 입출력 예시 let output = power(3, 40); console.log(output); // --> 19334827 수도..
Toy 문제 8
문제 정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 합니다. 주의사항 입력으로 주어진 배열은 중첩되지 않은 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); // --> 35 (= -1 * -5 * 7) 수도코드(해석) 1. 배열을 입력받으면 순서에 따라 배열을 정렬 2. 앞에서부터 3번째 까지 곱하고, 뒤에서부터 ..
Toy 문제 7
문제 임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다. 입력 인자 1 : node 'value', 'children' 속성을 갖는 객체 (Node) 'node.value'는 number 타입 'node.children'은 Node를 요소로 갖는 배열 주의사항 생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다. 입출력 예시 let root = new Node(1); let rootChild1 = root.addChild(new Node(2)); let rootChild2 = root.addChild(..
Toy 문제 6 sudoku
문제 스도쿠는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐입니다. 퍼즐을 푸는 방법은 아홉 가로줄, 세로줄, 3X3 칸에 1에서 9까지의 숫자를 중복되지 않게 한 번씩만 넣으면 됩니다. 일부 칸이 비어있는 상태인 스도쿠 보드를 입력받아 스도쿠 퍼즐이 완성된 보드를 리턴해야 합니다 입출력 예시 let board = [ [0, 3, 0, 2, 6, 0, 7, 0, 1], [6, 8, 0, 0, 7, 0, 0, 9, 0], [1, 9, 0, 0, 0, 4, 5, 0, 0], [8, 2, 0, 1, 0, 0, 0, 4, 0], [0, 0, 4, 6, 0, 2, 9, 0, 0], [0, 5, 0, 0, 0, 3, 0, 2, 8], [0, 0, 9, 3, 0,..
Toy 문제 5
문제 세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다. 해석(수도코드) 입출력 예시 let output = tiling(2); console.log(output); // --> 2 output = tiling(4); console.log(output); // --> 5 2 x 4 보드에 타일을 놓는 방법은 5가지 각 타일을 a, b, c, d로 구분 2 | a b c d 1 | a b c d ------------ 2 | a a c c 1 | b b d d ------------ 2 | a b c c 1 | a b d d ------------ 2 | a a c d 1 | b b c d ------------..