삽입 정렬이란?

정렬을 할 때, 자신보다 앞에 있는 배열들은 정렬이 되어있다고 가정하고 “자신의 위치를 찾아 삽입”하는 방법의 정렬이다. 즉 배열에서 정렬할 요소 선택하기 위해 모두 한번씩은 순회 해야하며(어떤 정렬이든 당연한 말이지만), 해당 요소를 선택한 경우에는 자신보다 앞에 있는 서브 배열을 순회하여 자신의 위치를 찾아야 한다. 즉, 처음부터 이쁘게 정렬이 되어있는 배열을 대상으로 삽입 정렬을 하려고 한다면 아주 빠르게(시간 복잡도 O(n)) 정렬이 가능하다.

과정

위와 같이 정렬되어 있지 않은 배열이 있다. 이 배열을 오름차순으로 정렬해보자.

1. 첫 번째 요소부터 배열을 순회하여 하나씩 정렬해 나간다. 따라서 가장 먼저 맨 첫번 째 요소를 선택한다. 그러나 첫 번쨰 요소의 경우 자신의 위치를 찾기위한 자기 앞의 정렬된 서브 배열이 없음으로 넘어간다. 그리고 이제 이 첫 번째 요소인 6은 정렬 된 서브 배열의 첫 구성원이 되었다.

2. 다음으로 5가 선택되었다. 선택된 5 앞에는 이미 정렬이 된 배열(그리고 우리가 꾸준히 정렬 해 나갈)이 존재하고 있다. 아직까진 정렬된 배열에 6 밖에 없다. 그럼, 5를 앞의 서브 배열의 어느 부분에 넣을지 생각해 보자.
   1. 일단 5를 빼내자. 서브 배열과 비교 도중 해당 요소인 5 보다 큰 요소가 한칸씩 밀려나가야 되기 때문에 이 빈 자리가 필요하다.
   2. 이제 이전에 빼낸 5와 서브 배열의 마지막 요소인 6과 비교한다. 6이 더 크기 때문에 6을 뒤로 한칸 밀어내고 5를 기존 6의 자리에 넣는다.
3. 다음은 3의 차례다. 3을 선택하고 빼내며 그 자리를 비워둔다(사실 비워두지 않아도 값은 덮어씌어 질 수 있어서 딱히 안비워도 되긴하다. 그러나 꼭 3을 따로 빼내야만 계속해서 3을 가지고 비교를 할 수 있다.).
   1. 빼낸 3을 이미 정렬된 앞의 서브 배열과 비교하며 적절한 위치에 삽입시킨다. 위의 과정과 동일하다. 여기서 눈여겨 볼 점은 이미 정렬된 서브 배열의 마지막 요소부터 비교하던지 첫 요소부터 비교하던지는 크게 중요하지 않다는 점이다! 하지만 상황에 따라 정 반대의 성능을 나타 낼 수가 있다. 왜일까? 만약 이미 오름 차순으로 정렬이 되어있는 요소를 그대로 오름 차순으로 정렬 할 경우, 우리가 하고 있는 방식(서브 배열의 마지막 요소부터 비교하는 방식)대로 라면 항상 서브 배열과 비교 하자마자 삽입될 위치가 정해진다. 예를 들어 1 2 3 4 5를 정렬 할 때, 3을 선택해서 삽입하려고 한다면, [1,2]로 된 서브배열에서 3의 위치를 찾아야 한다. [1,2]의 마지막 요소 2와 3을 비교하면 3이 크다. 한 번더, [1,2,3] 과 4의 관계도 마찬가지다. 처음 3과 4를 비교하면 바로 4의 위치가 나온다. 그렇다면 이번엔 5 4 3 2 1 로 구성된 요소를 오름차순으로 정렬해보자. 이때도 서브 배열의 마지막 요소부터 비교한다면 항상 끝까지 비교를 끝마쳐야 자신의 위치를 찾을 수 있다. 예를 들어 정렬이 완료된 서브 배열 [3,4,5]가 있고 이번 차례는 2라면, 5와 2를 비교, 4와 2를 비교, 3과 2를 비교해야만 자신의 위치가 가장 첫 자리로 배정된다. 이럴 땐 서브 배열의 첫 요소부터 비교하게끔 알고리즘을 작성하면 된다.
4. 이후 과정인 1 8 7 을 정렬하는 과정은 같은 과정의 반복이므로 패스!

코드

def insertionSort(x):
    for size in range(1, len(x)): # 삽입할 요소를 하나씩 선택하기 위한 루프
        val = x[size]
        i = size
        while i > 0 and x[i-1] > val: # 정렬된 서브배열과 비교하는 루프
            x[i] = x[i-1]
            i -= 1
        x[i] = val

시간복잡도

• 최선 : O(n)
• 평균 : O(n^2)
• 최악 : O(n^2)

선택 정렬이란?

선택 정렬은 배열의 길이만큼 루프를 돌며, 루프를 돌 때 마다 가장 작은 값을 “선택!” 해서 맨 왼쪽으로 옮겨가며 정렬한다. 따라서 한 번 루프를 돌때 마다 매번 최소값이 왼쪽에 정렬 된다(물론 내림차순 정렬이라면 최대값을 왼쪽으로 보내면 된다). 코드를 보면 이해가 쉽다.

과정

위와 같이 정렬 되어있지 않은 배열이 있다. 정렬을 하는과정은 아래 과정의 반복이다.

1. 정렬된 배열을 제외하고 모든 요소를 방문하여 최소값을 찾는다.

2. 찾은 최소값을 정렬되지 않은 범위에서 가장 왼쪽에 놓는다. (이렇게 되면 루프 한번에 한개의 요소가 정확히 정렬 된것이다. 제일 작은 것이 제일 왼쪽에 왔으니까!)

3. 두 번째 루프부터는 정렬된 초록색 배열 부분을 제외하고 1번 2번을 동일하게 진행한다.

즉 이렇게 배열 길이만큼의 루프를 돌며 반복하면 모든 요소가 정렬된다.

코드

def selection(arr):
  for i in range(len(arr)-1):
    minVal = arr[i] # 루프를 돌 때 마다 일단 최소값을 배열되지 않은 것들중 맨 처음 요소로 잡는다.
    index = i # 최소값을 가진 인덱스
    for j in range(i+1,len(arr)):
      if minVal > arr[j]:
        minVal = arr[j]
        index = j
    arr[index], arr[i] = arr[i], minVal 
  return arr
print(selection([5,4,3,2,1]))

시간복잡도

• 평균 : O(n^2)
• 최악 : O(n^2)

프로그래머스같은 경우는 입력이 자동으로 되기 때문에 함수만 작성하면 된다. 그러나 구름ide 또는 백준 알고리즘 같은 경우 테스트 케이스 입력을 받기 위한 코드를 작성해야한다. Node.js로 입력을 받는데 헤맨 부분이 있어 입력 받는 방법을 간단하게 정리해보기로 했다.

readline

백준 사이트에서 javascript로 풀어진 몇 예제를 보면

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split(' ');

이렇게 입력을 받는 것을 볼 수가 있는데, 여기서 경로는 알고리즘 사이트마다 다르기 때문에 보편적으로 사용할 수 없다.

인터넷에 예제들을 보면 대부분 readline을 사용하고 있다. 기본적인 형태는 아래와 같다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.on("line", function(line) {
  console.log("hello !", line);
  rl.close();
}).on("close", function() {
  process.exit();
});

위 코드는 사용자로 부터 한 줄의 입력만 받고 프로그램이 끝나게 된다. 만약 위의 코드에서

rl.close()

부분이 없다면 무한으로 입력을 받으며 받은 만큼 실시간으로 console.log를 찍는다.

간단한 예제로 두 수를 공백으로 구분지어 입력받은 후 합을 구해 출력하는 코드를 살펴보자.

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];

rl.on('line', function (line) {
    input = line.split(' ').map((el) => parseInt(el));
  })
  .on('close', function () {
    console.log(input[0] + input[1]);
    process.exit();
  });

// 입력 : 1 2
// 출력 : 3

여기서 알아두어야 할 점은, 이 코드를 콘솔에서 실행하게 되면 close 이벤트에 걸리지를 않아서 console.log가 찍히지 않고, 입력만 계속해서 받게 된다. 그 이유는 콘솔에서 실행했기 때문이다. 콘솔에서는 interactive shell이 계속 열려있기 때문에 자동으로 close가 호출되지 않는다. 그러나 이 코드를 구름 ide에서 실행하게 되면 EOF에 걸리게 되어 정상적으로 console.log가 찍힌다.

(백준 사이트나 구름 IDE 같은 경우 알고리즘을 테스트하기 위한 테스트 데이터들이 파일에 존재한다. 콘솔에서 실행하면 키보드로부터 입력을 받기 때문에 계속해서 입력 이벤트를 대기하게 되지만, 파일을 받게 되는 경우에는 파일의 데이터가 끝이나면 자동으로 EOF에 걸려 close되어 코드가 끝나는 것이다.)

만약 두 줄, 세 줄의 입력을 받아야 한다면 아래와 같이 할 수 있다.

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];

rl.on('line', function (line) {
    input.push(line)
  })
  .on('close', function () {
    console.log(input);
    process.exit();
});

콘솔에서 close를 하는 방법

일반적으로 콘솔에서는 계속해서 입력 이벤트를 기다리고 있기 때문에 close가 실행되지 않는다. 그러나 리눅스의 경우 콘솔에서 ctrl + D 를 입력하면 EOF에 걸리게 된다(윈도우라면 gitbash를 통해 node파일을 실행시킨 후 입력이 다 되었다면 ctrl + D를 누르면 된다). 위의 코드의 경우 1 -> enter -> 2 -> ctrl + D 를 입력하면 된다.

결론

입출력이 간단한 경우에는 크게 무리가 없을 것 같지만 입력이 상당히 많아질 경우 복잡해 질 것 같긴하다. 사람들이 js로 알고리즘을 잘 안푸는 이유가 있긴 있는 것 같다ㅠㅠ

javascript 라이브러리들을 사용하다보면, react-redux의 connect 함수와 같이 함수의 인자를

export default connect(mapStateToProps)(TodoApp)

함수(인자1)(인자2)

와 같이 받는 함수들이 꽤 있다. 이렇게 하는 이유와, 이 것의 용어, 내부 동작 방식이 궁금해서 여러 포스트를 보고, 유인동 님의 강의를 보면서 살짝 정리해 보았다. 우선 이 것의 용어는 Currying이다.

Currying

Adam Bene의 블로그에 따르면 currying이란 두개 이상의 인자를 갖는 함수를 인자를 하나만 갖게 하는 함수로 줄여나가는 방법이라고 한다.

f(n, m) --> f'(n)(m)

const multiply = (n, m) => (n * m)
multiply(3, 4) === 12 // true

// ------ currying -------

const curryedMultiply = (n) => {
  return (m) => multiply(n, m)
}
const triple = curryedMultiply(3)
triple(4) === 12 // true

우선 위의 curryedMultiply함수를 보면 처음으로 인자 n을 받고, n을 간직하고 있는 새로운 익명 함수를 반환하게 된다. 즉, 클로저가 된다.

조금 일반화 해서 보자면, curry함수는 아래와 같을 수 있다.

function _curry(fn) {
  return function(a) {
    return function(b) {
      return fn(a, b)
    }
  }
}

fn은 우리가 _curry함수를 호출할 넘겨줄 함수가 된다. 두 가지 수를 더하는 add 함수를 만들고자 할 경우 우리는 _curry의 힘을 빌려 이렇게 만들 수 있다.

const add = _curry((a,b) => (a + b))

이제 add의 구현체 부분은 곧

function(a) {
  return function(b) {
    return fn(a, b)
  }
}

이 부분인 것이며 이는 인자를 하나 받는다는 뜻이다. 결과적으로 우리는

add(10)(5)

와 같이 할 수 있다.

그런데 조금만 더 생각해 보면 add(a,b) 와 add(a)(b)를 혼용해서 사용할 수 있는 방법이 있다.

function _curry(fn) {
  return function(a,b) {
    return arguments.length == 2 ? fn(a,b) : function (b) { return fn(a,b); }
  }
}

이렇게 arguments의 갯수를 파악해서 조건에 따라 함수를 즉시 실행할지, 다른 함수를 반환할지를 결정하면 된다.

만약 a와 b의 위치를 변경하고 싶다면, 즉 b가 좌변에 오도록 하고 싶다면 _curryr이라는 함수를 아래와 같이 만들면 된다.

function _curry(fn) {
  return function(a,b) {
    return arguments.length == 2 ? fn(a,b) : function (b) { return fn(b,a); }
  }
}

사실 여기까지만 보아서는 왜 curry를 사용하는지, 어떤 이점이 있는지 몰랐다. 그냥 add함수를 만들고 사용하면 되지 왜 굳이 currying을 할까? 라는 생각이 가시질 않았다. 이후에 _get함수를 사용하는 사례를 보니 조금은 알 것 같았다.

_get함수는 어떤 object에 key값으로 접근하는 간단한 함수로 아래와 같다.

users = [{name:'leezep', age: '18'}, {name: 'elecoder', age: '15'}];

const _get = _curryr((obj,key) => (obj == null ? undefined : obj[key]));

이렇게 했을 경우 우리는 아래처럼 _get을 활용할 수 있다.

_get(user[0], 'name');
// 또는
_get('name')(user[0]);

이 말은 즉,

const get_name = _get('name');

이렇게 할 경우에 get_name은 어떤 객체가 주어지기만 한다면 name을 가져오는 함수가 된다. 즉 currying을 통해 재사용성이 증가하게 되었고 그로인해 생긴 편리한 함수인 것이다. 이 get_name은 object를 인자로 받으면 되니까 map이나 각종 루프에서 활용하면 코드가 훨씬 깔끔해질 것이다. 바로 아래처럼. (_get함수에 인자 하나가 (‘name’)으로 들어가 실행되면 곧 get_name함수이다.)

// _get함수가 없으면 사용할 방법
map(users, (user) => (user.name))

// _get 함수 사용시 깔끔해진 함수
map(
  users, _get('name')
)

참고자료

• JavaScript에서 커링 currying 함수 작성하기

• 유인동 님의 강의

• Adam Bene의 블로그

증상

lambda로 서버를 운영하는 도중 multer-s3를 사용해 이미지를 S3로 업로드를 할 때, 이미지는 정상적으로 올라가지만 올라간 파일을 열어보면 “이 형식은 지원되지 않는 형식인 것 같습니다” 라는 에러가 떴었다. local 환경의 서버를 통한 이미지는 잘 열렸는데 람다를 통해서 업로드 된 파일만 읽히지 않는 것이었다.

원인

lambda는 기본적으로 binary type support가 되지 않는다고 한다. 따라서 api gateway에 Binary type support를 설정해 줘야 했다.

해결

수동으로 Binary support를 추가하는 방법도 있고 플러그인을 설치해 serverless-framwork에 설정하는 방법이 있었다. 나는 플로그인으로 설정했다.

플러그인은 serverless-apigw-binary 이고 npm이나 yarn으로 설치할 수 있다. 이후 serverless.yml에 추가 설정을 아래와 같이 했다

custom:
  apigwBinary:
    types:           #list of mime-types 
      - '*/*'

그리고 aws-serverless-express에서 설정해 줘야 할 것들이 있다. 이 라이브러리의 깃헙 이슈에서 얻은 정보로 아래와 같이 설정해 줘야 한다.

// lambda.js
'use strict'
const awsServerlessExpress = require('aws-serverless-express')
const app = require('./app')

// NOTE: If you get ERR_CONTENT_DECODING_FAILED in your browser, this is likely
// due to a compressed response (e.g. gzip) which has not been handled correctly
// by aws-serverless-express and/or API Gateway. Add the necessary MIME types to
// binaryMimeTypes below, then redeploy (`npm run package-deploy`)
const binaryMimeTypes = [
  'application/javascript',
  'application/json',
  'application/octet-stream',
  'application/xml',
  'font/eot',
  'font/opentype',
  'font/otf',
  'image/jpeg',
  'image/png',
  'image/svg+xml',
  'text/comma-separated-values',
  'text/css',
  'text/html',
  'text/javascript',
  'text/plain',
  'text/text',
  'text/xml'
]
const server = awsServerlessExpress.createServer(app, null, binaryMimeTypes)

exports.handler = (event, context) => awsServerlessExpress.proxy(server, event, context)

참고 자료

• aws-serverless-express 이슈
• Does not play nice with multer