Algorithm
-
동전교환Algorithm 2022. 6. 28. 11:23
문제설명 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 입력설명 첫 번째 줄에는 동전의 종류개수 N(1= answer) return; if (sum === exchange) { answer = Math.min(answer, L); } else { for (let i = 0; i < n; i++) { DFS(L + 1, sum + coins[i]); } } } DFS(0, 0); return answer; } 문제출처 https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%..
-
중복순열 구하기Algorithm 2022. 6. 27. 11:25
문제설명 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다. 이 문제는 M번이 상수로 주어질 경우 다중 for문을 이용하여 쉽게 구할 수 있다. 하지만 지금처럼 몇번 뽑아야하는지 모를 때는 일일이 다중 for문의 변수를 i,j,k, ... 이런식으로 늘려줄 수가 없기에 재귀함수를 이용하여 M번의 레벨에서 멈추게 해주면 쉽게 구현할 수 있다. function solution(n, m) { let answer = 0; function DFS(L) { if (L === m) { answer++; } else { for (let i = 1; i
-
합이 같은 부분집합 (아마존 인터뷰)Algorithm 2022. 6. 26. 12:27
문제설명 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력설명 첫 번째 줄에 자연수 N(1 prev + cur, 0) === arr .filter((v) => !subSet.includes(v)) .reduce((prev..
-
부분집합 구하기Algorithm 2022. 6. 26. 10:58
문제 설명 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요. 입력설명 첫 번째 줄에 자연수 N(1 0) answer.push(arr); } else { check[v] = 1; DFS(v + 1); check[v] = 0; DFS(v + 1); } } DFS(1); return answer; } // [ [ 1, 2, 3 ], [ 1, 2 ], [ 1, 3 ], [ 1 ], [ 2, 3 ], [ 2 ], [ 3 ] ] check라는 배열을 [0,0,0,0]으로 초기화하고 DFS(1)부터 시작하여 DFS(3)까지 재귀함수를 호출하고 4에 출력을 한다. 호출 과정에서 check의 상태가 정해지게 된다. 예를들어 check = [0,1,1,1] 로 정해..
-
뮤직비디오Algorithm 2022. 6. 23. 14:32
문제 설명 지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기 로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. ..
-
이분검색Algorithm 2022. 6. 23. 09:23
이분검색이란? 정렬된 배열에서 고유한 값들을 가질 때 중간 값을 기준으로 반으로 나누어 특정 값의 위치를 효율적으로 찾는 알고리즘이다. 예를 들어 [1,2,3,4,5,6,7,8,9] 배열이 있고 우리가 찾는 값은 2라고 가정하자. 1) 중간 값(5)을 기준으로 검색을 하면 2는 5보다 작으므로 5의 왼쪽에 포함되어 있다. 2) [1,2,3,4] 배열만 남긴채 위와 같은 검색을 한다. (이때, 크기가 짝수일 경우 '왼쪽'을 중간값으로 하겠다 라고 기준을 정해놓겠다) 3) 중간 값은 2이고, 우리가 찾는 숫자랑 같으면 검색을 종료한다. 배열의 데이터가 n개 라면 첫 번째 검색을 하면 n/2가 남는다. 두 번째는 n/2 * 1/2 가 남는다. 세 번째 n/2 * 1/2 * 1/2 ... 반복을 하면 k번째에는..
-
결혼식Algorithm 2022. 6. 22. 18:23
문제 설명 현수는 다음 달에 결혼을 합니다. 현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다. 피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다. 각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다. 현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요. 만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다. 입력설명 첫째 줄에 피로연에 참석할 인원수 N(5 { if (a[0] === b[0]) return a[1].ch..