choi95의 TIL📝

문제 n개의 정수로 이루어진 리스트 nums와 정수 target이 주어졌을 때, num에 있는 정수 4개를 합하여 target을 만들 수 있는 모든 조합을 구하시오.단, 정답에는 동일한 정수 조합이 여러개 포함되어서는 안된다. 문제풀이 중복을 허락하지 않기 때문에 이를 확인할 수 있는 체크 배열을 생성 조건을 만족하는 정수 조합은 여러개 포함되면 안되기 때문에 이를 식별할 수 있는 별도의 변수 선언 깊이 탐색을 통해 조건에 만족하는 조합을 정답 리스트에 포함시키고, 처음 재귀를 시작할 때 해당 정답 리스트에 현재 검사하는 조합이 포함되어 있는지 검사_조합은 순서를 고려하지 않기 때문에 하고, 있다면 그대로 함수를 종료 처음에는 3번 조건을 만족시키기 위해 forEach 메서드를 사용하여 순회하려고 했지만..

문제 문제풀이 문제를 풀기 전 해당 공식이 어떻게 성립이 되는지 살펴 보자. 예를 들어 5개의 경우수 중 3개를 뽑는다고 가정해 보자. 이때 가장 큰 값인 5(n)를 기준으로 봤을 때, 조합을 구할 수 있는 경우의 수는 크게 5를 포함한 경우와 5를 포함하지 않을 경우인 2가지로 나뉜다. 5를 포함할 경우에는 남은 4개의 경우수 중 나머지 자리 2개(r-1)를 뽑고 5를 포함하지 않을 경우에는 남은 4개 경우수 중 나머지 3개(r)개를 뽑은 것이다. 코드 function solution(n, r) { let answer = 0; function DFS(n , r) { if(n === r || r === 0) return 1; //나올 수 있는 가장 작은 경우수 1을 반환 else return DFS(n ..

문제 10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 문제풀이 중복을 허락하지 않기 때문에 별도의 체크 배열을 만들어 이전에 참조했던 value일 경우에는 연산을 수행하지 않도록 한다. 코드 function solution(m, arr) { let answer = []; let n = arr.length; let tmp = Array.from({length: m}, () => 0); let ch = Array.from({length: n}, () => 0); function DFS(L) { if(L === m) { answer.push(tmp.slice()); } else { for(let i = 0; i < n; i++) { if(ch[i] === 0) ..

문제 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?각 단위의 동전은 무한정 쓸 수 있다. 문제풀이 코드 function solution(arr, m) { let answer = Number.MAX_SAFE_INTEGER; let n = arr.length; function DFS(L, sum) { if(sum > m) return; //거스름돈 금액을 합산 금액이 넘어섰을 경우 if(sum === m) { answer = Math.min(answer, L); } else { for(let i = 0; i < n; i++) { DFS(L + 1, sum + arr[i]); } } } DFS(0, 0); return answer; } c..

문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 문제풀이 다중 for문과 재귀의 차이 트리 구조를 통해 DFS 탐색을 하는 것은 다중 for문을 하는 것과 전체적인 동작 방식이 똑같다.하지만 왜 해당 문제에서 중복순열을 구할 때 다중 for문이 아닌 재귀 함수를 사용하는 것인지는 다음 코드를 통해 확인할 수 있다. function solution(n , m) { let answer = []; for(let i = 1; i

문제 이번 정보올림피아드 대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다. 한 유형 당 한 개만 풀 수 있습니다) 문제풀이 코드 function solution(limit, arr) { let answer = Number.MIN_SAFE_INTEGER; let n = arr.length; function DFS(level, time, sum) { if(level === n) { if(time > limit) return; //제한 시간을 초과했을 경우 answer = Ma..

문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 문제풀이_묶음 기준 묶을 경우와 묶지 않을 경우 두 개로 나눠 다음 레벨로 이동 depth를 넘어설 경우 탐색 종료 및 나뉜 두 집합을 비교 코드 function solution(d, n) { le..

문제 자연수 N이 주어지면 1부터 N개까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 문제풀이 원소가 포함되냐(1) 포함되지 않느냐(0)에 따라 두 간선으로 나눔 자연수 N개까지 탐색을 계속 하고 N의 범위를 넘어서게 되면 탐색을 종료 및 부분집합 출력 부분집합을 출력하기 위해서 지금까지 탐색 했던 원소들이 포함인지 미포함인지 체크해둔 별도의 변수 필요 코드 function solution(n) { let answer = []; let check = Array.from({length: n + 1}, () => 0); //포함인지 미포함인지 체크하는 배열(자연수 1부터 시작이기 때문에 체크 배열 또한 1가산) function DFS(v) { if(v === n + 1) { //N..