BOJ 10819 with js _ 차이를 최대로 (순열)
10819 with Node.js _ 차이를 최대로
문제
N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.
| A[0] - A[1] | + | A[1] - A[2] | + … + | A[N-2] - A[N-1] |
입력
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
출력
첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.
정답 코드
const fs = require("fs");
const stdin = (
process.platform === "linux"
? fs.readFileSync("/dev/stdin").toString()
: `` // 기본 입력값 설정 (백준 코딩테스트에서 비워놔도 무방하다.)
).split("\n");
const input = (() => { //input()을 호출할 때마다 한줄씩 읽어온다.
let line = 0;
return () => stdin[line++];
})();
const count = +input();
let list = input().split(' ').map(value => Number(value));
let checkList = new Array({length : list.length}, v => false);
let temp = [];
let result = 0;
function permitation(index){ // 순열을 이용한 완전 탐색
if(index == count) {
let sum =0;
for(let i = 0; i < temp.length - 1; i++){
sum += Math.abs(temp[i] - temp[i+1]);
}
result = Math.max(sum, result);
}
for(let i = 0; i < count; i++){
if(checkList[i] == true){
continue;
}
checkList[i] = true;
temp.push(list[i]); // 백 트래킹 하나의 재귀호출마다 자릿수 하나를 채워 넣음
permitation(index+1);
temp.pop();
checkList[i] = false;
}
}
permitation(0);
console.log(result);
살펴보아야 할 점
- 숫자가 최대 8개 밖에 되지 않기 떄문에, 완전탐색으로 전부 검사 가능하다.
- 순열을 찾는 방식을 통해 하나의 재귀호출마다 자릿수 하나를 채워넣는다.
- 첫 자리의 값을 N 개 중 하나로 결정하면, 두번째 자리로 들어가 나머지 N-1 개 중 하나를 뽑고, 세번째 자리에서는 N-2 개 중 하나를 뽑는 식으로 재귀가 들어간다.
백트래킹(Backtracking)
해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.
즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.
이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.
일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다.
가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.
정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것입니다.
즉 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 됩니다.
주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있습니다.
참고사이트
https://chanhuiseok.github.io/posts/algo-23/
Leave a comment