목록알고리즘_JS/인프런 JS알고리즘 (17)

프론트엔드 개발자의 기록 공간

[DP] 최대 부분 증가 수열

🚩 최대 부분 증가 수열 📖 문제 설명 : N개의 자연수의 수열이 주어질 때, 가장 길게 증가하는 원소의 길이를 찾아라. ex) 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하는 원소들은 2, 5, 6, 7, 12이다. 따라서 길이는 5이다. 💡 i 번째 원소에서 0 ~ i-1 번째 원소를 탐색하면서 자기보다 작은 원소들의 개수를 파악한다. // 최대 부분 증가수열 (DP) function solution(arr, n) { let answer = 0 let dp = Array.from(Array(n), () => 0) dp[0] = 1 for (let i = 1; i = 0; j--) { if (a..
알고리즘_JS/인프런 JS알고리즘 2022. 4. 7. 22:16
[DP] 계단 오르기

🚩 계단 오르기 📖 문제 설명 : 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 4계단을 오른다면 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 총 5가지이다. N 계단일 때 올라갈 수 있는 방법의 수는?? 💡 피보나치 수열을 활용한다. // 계단오르기 DP function solution(n) { let answer = 0 let dp = Array.from(Array(n + 1)).fill(0) dp[1] = 1 // 첫 번째 계단 경우의 수 dp[2] = 2 // 두 번째 계단 경우의 수 for (let i = 3; i
알고리즘_JS/인프런 JS알고리즘 2022. 4. 6. 18:13
[BFS, DFS] 섬나라 아일랜드

🚩 섬나라 아일랜드 BFS, DFS 풀이 📖 문제 설명 : 0과 1로 이루어진 격자판 정보가 주어진다. 이웃한 1의 집합이 곧 하나의 섬이 된다. 몇 개의 섬으로 이루어져 있는지 구해라. (상하좌우 대각선 이동 가능) 💡 모든 격자판을 순회하면서 1일 경우 탐색을 하고, 상하좌우 대각선으로 이동하면서 0으로 값을 변경 하나의 탐색이 끝나면 하나의 섬을 탐색한 것이다. BFS // 섬나라 아일랜드(BFS) // 상, 하, 좌, 우, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 const dx = [-1, 1, 0, 0, -1, -1, 1, 1] const dy = [0, 0, -1, 1, -1, 1, -1, 1] function BFS(i, j, arr) { let queue = [] queue.pus..
알고리즘_JS/인프런 JS알고리즘 2022. 4. 5. 15:11
[BFS] 송아지 찾기

🚩 송아지 찾기 📖 문제 설명 : 현수가 -1, +1, +5칸을 움직일 수 있다. 최소 몇 번의 이동으로 송아지가 위치한 곳 까지 갈 수 있는지 구해라. 💡 +1을 간 경우에서 -1을 수행할 경우 똑같은 위치를 반복해서 탐색하는 경우가 있다. 따라서 방문 표시를 위한 체크 배열을 이용한다. // 송아지 찾기 (BFS: 상태트리탐색) function solution(S, E) { let answer = 1 // 연산 편의를 위한 1부터 시작 let queue = [S] // 처음 나의 위치 let visited = [] // 중복 숫자 처리를 위한 방문 처리 배열 while (true) { let tmp = [] let n = queue.length // queue.shift 할 경우 길이가 반복문 수행시..
알고리즘_JS/인프런 JS알고리즘 2022. 4. 4. 01:20
[DFS] 경로 탐색

🚩 경로 탐색 (인접행렬, 인접리스트) 📖 문제 설명 : 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력 (인접 행렬, 인접 리스트) 인접 행렬 방식 // 경로 탐색(인접행렬) let path = [] // 탐색한 노드 경로 function DFS(n, graph, visited, v, arr) { if (v === n) { // 누적 경로 + 현재 경로 path.push([...arr, v]) return } visited[v] = 1 // 방문 처리 // 인접 행렬을 순회하면서 방문하지 않은 노드들의 경로를 재귀적으로 탐색 for (let j = 1; j Array(n + 1).fill(0)) let visited = Array.from(Array(n + 1), (..
알고리즘_JS/인프런 JS알고리즘 2022. 4. 4. 00:46
[재귀함수, 완전탐색] 조합 구하기

🚩 조합 구하기 📖 문제 설명 : 1부터 N 까지의 자연수 중 M 개를 뽑는 방법의 수 출력(조합) 순열과 비슷하지만 순서가 상관 없기 때문에 [1,4] 뽑혔다면 [4,1]은 뽑는것이 불가능하다. 💡 뽑은 조합 중에 가장 마지막 카드의 +1부터 N까지 재귀 함수 이용 let combination = [] function recursion(n, r, arr) { // 배열 길이가 r 보다 클 때 if (arr.length > r) { return } // arr 마지막 배열 +1 부터 반복문을 실행해야지 중복값이 안들어감 // 처음 arr 배열은 undefined이기 때문에 || 1을 통해 1로 초기화 for (let j = arr[arr.length - 1] + 1 || 1; j Array(r + 1)...
알고리즘_JS/인프런 JS알고리즘 2022. 4. 3. 01:36
Prev 1 2 3 Next