algorithm

알고리즘 연습문제

1. slice max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* 정수값을 가진 배열이 있을 때, 임의의 x,y,z 값을 정하고, 0<= x < y < z <= arr.length 라고 정의한다.
문제) a[x+1]에서 a[y-1] 사이의 값들과 a[y+1]에서 a[z-1] 사이의 값을 모두 더했을 때 최대값은 무엇인지 구하시오.
function slice(arr)
(3 <= arr.length <= 100,000)
(-10,000 <= n <= 10,000)

예를 들어 a = [3,2,6, -1,4,5, -1,2] 일 때,
(x=0, y=3, z=6) 일 때 a[1] + a[2] + a[4] + a[5] => 2 + 6 + 4 + 5 = 17,
(0, 3, 7) a[1] + a[2] + a[4] + a[5] + a[6] => 2 + 6 + 4 + 5 − 1 = 16,
(3, 4, 5) 사이 값이 없으므로 0.

따라서 최대값은 17이 된다. */

function slice_origin(arr){
    var sum = 0 ;
    // x = 0~ arr.length-3
    // y = 1~ arr.length-2
    // z = 2~ arr.length-1
    for(var x=0; x<arr.length-3; x++){
        for(var y=0; y<arr.length-2; y++){
            for(var z=0; z<arr.length-1; z++){
                if(x<y && y<z){
                    var temp_sum = sums(x,y,z,arr);
                    if(sum < temp_sum){
                        sum = temp_sum;         
                        console.log("===");               
                        console.log("sum"+sum);
                        console.log("===");     
                        console.log(x,y,z);
                        console.log("===");     
                    }
                 }
            }
        }
    }
    function sums(x,y,z,arr){
        var sum = 0;
        var xy = arr.slice(x+1,y);
        for(var i=0; i<xy.length; i++){          
            sum += xy[i];
        }
        var yz = arr.slice(y+1,z);
        for(var j=0; j<yz.length; j++){
            sum += yz[j];
        }
        return sum;
    }
}
var arr = [-3,-1,10,-6,-3,4,5,-1,-5,-1,5,4,1,-5,-1,-5,-11111,-2,0,-9,-10,14,1,-1];//  [200,6,1,4,5,1,10,2,4,6,-100,-10000] ;
slice_origin(arr);

2. bracket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* Visual Studio Code와 유사한 Editor+++라는 에디터가 있다.
Visual Studio Code에서는 괄호를 입력하면 자동으로 닫는 괄호가 입력되는 것처럼 Editor+++도 자동으로 괄호를 닫는다.
그런데 Editor+++는 가끔 버그로 인해 닫는 괄호를 늦게 다는 경우가 있다. 

여기에 Editor+++에서 작성한 텍스트가 있는데 이 텍스트를 Visual Studio Code로 복사하고자 하는데
이 때 괄호가 올바른지 아래와 같이 검증하고자 한다.

예를 들어 (), {()} {()()} 처럼 입력할 때 닫는 괄호가 올바르게 표시되며 이는 올바른 형태이다.
그러나 ([)()] 의 경우 모두 쌍은 맞으나 괄호가 올바를 위치에 있지 않으므로 이는 올바르지 않은 형태이다.


문제) Editor+++에서 작성한 괄호값을 가진 임의의 텍스트가 있을 때, Visual Studio Code에서 인식이 가능한지 파악하고, 가능하면 true, 불가능하면 false를 출력하라. */
function bracket_replace(str){    
    var result = true;
    if(str.length%2==1) return false;
    var startlength = str.length;
    
    do {
        str = str.replace(/\(\)|\{\}|\[\]/g,'');
        if(str.length==0) break;
        if(str.length == startlength) result = false;
        startlength=str.length;
    } while (result);

    return result;
}

3. count arr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 배열 A가 있다. 이 배열은 배열 B의 몇번째 위치에 값을 증가(++) 시켜야 하는지에 대한 정보를 담고 있다.
예를 들어 a = [3,4,4,5,1,4,4] 인 배열이 있다고 할 때,
a[0]= 3 이므로 배열의 3번째 값을 증가 시켜라 (0,0,1,0,0)
a[1]= 4 이므로 배열의 4번째 값을 증가 시켜라 (0,0,1,1,0)
a[2]= 4 이므로 배열의 4번째 값을 증가 시켜라 (0,0,1,2,0)
이 것을 반복하면 배열 B는 [1,0,1,4,1] 값을 갖는다. */
function count_arr(arr){
    var max = arr.reduce( function (previous, current) { 
		return previous > current ? previous:current;
	});
    var return_arr = new Array(max);
    return_arr.fill(0);

    for(let val of arr){
        return_arr[val-1] = return_arr[val-1]+1;
    }
    return return_arr;
}

4. quick sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Array.prototype.quickSort = function() {

    var r = this;
    if(this.length <= 1) {
      return this;
    }
    var less = [], greater = [];
  
    var pivot = r.splice(Math.floor(r.length / 2),1);
    console.log("중간지점값:"+pivot);
     // 중간값 기준 작은 값 or 큰 값
    for (var i = r.length - 1 ; i >= 0; i--){
      if ( r[i] <= pivot) {
        less.push(r[i]);
      } else {
        greater.push(r[i]);
      }
    }   
    var c = [];
    
  return c.concat(less.quickSort(), pivot, greater.quickSort());
  
  };
  
  var a = [3,1,43,5,123,6,231,0];
  console.log(a.quickSort());