문제


숫자 1, 2, 3을 이용하여 숫자 N을 만드는 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들어, N이 4일 경우에는 다음의 7가지 경우가 존재한다. 단, 경우의 수가 매우 많을 수 있으므로, 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

 

입력


첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )  

출력


1, 2, 3을 이용하여 N을 만들 수 있는 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.  

예제 입력

4

예제 출력

7

 

예제 입력

200

예제 출력

290816

 

출처


Taejon 2001 PC번  






문제 풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution01.java







Concepts

핵심은, webpack은 모던 JavaScript 어플리케이션의 정적 모듈 번들러라는 것이다. webpack 이 어플리케이션을 처리할 때, 내부적으로 모듈 디펜던시 그래프를 생성하여 하나 또는 그 이상의 번들을 생성한다.

4.0.0 버전 이후로, webpack 은 프로젝트를 빌드하기 위해 configuration file 이 필요 없다. 그럼에도 딱 맞는 설정을 할 수 있다.

webpack을 시작하기 위해서는, 핵심 컨셉을 이해할 필요가 있다.


  • Entry
  • Output
  • Loaders
  • Plugins
  • Mode
  • Browser Compatibility

이 문서는 high-level 오버뷰 이다. 


Entry

entry point는 모듈 webpack 이 내부적인 디펜던시 그래프를 만들기 시작하는 지점이다. webpack은 entry point 와 직접적, 간접적 디펜던시가 있는 다른 모듈과 라이브러리를 구분 할 것이다.

기본 값은 ./src/index.js 이지만, webpack configuration 에 entry 프로퍼티를 설정하여 다른 entry point 값(들)을 명시 할 수 있다.
예를 들면,

webpack.config.js

const path = require('path');

module.exports = {
  entry: './path/to/my/entry/file.js',
  output: {
    path: path.resolve(__dirname, 'dist'),
    filename: 'my-first-webpack.bundle.js'
  }
};

Output

output 프로퍼티는 webpack 에게 번들 파일들을 생성할 위치와 이름을 알려준다. 기본적으로 ./dist/main.js 이 주요 출력 파일이고 ./dist 폴더는 다른 파일들의 기본폴더이다.

설정으로 output 필드를 명시하여 설정할 수 있다.

webpack.config.js

const path = require('path');

module.exports = {
  entry: './path/to/my/entry/file.js',
  output: {
    path: path.resolve(__dirname, 'dist'),
    filename: 'my-first-webpack.bundle.js'
  }
};


Loaders

webpack은 JavaScript 와 JSON 파일만 이해하는 반면, Loader는 다른 문법의 파일을 (예를들면, TypeScript, CoffeeScript ..) 유요한 JavaScript 파일로 변환하여 webpack이 디펜던시 그래프에 추가할 수 있도록 한다.


크게보면, loaderwebpack 구성에서 다음 두 가지 속성을 가진다.
  1. test 속성은 변환되어야하는 파일 또는 파일들을 나타낸다
  2. use 속성은 변환을 수행하는데 사용해야만 하는 loader 를 나타낸다.

webpack.config.js

const path = require('path');

module.exports = {
  output: {
    filename: 'my-first-webpack.bundle.js'
  },
  module: {
    rules: [
      { test: /\.txt$/, use: 'raw-loader' }
    ]
  }
};


위의 설정에서 정의된 rules 속성은 두가지 프로퍼티가 요구된다. test 와 use

이것은 webpack의 컴파일러에게 다음과 같은 의미를 전달한다

헤이 webpack~

import require() 의 경로에서 .txt 로 리졸브되는 경로를 발견하면, 

번들에 추가하기 전에 raw-loader 를 사용하여 변환해줘


Plugins

loader 가 특정 타입의 모듈을 변환하는데 사용되는반면, 플러그인은 번들 최적화, 자원 관리, 환경변수 주입 등과 같은 좀 더 넓은 범위의 일들을 수행하는데 활용될 수 있다.

플러그인을 사용하기 위해서는, require()를 사용하여 로드하고 그것을 plugins 배열에 추가해야 한다. 
대부분의 플러그인들은 옵션을 통해 커스터마이징 가능하다. 서로다른 목적으로 하나의 플러그인을 여러번 사용할 수 있으므로, 항상 new 연산자로 플러그인을 호출하여 인스턴스를 생성해야 한다.


webpack.config.js

const HtmlWebpackPlugin = require('html-webpack-plugin'); //installed via npm
const webpack = require('webpack'); //to access built-in plugins

module.exports = {
  module: {
    rules: [
      { test: /\.txt$/, use: 'raw-loader' }
    ]
  },
  plugins: [
    new HtmlWebpackPlugin({template: './src/index.html'})
  ]
};

위의 예에서는, html-webpack-plugin 이 모든 생성되는 번들을 자동적으로 인젝팅하여 어플리케이션에 HTML 파일을 생성한다.


webpack은 많은 플러그인을 제공한다.

webpack 설정에서 플러그인의 사용은 간단하지만, 좀 더 유심히 봐야할 경우가 있다.  Learn more about them here.


Mode

mode 파라미터를 development, production 또는 none 으로 설정하면, 각 환경에 맞는 빌트인 된 webpack 최적화를 활성화 할 수 있다.
기본값은 production 이다.

Learn more about the mode configuration here and what optimizations take place on each value.


Browser Compatibility

webpack 은 IE8 이하를 제외한 모든 브라우저를 지원한다.
webpack import()와 requrie.ensure()를 위해 Promise가 필요하다. 만약 오래된 브라우저 지원을 원한다면, 저 표현식을 사용하기 전에 polyfill 을 로드해야 한다.


'WEB > Webpack' 카테고리의 다른 글

webpack 이란 무엇인가  (1) 2019.01.15

webpack

JavaScript 모듈화를 지원하기 위해 태어난 도구. 프레임웤.

webpack 은 모듈 시스템 지원 외에도, 로더, 빠른 컴파일 속도 등 장점이 많다.

Node.js 가 설치된 환경에서 실행되는데, 사용법은 아래와 같다.


npm install webpack -g


webpack이 설치되면 엔트리 파일 및 번들 파일 형식으로 명령어를 실행하여 모듈을 컴파일 한다.

webpack ./entry.js bundle.js


webpack 은 컴파일 시 엔트리 파일을 시작으로, 디펜던시가 있는 다른 파일들을 엮어서 하나의 번들 파일을 만든다.

이 묶여진 번들 파일을 HTML 에서 로딩하기만 하면 전체 모듈을 사용할 수 있다.


그림 1 컴파일 과정


엔트리 파일이 여러개 일 경우는 엔트리 파일마다 번들 파일이 생성된다.

그림 2 엔트리 파일이 여러 개일 때의 컴파일 과정


컴파일 시 --watch 옵션을 사용하면, 모듈이 변경됨을 감지하여 자동으로 컴파일 한다.

webpack --watch ./entry.js bundle.js


webpack config

webpack 을 사용하여 컴파일 할 때 명령어 옵션이 많거나 입력할 내용이 많으면 매우 불편하다.
따라서 이런 입력 내용들을 설정 파일을 만들어 관리 할 수 있다.

module.exports = { context: __dirname + '/app', // 모듈 파일 폴더 entry: { // 엔트리 파일 목록 app: './app.js' }, output: { path: __dirname + '/dist', // 번들 파일 폴더 filename: '[name].bundle.js' // 번들 파일 이름 규칙
}

이런 형태로 webpack.config.js 파일을 작성하고 아래와 같이 명령어만 입력하면 컴파일이 된다.

webpack

로더

webpack 은 다양한 로더 라이브러리를 지원한다.

예를들면 less 로더는 .less 파일을 순수 스타일 파일인 .css 로 로딩할 수 있도록 도와준다.
vue 로더는 .vue 파일을 순수 HTML + JavaScript + CSS 파일로 로딩할 수 있도록 도와준다.

ECMAScript 2015 를 사용할 수 있게 컴파일 하는 Babel 도 사용할 수 있다.





참고


'WEB > Webpack' 카테고리의 다른 글

webpack 주요 컨셉 알아보기  (0) 2019.01.16

회고

커스텀 테스트 케이스 만들 때 실수하지 말자.
점화식은 비교적 간단하게 구현했는데, 테스트 케이스 답을 잘못 생각해서 계속 헤맸던 문제. 반성하자.

노드가 300개 이하이므로, o(n²) 이어도 90000 이므로 1초 내로 끝남.
만약 n <= 300,000 이라면??



풀이


문제

N개의 도시가 동쪽에서 서쪽으로 순서대로 위치해 있다. 제일 동쪽에 있는 도시는 1번 도시이며, 제일 서쪽에 있는 도시는 N번 도시이다.

당신은 이와 같은 도시 중에서 M개 이하의 도시를 지나는 여행을 계획하려 한다. 여행 경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝나야 한다. 물론 이 두 도시도 M개의 도시에 포함된다. 당신은 시차에 매우 민감하기 때문에, 한 번 서쪽으로 이동했다가 다시 동쪽으로 이동하면 몸이 대단히 아프다. 그래서 당신은 계속 서쪽으로만, 즉 도시 번호가 증가하는 순서대로만 이동하기로 하였다.

한편, 모든 도시에서 다른 모든 도시로 이동할 수 있는 건 아니다. 각각의 도시에서 다른 도시로 이동할 때에는 비행기를 타고 이동해야 하는데, 때로는 비행 항로가 개설되지 않았을 수도 있다. 또한 당신은 비행기를 아무렇게나 타려는 것이 아니라, 최대한 맛있는 기내식만 먹으면서 이동하려 한다(사실 이게 여행의 목적이다).

항로 개설 여부와 해당 항로에서 제공되는 기내식의 점수가 주어졌을 때, 먹게 되는 기내식의 점수의 총 합이 최대가 되도록 하시오.

입력

첫째 줄에 N(1≤N≤300), M(2≤M≤N), K(1≤K≤100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1≤a, b≤N, 1≤c≤10,000)가 주어진다. 이는 a번 도시에서 b번 도시로 이동하는 항로가 있고, 서비스되는 기내식의 점수가 c점이라는 의미이다. 서쪽에서 동쪽으로 이동하는 항로가 입력될 수도 있고, 같은 도시 쌍 사이에 항로가 여러 개 있을 수도 있지만, 날아다니다 다시 원래 도시로 돌아오는 a=b 와 같은 입력은 없다.

출력

첫째 줄에 기내식 점수의 총 합의 최댓값을 출력한다.

예제 입력 1 

3 3 5
1 3 10
1 2 5
2 3 3
1 3 4
3 1 100

예제 출력 1 

10































소스


회고

입력이 무려 백만!! 헐헐헐 1,000,000!!
기존 O(n²) 알고리즘으로는 불가능 하다.
텅 빈 수열에서 시작해 숫자를 하나씩 추가해 나가며 각 길이를 갖는 증가 수열 중 가장 마지막 수가 작은 것은 무엇인지를 추적한다.

즉, dp[i] = 지금까지 만든 부분 배열이 갖는 길이 i 인 증가 부분 수열 중 최소의 마지막 값.
이분검색을 하는 과정이 필요하므로, O(nlgn) 으로 가능

풀이


문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {1020, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4






































소스


회고

재귀함수 리턴값이 수열의 길이가 아닌, 수열의 합

입력의 크기가 1,000 이하이므로 O(n²) 으로 가능



풀이


문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 25060, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력 1 

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1 

113





































소스

https://github.com/JK921/icandoit/blob/develop/dp/src/Solution11055.java


회고

입력의 크기가 1,000 이하 이므로 O(n²) 의 알고리즘으로 가능.
dp[n] = max(dp[n], dp[n+k] + 1) (if, num[n] < dp[n+k])

memoization 시, 초기값을 -1 로 채워서, 꼭 계산 여부를 체크하도록..

풀이

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {1020, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.


예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4




























소스

https://github.com/JK921/icandoit/blob/develop/dp/src/Solution11053.java

탐욕법 (greedy method)

가장 직관적인 알고리즘 설계 패러다임

우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고,
각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없다.
But, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택 하는 방법.

주의할점
탐욕적 알고리즘은 많은 경우 최적해를 찾지 못함.

탐욕적 알고리즘이 사용되는 경우

  1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우
    탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용함.

  2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기가 너무 어려운 경우
    최적해 대신 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있음.


프로그래밍 대회에서는 주로 1번 용도로만 사용됨.
=> 근사해를 찾는 문제는 주어지지 않음..


탐욕법 vs 동적 계획법

사실, 탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있음.

 탐욕법

 

 동적 계획법

하나의 경우만 고려해서 답을 얻는 방법

  

모든 경우의 수를 다 찾아 답을 얻는 방법


따라서 동적 계획법으로 탐욕법이 고려하는 경우를 커버하기 때문에 가능함.

하지만 동적 계획법에 필요한 메모리나 시간이 과도하게 큰 경우는 탐욕법을 사용해야 할 수도 있음.

'스터디 > 알고리즘 정리' 카테고리의 다른 글

동적 계획법 테크닉 (not yet)  (0) 2018.12.02
동적 계획법 문제 풀이 (not yet)  (0) 2018.12.02
동적 계획법  (0) 2018.12.01
분할 정복  (0) 2018.11.27
알고리즘 시간 복잡도  (0) 2018.11.26

+ Recent posts