728x90
순열 알고리즘 Permutation Algorithm
(1) 순열
서로 다른 n개에서 r( 0 < r ≤ n )개를 택하여 일렬로 나열하는 것을 n개에서 r개를 택하는 순열이라 하고, 이 순열의 수를 기호로 nPr와 같이 나타낸다.
ex) 서로 다른 5개에서 3개를 택하는 순열의 수는 5P3 = 5 · 4 · 3 = 60 이다.
n : 서로 다른 것의 개수
r : 택하는 것의 개수
(2) 문제
사용자로부터 길이가 같은 배열 A, B를 받아 A를 B의 순열에 1대 1로 중복 없이 곱한 수 중 가장 적은 결과 값을 구하시오.
ex) 사용자로부터 받은 배열 A={1, 2}, B={1, 2}
결과값① : A{1, 2}, B{1, 2} => 1*1 + 2*2 = 5
결과값② : A{1, 2}, B{2, 1} => 1*2 + 2*1 = 4
가장 적은 결과값 = 4
(3) 접근방식
※ 순열 공식 nPr은 경우의 수를 반환하는 공식일 뿐 실제 순열의 결과 값들은 알 수 없다. 그러므로 순열 알고리즘이라는 이름 아래 모든 경우의 수가 아닌 모든 경우의 결과 값을 구하는 javascript 함수를 작성한 뒤 활용하기로 하였다.
기능 구현 구상
1. 사용자로부터 같은 길이의 배열 A와 B를 받는다.
2. 배열 B의 순열을 구하는 동시에 A를 순차적으로 곱한다.
3. 곱하는 과정 중 도출된 첫 번째 결과 값을 result 전역변수에 저장한다.
4. 곱하는 과정 중 도출된 순열과 결과 값을 전역 변수에 추가한다.
5. 두 번째 이후로 도출된 결과 값을 result 와 비교하고 더 적은 수일 경우 바꿔담는다.
6. (출력) 배열 B의 순열을 나열한다. ex) B의 순열은 {1, 2}, {2, 1} 입니다.
7. (출력) 모든 결과 값을 나열한다. ex) 결과 값은 5, 4 입니다.
8. (출력) 가장 적은 결과 값을 출력한다. ex) 가장 적은 결과 값은 4 입니다.
(4) 풀이
<!DOCTYPE html>
<html>
<head>
<title>bucketplace_JangEunYeong</title>
<style type="text/css">
/*Common css*/
input[type=button]{cursor: pointer;}
.w50p{display: inline-block; vertical-align: top; width: 49%;}
/*Calculation css*/
#numberBox{width: 100%;}
#numbers1, #numbers2{width: 205px;}
#number1, #number2{width: 50px;}
#btnClear, #btnResult{display: inline-block; margin: 10px 0px; width: 175px; height:30px;}
#btnClear, #btnResult{background-color: white; border: none; box-shadow: 1px 1px 3px 0px gray;}
#btnClear:hover, #btnResult:hover{background-color: gainsboro;}
#msg{color: red;}
</style>
</head>
<body>
<!-- START Document Elements -->
<div>
<div>
<h2>계산</h2>
<p>사용자가 원하는 숫자 배열을 생성한 후 결과확인 버튼을 누르면 만들어지는 결과 값 중에서 가장 작은 결과 값을 반환합니다.</p>
<p id="lengthCheck">*배열 ①과 ②는 동일한 갯수로 등록해 주세요.</p>
<div id="numberBox">
<div>
<span>①</span> : <input id="number1" type="text" value=""/>
<input type="button" onclick="addNumber('1')" value="+"/>
<input id="numbers1" type="text" value="" disabled="disabled"/>
<input type="button" onclick="removeNumber('1')" value="←"/>
</div>
<div>
<span>②</span> : <input id="number2" type="text" value=""/>
<input type="button" onclick="addNumber('2')" value="+"/>
<input id="numbers2" type="text" value="" disabled="disabled"/>
<input type="button" onclick="removeNumber('2')" value="←"/>
</div>
<input id="btnClear" type="button" onclick="init()" value="초기화"/>
<input id="btnResult" type="button" onclick="calculation()" value="결과"/>
<span id="msg"></span>
</div>
</div>
<hr>
<div>
<div class="w50p" style="border-right: 1px solid gainsboro;">
<h2>풀이</h2>
<div>
<p>배열 ②의 모든 순열</p>
<span id="arrPermBox"></span>
<hr>
<p>곱한 결과 값 목록</p>
<span id="arrMultipleBox"></span>
</div>
</div>
<div class="w50p">
<h2>결과</h2>
<span>가장 작은 결과 값은 </span><span id="resultBox">...</span><span>입니다.</span>
</div>
</div>
</div>
<!-- END Document Elements -->
<!-- START javascript -->
<script type="text/javascript">
//주요변수 선언
var $numbers1 = document.getElementById("numbers1"); //배열 ①
var $numbers2 = document.getElementById("numbers2"); //배열 ②
var $number1 = document.getElementById("number1"); //숫자 ①
var $number2 = document.getElementById("number2"); //숫자 ②
var $arrPermBox = document.getElementById("arrPerm"); //풀이과정 - 배열 ②의 모든 순열
var $arrMultipleBox = document.getElementById("arrMultiple"); //풀이과정 - 모든 곱의 경우
var $result = document.getElementById("result"); //결과
var $msg = document.getElementById("msg"); //메세지
var _arrPerm = new Array(); //배열 순열 데이터
var data = new Array(); //원본배열
//add number to array
function addNumber(type){
if(type == "1"){
var numbers = numbers1.value;
var num = number1.value.replace(/\s/g,''); //remove spaces
if(!num){
alert("배열 ①의 숫자를 입력해주세요.");
return;
}
numbers1.value = numbers != "" ? numbers + "," + num : num;
number1.value = "";
} else if(type == "2"){
var numbers = numbers2.value;
var num = number2.value;
if(!num){
alert("배열 ②의 숫자를 입력해주세요.");
return;
}
numbers2.value = numbers != "" ? numbers + "," + num : num;
number2.value = "";
}
}
//remove number(backspace)
function removeNumber(type){
if(type == "1"){ //고정 배열
var numbers = numbers1.value.split(",");
if(numbers.length > 1){
for(var i=0; i<numbers.length-1; i++){
if(i==0){
numbers1.value = numbers[i];
}else{
numbers1.value += ","
numbers1.value += numbers[i];
}
}
}else{
numbers1.value = "";
}
} else if(type == "2"){ //swap할 대상 배열
var numbers = numbers2.value.split(",");
if(numbers.length > 1){
for(var i=0; i<numbers.length-1; i++){
if(i==0){
numbers2.value = numbers[i];
}else{
numbers2.value += ","
numbers2.value += numbers[i];
}
}
}else{
numbers2.value = "";
}
}
}
//init
function init(){
numbers1.value = "";
number1.value = "";
numbers2.value = "";
number2.value = "";
arrPermBox.innerHTML = "";
arrMultipleBox.innerHTML = "";
resultBox.innerHTML = "...";
}
//deep copy
function copyArray(arr){
var result = new Array();
for(var i=0; i<arr.length; i++){
result[i] = arr[i];
}
return result;
}
//calculation
function calculation(){
var arr1 = numbers1.value.split(","); //배열 ①
var arr2 = numbers2.value.split(","); //배열 ②
var arrMultiple = new Array(); //배열 ①과 ②의 순열을 곱한 모든 경우의 결과 값
var result = 0; //결과 값(가장 적은 결과 값)
_arrPerm = new Array(); //배열의 순열 데이터를 담는 변수
//배열의 길이가 다를 경우 반환
if(arr1.length !== arr2.length){
msg.innerHTML = "*두 배열의 길이가 일치하지 않습니다.";
//값 초기화
arrPermBox.innerHTML = "";
arrMultipleBox.innerHTML = "";
resultBox.innerHTML = "...";
return;
}else{
msg.innerHTML = "";
}
//배열 ②의 순열 목록 _arrPerm에 담기
data = arr2;
permutation(data.length, data.length);
//배열 ①과 ②의 순열을 곱한 모든 경우의 결과 값 담기
for(var i=0; i<_arrPerm.length; i++){
var val = 0;
for(var j=0; j<arr1.length; j++){
val += arr1[j] * _arrPerm[i][j];
}
arrMultiple.push(val);
//결과 값(가장 적은 결과 값) 담기
if(i==0){
result = val;
}else if(val < result){
result = val;
}
}
//출력 (풀이과정, 모든 곱의 경우, 결과)
print(_arrPerm, arrMultiple, result);
}
//permutation
function permutation(len, depth){
//순열 목록에 담기
if( depth == 1 ) {
_arrPerm.push(copyArray(data));
}
//배열 원본 데이터를 유지하기 위해 swap을 두 번 실행한다.
for(var i=0; i<depth; i++){
swap(i, depth-1);
permutation(len, depth-1);
swap(i, depth-1);
}
}
//swap
function swap(i, j){
var temp;
if(i==j){
return;
}
temp = data[i];
data[i] = data[j];
data[j] = temp;
return;
}
//print
function print(_arrPerm, arrMultiple, result){
//값 초기화
arrPermBox.innerHTML = "";
arrMultipleBox.innerHTML = "";
resultBox.innerHTML = "...";
//풀이 - 배열 ②의 모든 순열
for(var i = 0; i<_arrPerm.length; i++){
arrPermBox.innerHTML += " [ ";
for(var j=0; j<_arrPerm[i].length; j++){
if(j==0){
arrPermBox.innerHTML += _arrPerm[i][j];
}else{
arrPermBox.innerHTML += ",";
arrPermBox.innerHTML += _arrPerm[i][j];
}
}
arrPermBox.innerHTML += " ] ";
}
//풀이 - 모든 곱의 경우
for(var k=0; k<arrMultiple.length; k++){
if(k==0){
arrMultipleBox.innerHTML += arrMultiple[k];
}else{
arrMultipleBox.innerHTML += ",";
arrMultipleBox.innerHTML += arrMultiple[k];
}
}
//결과
resultBox.innerHTML = result;
}
</script>
<!-- END javascript -->
</body>
</html>
(5) 풀이 후기
인터넷에 많이 올라와 있는 순열 알고리즘 참고소스를 확인하기 전 수학공식을 토대로 스스로 만들어보려고 했다. 그러나... 도출하고자 했던 최종 결과 값 까지는 뽑아내었는데 문제는 출력 구상 목록 중 1번인 배열 B의 순열을 나열한다는 부분에서 중복되는 배열이 출력되는 현상이 나타났다.
이 현상을 고치고자 이리 저리 머리를 굴려보다 결국 인터넷 소스를 참고하게 되었고 depth를 활용한 소스를 참고하여 수정하고 나니 중복된 배열 출력 현상을 해결할 수 있었다.
728x90
'Study Note > Algorithm' 카테고리의 다른 글
| 프로그래머스 #정렬 - K번째수 lv1 (0) | 2021.01.20 |
|---|---|
| 프로그래머스 #해시 - 베스트앨범 lv3 (0) | 2021.01.16 |
| 프로그래머스 #스택/큐 - 기능개발 lv2 (0) | 2021.01.16 |
| 프로그래머스 #해시 - 위장 lv2 (0) | 2021.01.10 |
| 프로그래머스 #해시 - 완주하지 못한 선수 lv1 (1) | 2020.10.16 |
댓글