inflearn78 [ 자바스크립트(JavaScript) ] section10 - 1 - 계단 오르기(DP) 📍 section10 - 1 - 계단 오르기(DP) 이번 섹션은 동적 계획 프로그래밍인(DP)에 대해서 배운다. (넷플릭스 DP 꿀잼 😁) DP 문제는 직관적으로 분석하기 어려운데, 이 감을 키우려면 선생님께서는 역시 양치기 즉, 많은 문제를 풀어봐야 한다고 하셨다. DP문제들의 특징을 살펴보자. DP는 큰 문제를 한 번에 풀기보다는 직관적으로 알 수 있는 단위로 잘게 쪼갠다. 작은 단계부터 답을 dp에 저장하고, 범위를 점차 넓혀간다. 이때, 앞에서 사용한 값을 그대로 사용한다. 직관적으로 알 수 있는 값은 dp에 저장하는데 보통은 dp[1]~dp[2] 정도이고 많으면 dp[0]~dp[3]정도까지 저장한다. 작은 단계부터 경우의 수를 한번 세본다. (이후에는 어떻게 활용할지 고민하기!) 이전 단계와의 .. 2021. 10. 13. [ 자바스크립트(JavaScript) ] section09 - 6 - 섬나라아일랜드(DFS, BFS) 📍 section09 - 6 - 섬나라 아일랜드(BFS, DFS) 문제: N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 이 문제는 DFS 와 BFS탐색으로 모두 풀 수 있는 문제다. 이 방법을 이용하면 백준4963 - 섬의 개수도 한번 풀어보자! 먼저, DFS로 푸는 방법을 알아보자. visited 배열을 선언하지 않고 현재 좌표를 0으로 만든 다음에 대각선 좌표의 값이 1인 곳만 탐색한다.(이때, 재귀적으로 dfs 함수를 호출한다.) board를 돌면서 현재 좌표와 대각선 좌표까지 0이면 더 이상 탐색할 수 없으므로 다음 좌표로 넘어간다... 2021. 10. 12. [ 자바스크립트(JavaScript) ] section09 - 5 - 송아지 찾기(BFS: 상태트리탐색) 📍 section09 - 5 - 송아지 찾기(BFS: 상태트리탐색) 문제: 현수의 위치와 송아지의 위치가 수직선 상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. BFS를 사용하는 문제인데, 왜 BFS를 사용하는지 강의를 통해 배울 수 있었다. 결론적으로 상태 트리, 레벨 트리를 살펴보면서 깊이 우선 탐색인 DFS처럼 한 level만 끝까지 파고들며 target과 동일할 때까지 탐색하는 것이 아니라, 한 레벨에서 이동할 수 있는 좌표를 살펴보고 targ.. 2021. 10. 12. [ 자바스크립트(JavaScript) ] section09 - 4 - 이진트리 넓이우선탐색(BFS) 📍 section09 - 4 - 이진트리 넓이우선탐색(BFS) 다음과 같이 생긴 이진트리에서 BFS로 1 2 3 4 5 6 7 출력이 나와야 한다. visited 방문 배열을 선언할 필요 없이 nv>7 일 때는 더 이상 queue에 push 하지 않아도 되므로 break한다. queue에 더 이상 값이 없을 때까지 shift()한다. console.log(solution()); function solution(){ let queue = []; let answer = ""; queue.push(1); while (queue.length){ let v = queue.shift(); answer+=v+" "; for (let nv of [v*2, v*2+1]){ if (nv > 7) break; queue.p.. 2021. 10. 7. [ 자바스크립트(JavaScript) ] section09 - 3 - 경로 탐색(인접리스트) 📍 section09 - 3 - 경로 탐색(인접리스트) 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하는 문제다. 예를 들어 1번 정점에서 5번 정점으로 가는 가지 수는 다음과 같다. 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 이전과 동일한 문제지만 이번에는 인접 리스트를 활용해서 푸는 문제다. 만약에 그래프를 이용한 문제에서 정점의 개수가 10,000개 이상이라면 인접리스트를 사용하자.(인접 행렬은 정점의 개수만큼 반복문을 돌아야 하기 때문에 비효율적이다.) 이 문제도 마찬가지로 DFS를 이용해서 풀 수 있다. 경로의 가짓수만 출력하는 것이 아니라 올바르게 이동했는지 알기 위해 path 변수를 추가했다.. 2021. 10. 6. 이전 1 2 3 4 5 ··· 16 다음
