목록전체 글 (146)
게으른개발너D
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/pr4Fv/btspNgiQ2x5/VMVZWMmfVWK6Zkp7LdMag1/img.png)
https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/di7gxQ/btspPbX2zyi/sppyZBt275YjReZEqsNtA0/img.jpg)
해당 그래프를 최소한의 비용으로 모든 정점을 연결하려면? 필요한 간선 외에는 모두 제거하면 된다. 이러한 알고리즘을 최소 신장 트리라고 한다. ✨ 최소 신장 트리 (Minimum Spanning Tree) 신장 트리 (Spanning tree)란 그래프 내에 모든 정점을 포함하는 최소 연결 부분 그래프이다. 여기서 최소 신장 트리 (MST)는 다음과 같은 조건을 만족한다. 최소한의 간선으로 모든 정점이 연결되어야 한다. 모든 신장 트리 중 가중치의 값이 최소여야 한다. Cycle이 발생해서는 안된다. 최소 신장 트리를 위한 알고리즘은 대표적으로 두 가지가 있다. 크루스칼 (Kruskal) 프림 (Prim) 미리 알아두면 좋은 크루스칼 알고리즘 그리디 개념을 이용하여 구현할 수 있다. 먼저 모든 그래프를 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/XC5nG/btspgoqcN4r/KyLyHWm6QCWKr8E5DIA6ck/img.png)
https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N 개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N 까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/c85fxX/btspOC2ammR/ySOVJBZKnjnor34mKywcKK/img.jpg)
✨ 최단 경로 알고리즘 그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘 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..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/njbSf/btspVpuc6Nn/2QMFp06ejQpvN7Gykbkds0/img.jpg)
✨ 순열과 조합 순열과 조합은 코딩테스트에서 자주 나오지만 자바스크립트에서 제공해주는 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를 제외한 요소를 추출한다..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/3jt6X/btspTKZHrAb/XlBQ4WZ1K6t0u3nHAzKdPK/img.jpg)
✨ 트리 순회 트리 순회는 트리 자료구조에서 각 노드를 한 번씩 탐색하는 알고리즘이다. 트리 순회는 여러 방법이 있지만 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)는 재귀를 이용할 수 있다. 모든 순회는 루트 노드부터 시작하며, 어떤 노드를 먼저 방문하는지가 달라진다. 1. 전위 순회 (Preorder) 먼저 노드를 방문한 후 왼쪽 서브 트리를 전위 순회한 다음에 오른쪽 서브 트리를 전위 순회하는 방식이다. 아래와 같은 이진 트리가 있다고 가정해 보자. 1을 방문한 후, 1의 왼쪽 서브 트리로 이동한다. 2를 방문한 후, 2의 왼쪽 서브 트리로 이동한다. 4를 방문한 후, 왼쪽과 오른쪽 서브 트리가 없기 때문에 다시 올라가서 2의 오른쪽 서브 트리로 이동한다...
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/TXrbb/btspUnwnGex/kRo2TNWMhL3q3xIB6sHAK0/img.jpg)
✨ 재귀함수 재귀함수는 자기 자신을 호출하는 함수이다. 자기 자신을 호출하는 것을 재귀 호출(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까지의 숫자 중 소수를 모두 찾아야할 경우엔 에..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bSgUzi/btspMjoxug6/mAecGeiwzNWvggP5DLwSJ1/img.jpg)
✨ 소수 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