합병 정렬 ( merge sort )

합병 정렬이란?

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.

합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

코드와 설명

const mergeSort = arr => {
    if ( arr.length < 2 ) return arr; // 배열의 길이가 1개일 때 배열을 리턴
    const middle = parseInt(arr.length/2); // 배열의 중간지점을 잡음
    const left = arr.slice(0, middle); // 0부터 중간까지
    const right = arr.slice(middle, arr.length); // 중간부터 끝까지
    return merge(mergeSort(left), mergeSort(right)); // merge라는 정렬해주는 함수에 인자로 보내줌
}

const merge = (left, right) => {
    let result = []; // 합병 결과 리턴값
    while ( left.length && right.length ) {
        left[0] > right[0] ? result.push(right.shift()) : result.push(left.shift()); // left, right 둘중 하나의 원소가 없을 때 까지 대소 비교 후 result 에 삽입
    }
    while ( left.length ) {
        result.push(left.shift()); // left의 남은 원소 삽입
    }
    while ( right.length ) {
        result.push(right.shift()); // right의 남은 원소 삽입
    }
    return result; // 리턴
}

console.log(mergeSort([3, 2, 1]))

우선 mergeSort라는 함수로 배열을 받으면, 배열의 길이가 1이될 때까지 반씩 쪼갬과 동시에 쪼갠 배열을 merge라는 함수에 넣어 순서대로 정렬한 뒤에 다시 합쳐준다.

사실 짜고도 완벽하게 정렬 과정이 이해가 안된다. 조금더 봐야할 것 같음ㅜ

// 추가 내용 : 직접 코드 진행 과정을 써보니까 이해가 되었음

mergeSort([3,2,1]) 을 기준으로 과정을 나열해 보면

mergeSort([3,2,1])

merge(mergeSort([3]), mergeSort([2,1])) // left, right 로 나뉘어져 리턴

merge([3], mergeSort([2,1])) // left 값, 즉 [3]은 배열의 길이가 1이므로 배열 자체를 리턴

merge([3], merge([2],[1])) // right값은 다시한번 left값 [2], right값 [1] 로 나뉘어짐

merge([3], [1,2]) // merge 함수에 의해 merge([2],[1]) 이 [1,2]로 리턴

[1,2,3] // merge 함수에 의해 merge([3], [1,2]) 가 [1,2,3]으로 리턴

위와 같이 정렬이 된다.

쉽다 !

Reverse Integer

문제

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

단순하게 숫자를 뒤집어서 출력하는 문제,

이때 32비트 정수를 넘어가면 0을 리턴

풀이

var reverse = function(x) {
    const rev = parseInt(x.toString().split('').reverse().join(''))
    if ( x > 2147483647 || rev > 2147483647 ) {
        return 0;
    } else {
        return x > 0 ? rev : -rev
    }
};

32비트 최대 정수값을 나타내는 자바스크립트 메소드가 있을줄 알고 한시간넘게 뒤졌는데 안나와서 그냥 214783647을 입력해버렸다..

설명할게 없당

삽입 정렬 ( Insertion sort )

삽입 정렬이란?

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

시간 복잡도는 O(n^2)지만, 인풋이 적고, 모든 데이터가 들어와 있다면 선택 정렬, 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠르다.

코드와 설명

const InsertionSort = arr => {
  let temp, j;
  for ( let i = 1; i < arr.length; i++ ) {
    temp = arr[i];
    j = i;
    while( j > 0 && arr[j-1] > temp ) {
      arr[j] = arr[j-1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}

console.log(InsertionSort([5,1,6,3,2,4,8]))

구현한 코드 설명하는게 코드짜는거보다 더어려운것 같다.

1. 배열의 i번째 인덱스 값을 temp에 담는다.
2. i 보다 작은 인덱스 j에 대해 각각 비교를 하며 temp가 값이 더 클때까지 j를 줄이며 반복문을 돌리며, 참일 경우에 한칸씩 뒤로 밀어준다.
3. while문에서 나오면 나온 지점에 temp를 넣어준다.
4. for문 나오면 리턴

코드 비주얼라이저로 직접 과정을 보면 이해가 쏙쏙!

3. Longest Substring Without Repeating Characters

문제

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

주어진 문자열에서 중복되지 않는 가장 긴 문자열을 찾아 길이를 리턴하는 문제

풀이

const lengthOfLongestSubstring = (s) => {
    let max = 0;
    let temp = [];
    for ( let i = 0; i < s.length; i++ ) {
        temp = [];
        for ( let j = i; j < s.length; j++ ) {
            if ( temp.indexOf(s[j]) === -1 ) {
                temp.push(s[j]);
                if ( max < temp.length ) {
                    max = temp.length
                }
            } else {
                break;
            }
        }
    }
    return max
};

for문 한개로 짜보려 했는데 도무지 생각이 안나서 두개로 어떻게 짜긴 짰는데 별로 좋은 코드는 아닌것 같다.

그래도 쓰긴 쓴거니까 설명을 붙이자면,

temp라는 임시 배열에 j번째 원소가 없다면 푸시해주는 방식으로 해서 temp 배열 길이의 최대값을 max에 담아 리턴하는식

어렵다 난이도가 medium 밖에 안되는 문젠데 ㅜ 갈길이 멀다.

다른사람의 풀이

const lengthOfLongestSubstring = function(s) {
    let result = '';
    let tempResult = '';
    for ( let i = 0; i < s.length; i++ ) {
        if ( tempResult.indexOf(s[i]) == -1 ) {
            tempResult += s[i];
            if ( tempResult.length > result.length ) {
                result = tempResult;
            }
        } else {
            if ( tempResult.length > result.length ) {
                result = tempResult;
            }
            let index = tempResult.indexOf(s[i]);
            tempResult = tempResult.slice(index+1) + s[i];
        }
    }
    return result.length;
};

사실 코드를 보고도 어떻게 하는지 감이 딱 오진 않지만, 내가 짠 코드보다는 낫다는건 알 것 같다.

내공이 부족한것 같다.

Two Sum

문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

nums라는 배열에서 임의의 두 수의 합이 target이 될 때 그 두수의 인덱스를 리턴하는 문제.
이 때 타겟이 만들어지는 경우는 한가지밖에 없다고 가정

풀이

const twoSum = (nums, target) =>  {
    for ( let i = 0; i < nums.length; i++ ) {
        if ( nums.indexOf(target-nums[i]) !== -1 && nums.indexOf(target-nums[i]) !== i ) {
            return [i, nums.indexOf(target-nums[i])]
        }
    }
};

포문으로 첫번째 인덱스 값부터 돌 때 타겟에서 뺀값이 배열내에 존재하면 해당 인덱스를 리턴하는 식

말로 설명하는게 더어렵다 ㅜ

LeetCode 알고리즘 공부

자바스크립트로 공부하기

보시면서 틀린 부분, 이해안되는 부분, 본인이 생각하는 더 나은 코드가 있다면 남겨주시기 바랍니다!

화이팅

가장 큰 정사각형 찾기 (Level 4)

문제

어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다.

A를 3만큼 밀면 D가 되고 z를 1만큼 밀면 a가 됩니다. 공백은 수정하지 않습니다.

보낼 문자열 s와 얼마나 밀지 알려주는 n을 입력받아 암호문을 만드는 ceasar 함수를 완성해 보세요.

• “a B z”,4를 입력받았다면 “e F d”를 리턴합니다.

풀이

function findLargestSquare(board) {
  let max = 0;
    for ( let i = 0; i < board[0].length; i++) {
      for ( let j = 0; j < board.length; j++ ) {
        board[i][j] = board[i][j] == "O" ? 1 : 0
      }
  }
  for ( let x = 1; x < board[0].length; x++ ) {
    for ( let y = 1; y < board.length; y++ ) {
      if ( board[x][y] !=0 ) {
        board[x][y] = 1 + Math.min(board[x-1][y], board[x][y-1], board[x-1][y-1])
      }
      if ( max < board[x][y] ) {
        max = board[x][y]
      }
    }
  }
  return Math.pow(max, 2)
}

//아래 코드는 테스트를 위한 출력 코드 입니다.
var testBoard = [['X','O','O','O','X'],['X','O','O','O','O'],['X','X','O','O','O'],['X','X','O','O','O'],['X','X','X','X','X']];
console.log(findLargestSquare(testBoard));

문제보고 주변 컴공인들에게 물어보니 그냥 DP로 풀면 되네! 라고 들어서 엄청 찾아봤는데도 접근도 어려운데다가 막상 써놓고 나서도 너무 복잡하다 생각들었는데, 다른사람들 코드가 더길어서 흐뭇했다(ㅋㅋ~)

BOJ 1915번과도 동일한 문제이다.

우선 첫 번째 for문에서는 O 표시를 1 X 표시를 0으로 바꿔준다.

두 번째 for문에서는 원소가 0이 아닌것에 대해서 왼쪽,위쪽, 왼쪽위쪽 세개 값중 최솟값에 1을 더해 만들수 있는 최대 변의 길이를 적어주고, 그 값이 max보다 크다면 max에 대입하는 식으로 해서, 최대 정사각형 변의 길이를 구한 후에 제곱해 리턴!

다른 사람의 풀이

더 좋은코드가 있을수도 있겠지만, 이것보다 더 긴 코드는 읽고싶지 않다..

시저 암호 (Level 3)

문제

어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다.

A를 3만큼 밀면 D가 되고 z를 1만큼 밀면 a가 됩니다. 공백은 수정하지 않습니다.

보낼 문자열 s와 얼마나 밀지 알려주는 n을 입력받아 암호문을 만드는 ceasar 함수를 완성해 보세요.

• “a B z”,4를 입력받았다면 “e F d”를 리턴합니다.

풀이

function caesar(s, n) {
  let arr = [];
  n = n % 26
  for ( let i = 0; i < s.length; i++ ) {
    const word = s.charCodeAt(i)
      if ( word == 32 ) {
      arr.push(" ")
    }
    else if ( word >= 65  && word <= 90 ) {
        if ( word+n > 90 ) {
          arr.push(String.fromCharCode(word+n-26))
      } else {
        arr.push(String.fromCharCode(word+n))
      }
    }
    else if ( word >= 90 && word <= 122 ) {
        if ( word+n > 122 ) {
          arr.push(String.fromCharCode(word+n-26))
      } else {
          arr.push(String.fromCharCode(word+n))
      }
    }
  }
  return arr.join("")
}

// 실행을 위한 테스트코드입니다.
console.log(caesar("abcdef", 25));

좀 오래걸린듯하다. 배열로 처리했음

다른 사람의 풀이

function caesar(s, n) {
    var result = "";
    // 함수를 완성하세요.
  var car = ""
  for (var i=0; i<s.length;i++)
  {        
    if ( s[i] == ' ' )
      result += ' '
    else 
        result += String.fromCharCode( (s.charCodeAt(i)>90)?
      (s.charCodeAt(i)+n-97)%26+97 : (s.charCodeAt(i)+n-65)%26+65 )     
  }
    return result;
}
// 실행을 위한 테스트코드입니다.
console.log('s는 "a B z", n은 4인 경우: ' + caesar("a B z", 4));

원리는 비슷하나 문자열로 조금더 간결한 코드