백트래킹10 [백준 10819/javascript] 차이를 최대로 처음에 n, n+1 일때를 더해서 답을 내면 되나 했지만 배열의 각 요소가 규칙없이 제멋대로 이동할 경우를 생각해야 하므로 특별한 로직이 없어 완전 탐색으로 풀려고 했다 하지만 배열 요소 수가 적으므로, 백트래킹이 더 유리하다고 판단하여 백트래킹을 사용하여 가능한 경우의 수를 모두 구하고 set 에 넣어 중복을 제거한 후 다시 배열로 만들어 최대값을 구해주면 되는 문제였다 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net let input = []; const.. 2022. 10. 12. [백준 1010/javascript] 다리 놓기 경우의 수는 너무 많을것 같으니 알고리즘을 생각해봤다 결국은 오른쪽 전체 중에 오른쪽 - 왼쪽 사이트 만큼. 즉 선택되지 않은 것들의 경우의 수를 구하면 되는 문제였다 백트래킹을 쓰려다 머리만 아파지고 콤비네이션(조합) 을 구현해서 풀었다 dp 로도 방법이 있다는데... 굳이 안써도 간단하게도 풀린다 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net let input = []; const readline = require("readline").c.. 2022. 10. 9. [백준 15655/javascript] N과 M (6) 백트래킹 문제 중복 불가이므로 중복을 확인할 배열을 만들어주고, 오름차순으로 결과가 나와야 하므로 미리 선택지 배열을 sort 후, 백트래킹 함수에 넣었다 앞의 수보다 뒤에 수가 더 커야 하므로 인자를 하나 더 전달하여 해결하였다 https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net let input = []; const readline = require("readline").createInterface({ input: process.std.. 2022. 9. 23. [백준 10974/javascript] 모든 순열 백트래킹 기본 문제 중복 불가이므로 isused 배열을 사용하여 사용중인지를 체크하였다 사전순 정렬은 어차피 1부터 증가시키며 넣어 완성하므로 신경쓰지 않아도 된다 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net let input; const readline = require("readline").createInterface({ input: process.stdin, output: process.stdout, }); readline.on("line", (line) => { input = line; readline.close(); }).. 2022. 9. 3. 이전 1 2 3 다음