DFS27 [ 자바스크립트(JavaScript) ] section08 - 6 - 바둑이 승차(DFS) 📍 section08 - 6 - 바둑이 승차(DFS) 문제: 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다고 한다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게는 무엇일까요? 부분집합을 이용한 문제다. 주어진 배열에서 부분집합을 구한 후 weight보다 작은 값 중 최댓값을 갱신시키는 방법으로 푼다. DFS 의 인자를 2개로 설정한 다음 weight 값을 누적시키거나 누적시키지 않는 방법을 사용한다. let weight = 259; let n = 5; let arr = [81, 58, 42, 33, 61]; console.log(solution(weight, n, arr)); function solution(weight, n, a.. 2021. 9. 17. [ 자바스크립트(JavaScript) ] section08 - 5 - 합이 같은 부분집합(DFS: 아마존 인터뷰) 📍 section08 - 5 - 합이 같은 부분집합(DFS: 아마존 인터뷰) N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나눌 때 두 부분집합의 원소의 합이 서로 같은 경우면 YES, 그렇지 않으면 NO를 출력하는 프로그램을 작성하는 문제다. 마찬가지로 순서도를 그려서 이해하는 것이 가장 빠르나, 입력 예제가 n=6이므로(총 64개의 가지를 그려야함) 따로 순서도를 그리지 않고 그림처럼 그리면 된다. 어떤 부분집합의 합이 같은지를 찾으려면 부분집합이 나올 수 있는 경우의 수를 모두 구한다. n=6이므로 총 부분집합의 개수는 2^6=64가 나온다. 합이 같은 부분집합을 찾을 때, A, B 부분집합을 모두 구하지 않고 한 부분집합만 구하고 나서 sum(배열) - aSum(한.. 2021. 9. 17. [ 자바스크립트(JavaScript) ] section08 - 4 - 부분집합 구하기(DFS) 📍 section08 - 4 - 부분집합 구하기(DFS) 자연수 n이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 구하여 출력 예제와 같은 순서로 출력하는데 공집합은 출력하지 않는 문제다. N의 범위는 1 2021. 9. 17. [ 자바스크립트(JavaScript) ] section08 - 3 - 이진트리 순회(깊이우선탐색) 📍 section08 - 3 - 이진트리 순회(깊이우선탐색) 이진트리 순회가 무엇인지 모르는 사람은 어려울 수 있는 문제다. 여기서 이진트리란 나무를 뒤집어 놓은 모양으로 한 개의 부모 노드와 2개의 자식 노드를 갖고 있는 트리구조를 일컫는다. 이진트리를 순회할 때는 3가지 방법이 있다. 전위순회(preOrder), 중위순회(inOrder), 후위순회(postOrder)가 있는데 어떻게 순회하는지 간략하게 알아보자. 첫 번째로 전위순회(preOrder)는 부모 → 왼쪽 자식 → 오른쪽 자식 순으로 탐색한다. 위 사진의 순회 결과는 1-2-4-5-3-6-7가 된다. 두 번째로 중위순회(inOrder)는 왼쪽 자식 → 부모 → 오른쪽 자식 순으로 탐색한다. 이때 주의할 점은 더 이상 자식이 없을 때까지 내려.. 2021. 9. 16. [ 자바스크립트(JavaScript) ] section08 - 2 - 재귀함수를 이용한 이진수 출력 📍 section08 - 2 - 재귀함수를 이용한 이진수 출력 10진수 N을 2진수로 변환하는 문제이다. 저번에 풀었던 재귀함수에서 조금 응용하면 쉽게 풀 수 있는 문제다. 백준에도 비슷한 문제가 있었는데 이진수와 관련한 문제인 백준 3460 - 이진수 문제였다. 재귀를 이용할 때 초보자는 if-else문을 사용하는것이 더 이해하기 쉽다고 선생님께서 말씀하셨다. 이진수를 구하려면 어떤 수를 몫이 0이 될 때까지 2로 계속 나누면서 나머지를 누적하는데 이때, 나머지를 거꾸로 누적해야 이진수가 된다. 예를 들어 11을 이진수로 표현한다고 가정하면 다음과 같이 계산하면 된다. 그리고 answer코드를 DFS 함수 위에 선언하냐 밑에 선언하냐에 따라 값이 달라지는데 DFS 위에 선언하게 되면 나머지가 반대방향으.. 2021. 9. 16. 이전 1 2 3 4 5 6 다음
