본문 바로가기

inflearn78

[ 자바스크립트(JavaScript) ] section09 - 2 - 경로 탐색(인접행렬) 📍 section09 - 2 - 경로 탐색(인접행렬) 방향 그래프가 주어지면 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 이 문제는 DFS를 이용해서 풀 수 있다. 경로의 가짓수만 출력하는 것이 아니라 올바르게 이동했는지 알기 위해 path 변수를 추가했다. 2차원 배열의 graph를 선언하여 정점과 간선의 정보를 넣는다. visited 배열을 선언하여 이미 지나온 곳은 건너뛰고 진행한다. DFS의 종료 조건은 v가 n과 같을 때이다. 인접 행렬이므로 반복문으로 모든 정점을 탐색해야 한다. DFS 함수.. 2021. 10. 6.
[ 자바스크립트(JavaScript) ] section09 - 1 - 그래프와 인접행렬 📍 section09 - 1 - 그래프와 인접행렬 이번 섹션은 그래프와 탐색(DFS, BFS)에 대해서 배운다. 지금은 문제를 풀지 않고 그래프에 대해 간단하게 알아보는 시간을 가져보자. 그래프는 다음과 같이 이루어진다. Vertex: 정점, 노드 Edge: 노드와 노드를 연결하는 간선 graph: 2차원 배열에서는 index가 정점(vertex) 번호다. 그래프의 종류는 3가지가 있다. 입력이 주어질 때 graph별로 어떻게 입력하는지 코드로 나타냈다. (여기서는 인접 행렬로 표현함) 1. 무방향 그래프(unDirected Graph): 방향이 없는 그래프 즉, 양방향인 그래프다. 입력은 보통 [a, b] 형태로 주어지는데 여기서 graph[a][b]=1, graph[b][a]=1을 모두 수행한다. /.. 2021. 10. 6.
[ 자바스크립트(JavaScript) ] section08 - 15 - 수들의 조합 📍 section08 - 15 - 수들의 조합 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개인지 출력하는 문제다. 예를 들면, 5개의 숫자 arr=[2, 4, 5, 8, 12]로 주어지면 3를 뽑는 조합의 합이 6의 배수인 값은 [2, 4, 12] (18), [ 4, 8, 12 ] (24)로 총 2개가 있다. 이 문제를 풀기 위해선 n개의 정수를 뽑는 모든 경우의 수(조합)를 구하고, 조합의 합을 m으로 나눈 나머지가 0인 값을 찾으면 된다. 조합을 구현하는 방법은 다음을 참고하자. 내가 문제를 풀 때는 DFS함수에 인자를 L, s만 넘기고 L===k일 때 reduce 함수를 이용하여 더했는데, 그것보단 DFS에 sum 인자를 하나 더 넘겨서 L이 .. 2021. 10. 5.
[ 자바스크립트(JavaScript) ] section08 - 14 - 조합 구하기 📍 section08 - 14 - 조합 구하기 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요 // 입력 4 2 // 출력 1 2 1 3 1 4 2 3 2 4 3 4 6 조합을 구하는 문제인데, 이전에 배웠던 순열과는 조금 다른 방식으로 풀어야 한다. 중복을 허용하지 않는 순열을 구현할 때 배웠던 것처럼 visited 배열로 재귀가 돌아올 때 visited[i]=0을 해주는 방법으로는 풀 수 없고 대신 반복문의 i값을 조금 다르게 i+1을 계속 넘겨줘야 한다. arr값이 따로 주어져있으면 i는 0부터 시작하는데, 이 문제는 arr이 주어져 있지 않고 현재 인덱스가 값으로 들어가므로 s 인자는 1로 초기화하여 넘긴다. let n = 4; let m =.. 2021. 9. 30.
[ 자바스크립트(JavaScript) ] section08 - 13 - 수열 추측하기 📍 section08 - 13 - 수열 추측하기 문제는 다음과 같다. 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 파스칼의 삼각형을 예로 들어 N이 4이고 가장 윗 줄에 3 1 2 4가 있다고 할 때 다음 그림과 같이 그려진다. N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 여러 가지 답이 나오면 사전 순으로 가장 앞에 오는 것을 출력한다. // 입력 4 16 // 출력 3 1 2 4 문제만 보면 조금 어렵다고 생각했는데, 어떻게 풀어야 할지 순서를 나누니까 괜찮았다. 파스칼의 삼각형 공식을 알아야 하는데, 조합공식을 사용하면 파스칼 삼각형을 구할 때 처음부터 끝까지 두 항을 더해서 누적하는 불 필요한 계산을 하지 않아도 된다. 예를 들어.. 2021. 9. 29.

티스토리툴바