본문 바로가기

DFS8

[Algorithm] 경로 탐색(그래프-인접리스트) ❐ 경로 탐색(인접리스트) ▶︎ 문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. ▷ 입력 예제 5, [ [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5] ] ▶︎ 출력 예제 6 ▷ 문제설명 인접행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방법이다. 인접 행렬은 정점이 연결되어 있는지 확인하기 위해서 graph[a][b]의 요소만 확인할 수 있기 때문에 직관적이고 구현하기 쉽다는 장점이 있다. 하지만 구현해야 하는 그래프의 정점(vertex, 노드)의 개수가 10억개라면 어떨까.. 2022. 10. 23.
[Algorithm] 경로 탐색(그래프-인접행렬) ❐ 경로 탐색(인접행렬) ▶︎ 문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. ▷ 입력 예제 5, [ [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5] ] ▶︎ 출력 예제 6 ▷ 문제설명 그래프를 그려 문제를 해결해 보자. 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다. 문제의 그래프는 정점이 단순히 연결되어 있을 뿐 아니라 방향을 가리키고 있다. 예를 들어 1번 정점(vertex, 노드)은 2, 3, 4번 정점을 가리키고 있고, 1번과 2번 정점은 서로를 가리키.. 2022. 10. 22.
[Algorithm] 조합 구하기(DFS) ❐ 조합 구하기 ▶︎ 문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요. 자연수 N과 M이 입력됩니다. ▷ 입력 예제 4 2 ▶︎ 출력 예제 1 2 1 3 1 4 2 3 2 4 3 4 ▷ 문제설명 조합은 서로 다른 n개의 원소를 가진 집합에서 순서에 상관없이 r개의 원소를 선택하는 것을 말한다. 쉽게 말해 1부터 n까지 적혀있는 구슬 주머니에서 r개의 원소를 한번에 뽑는 경우의 수를 세는 것과 같다. 구슬을 뽑는 순서도 고려하는 순열과는 다르다. 문제처럼 자연수 4까지의 수에서 2개를 뽑는 경우의 수를 그림으로 도식화하면 다음과 같다. 총 2개를 뽑는데 숫자 1은 무조건 포함되어 있는 경우의 수는 3개, 숫자 2는 무조건 포함되어있고 앞선 조.. 2022. 10. 19.
[Algorithm] 순열 구하기(DFS) ❐ 순열 구하기 ▶︎ 문제 10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 입력으로 M과 N개의 자연수가 오름차순으로 정렬된 배열이 주어집니다. ▷ 입력 예제 2, [3, 6, 9] ▶︎ 출력 예제 3 6 3 9 6 3 6 9 9 3 9 6 ▶︎ 문제 설명 순열은 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 나열하는 것을 말한다. 이전 포스팅에서 중복순열은 중복을 허용하기 때문에 3 3과 같은 경우의 수가 가능했던 반면, 순열에서는 이것이 허용되지 않는다. ▷ 내 답안 function solution(m, arr) { let answer = []; let n = arr.length; let ch = Array.from({ length: n }.. 2022. 10. 13.
[Algorithm] 중복순열 구하기(DFS) ❐ 중복순열 구하기 ▶︎ 문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. ▷ 입력 예제 3 2 ▶︎ 출력 예제 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 ▷ 문제설명 일반적으로 순열은 서로 다른 n개 중 r개를 순서를 고려하여 나열하는 것을 말한다. 한 번 고른 것은 다시 고를 수 없는 것이 원칙이나, 중복순열의 경우에는 특별히 중복을 허용한다. 문제는 3까지의 번호가 적힌 구슬에서 두 개를 뽑아 중복을 허락하여 나열하는 경우의 수를 구하라고 한다. 즉, 주머니에 1부터 3까지 적혀있는 구슬 세개가 들어있다고 가정했을 때 ① 주머니에 들어있는 세개의 구슬 중 하나를 뽑아서 첫번째 자리 수를 정하고 ② 뽑은.. 2022. 10. 12.
[Algorithm] 합이 같은 부분집합(DFS) ❐ 합이 같은 부분집합 ▶︎ 문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 예를 들어 {1, 3, 5, 6, 7, 10} 이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있습니다. ▷ 입력 예제 1 3 5 6 7 10 ▶︎ 출력 예제 YES ▷ 내 답안 function solution(arr) { let answer = "NO"; let c.. 2022. 10. 9.
[Algorithm] 부분집합 구하기(DFS) ❐ 부분집합 구하기 ▶︎ 문제 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하시오. 단, 공집합은 출력하지 않습니다. ▷ 입력 예제 3 ▶︎ 출력 예제 1 2 3 1 2 1 3 1 2 3 2 3 ▷ 내 답안 function solution(n) { let answer = ""; let ch = Array.from({ length: n + 1 }, () => 0); function DFS(L) { if (L > n) { ch.forEach((ele, i) => { if (ele === 1) { answer = answer + i.toString(); } }); answer = ""; return; } else { ch[L] = 1; DFS(L + 1); .. 2022. 10. 8.
[Algorithm] 이진트리 깊이우선탐색(DFS) ❐ 이진트리순회 이진트리는 부모노드에서 자녀노드로 뻗어나가는 구조를 가진다. 그림에서 왼쪽에 위치한 자녀는 (부모노드)*2의 값을 가지고, 오른쪽에 위치한 자녀는 (부모 노드)*2+1의 값을 가지게 된다. 이진트리를 순회하는 여러가지 방법이 있다. 이 글에서는 3가지 방법을 소개하는데 부모의 순서에 따라 전위/중위/후위 순회로 구분된다. 전위 순회는 부모, 왼쪽자녀, 오른쪽 자녀 순서로 출력된다. 중위 순회는 왼쪽자녀, 부모, 오른쪽 자녀 순서로 출력된다. 후위 순회는 왼쪽자녀, 오른쪽 자녀, 부모 순서로 출력된다. 위의 그림을 전위/중위/후위 순회한 결과는 이렇다. 전위 순회: 1-2-4-5-3-6-7 중위 순회: 4-2-5-1-6-3-7 후위 순회: 4-5-2-6-7-3-1 코드로 나타내보자. con.. 2022. 10. 7.