게으른개발너D

✨ 최단 경로 알고리즘 그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘 DFS, BFS도 최단 경로 알고리즘으로 사용할 수 있다. 대표적인 최단 경로 알고리즘 BFS 다익스트라 (Dijkstra) 벨만-포드 (Bellman-Ford's) 플로이드 와샬 (Floyd Warchall) 목적에 따라 알고리즘을 선택할 수 있다. BFS, DFS 그래프의 간선 가중치가 모두 같을 때 적합하다. 예를들어, 아래와 같이 2차원 배열(지도) 입력이 주어진 상태로 최단거리를 찾아야 한다면 BFS, DFS로 푸는 경우가 많다. 이 경우 배열의 한 칸이 정점이 된다. 그리고 위, 아래, 오른쪽, 왼쪽이 간선이 된다. 간선의 가중치는 공평하게 1이 된다. 만약 간선에 가중치가 있다면? Dijkstra 그래프의..

https://school.programmers.co.kr/learn/courses/30/lessons/68644?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Question 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers의 길이는 2 이상 100 이하입니다. numbers의 모든 수는 0 이상 100 이하입니다. 입출력 예 nu..

✨ 순열과 조합 순열과 조합은 코딩테스트에서 자주 나오지만 자바스크립트에서 제공해주는 built-in 함수가 없기때문에 직접 구현해야한다. 성능이나 콜 스택 위험으로 인해 스택으로 구현하는 것이 좋지만, 순열과 조합 자체가 시간복잡도가 굉장히 크기때문에 n이 크게 나오는 경우가 많지 않다. 따라서 재귀로 외우는 것이 직관적으로 편하다. 1. 순열 시간복잡도 O(n!) function permutations(arr, n) { // 1개만 뽑는다면 그대로 순열을 반환한다. 탈출 조건으로도 사용된다. if (n === 1) return arr.map((v) => [v]); let result = []; arr.forEach((fixed, idx, arr) => { // 현재 index를 제외한 요소를 추출한다..

✨ 트리 순회 트리 순회는 트리 자료구조에서 각 노드를 한 번씩 탐색하는 알고리즘이다. 트리 순회는 여러 방법이 있지만 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)는 재귀를 이용할 수 있다. 모든 순회는 루트 노드부터 시작하며, 어떤 노드를 먼저 방문하는지가 달라진다. 1. 전위 순회 (Preorder) 먼저 노드를 방문한 후 왼쪽 서브 트리를 전위 순회한 다음에 오른쪽 서브 트리를 전위 순회하는 방식이다. 아래와 같은 이진 트리가 있다고 가정해 보자. 1을 방문한 후, 1의 왼쪽 서브 트리로 이동한다. 2를 방문한 후, 2의 왼쪽 서브 트리로 이동한다. 4를 방문한 후, 왼쪽과 오른쪽 서브 트리가 없기 때문에 다시 올라가서 2의 오른쪽 서브 트리로 이동한다...

✨ 재귀함수 재귀함수는 자기 자신을 호출하는 함수이다. 자기 자신을 호출하는 것을 재귀 호출(Recursion call)이라고 한다. 함수 호출은 Call stack에 쌓이기 때문에 스택 자료구조와 유사하게 동작한다. 함수형 프로그래밍에선 루프 구현을 재귀로 구현하는 경우가 많다. 잘못 작성하면 무한 루프에 빠질 수 있다. Javascript에서 재귀함수 Call stack 제한이 있다. 자바스크립트 엔진마다 제한 수는 다르다. 크롬의 경우 약 1만개이다. 재귀함수 성능 개선을 위한 꼬리 재귀(Tail recursion)가 제공되지 않는다. 성능이 좋지 않다. 재귀로 구현해야 편한 알고리즘 Union-Find DFS Backtracking 불편함을 무시한다면 더 빠른 성능으로 작성할 수 있지만 코딩 테스..

https://programmers.co.kr/learn/courses/30/lessons/12921?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Question 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한조건 n은 2 이상 1000000 이하의 자연수입니다. 입출력 예 n return 10 4 5 3 Solution 1부터 n까지의 숫자 중 소수를 모두 찾아야할 경우엔 에..

✨ 소수 1 또는 자기 자신만을 약수로 가지는 수를 의미 즉, 1과 자기 자신 외에는 그 어떤 값으로도 나눠질 수 없다. ✨ 소수 구하는 방법 1. 가장 직관적인 방법 2부터 N-1까지 루프를 돌며 나눠보기 시간 복잡도 O(n) // O(n) function isPrime(num) { for(let i = 2; i < num; i++) { if (num % i === 0) { return false; } } return true; } 2. 효율성 개선하기 위의 알고리즘을 좀 더 효율적으로 개선해 보자. 그 어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 점을 이용. 시간 복잡도 O(sqrt(n)) // O(sqrt(n)) function isPrime(num) { for(let i = 2; i * i

https://school.programmers.co.kr/learn/courses/30/lessons/42883# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Question 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제..