inflearn78 [ 자바스크립트(JavaScript) ] section08 - 7 - 최대점수 구하기(DFS) 📍 section08 - 7 - 최대점수 구하기(DFS) 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 구하는 문제다. 처음 문제를 봤을 때 회의실 배정문제와 비슷한 줄 알았는데, 그리디로는 풀 수 없었다. 점수를 높은 순으로 정렬(sort)한 다음 순서대로 풀면 제 한 시간 안에 최대 점수를 얻을 수 있지 않나?라고 생각했는데 그것보다, 모든 경우의 수(부분집합)를 구해서 M보다 작으면서 동시에 최대 점수를 갱신하면 되는 문제였다. 여기서 모든 경우의 수를 구하지 않고 edgeCut(가지치기)을 이용했는데 현재까지 누적된 시간이 M보다 크다면 더 이상 계산 할 필요 없이 return하는 코드를 추가했다. 종료 조건은 L===n인데, 문제는 한 유형당 한 개씩만 풀 수 있기 때문에 하나씩 모.. 2021. 9. 23. [ 자바스크립트(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. 이전 1 2 3 4 5 6 7 8 ··· 16 다음
