[Algorithm] Codility Lesson 6 Sorting - NumberOfDiscIntersections

We draw N discs on a plane. The discs are numbered from 0 to N − 1.
A zero-indexed array A of N non-negative integers, specifying the radiuses of the discs, is given.
The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs
have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:
    A[0] = 1
    A[1] = 5
    A[2] = 2
    A[3] = 1
    A[4] = 4
    A[5] = 0

There are eleven (unordered) pairs of discs that intersect, namely:
    - discs 1 and 4 intersect, and both intersect with all the other discs;
    - disc 2 also intersects with discs 0 and 3.

Write a function:
    class Solution { public int solution(int[] A); }

that, given an array A describing N discs as explained above,
returns the number of (unordered) pairs of intersecting discs.
The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Assume that:
    - N is an integer within the range [0..100,000];
    - each element of array A is an integer within the range [0..2,147,483,647].

Complexity:
    - expected worst-case time complexity is O(N*log(N));
    - expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

=======================================================================

우리는 평면에 N개의 디스크를 그린다. 디스크 들은 0 부터 N - 1로 번호가 매겨진다.
디스크의 반지름으로 구분되는 N개의 음수가 아닌 정수 배열 A가 주어진다.

J번째 디스크는 중앙이 (J, 0)이고 반지름 A[J] 으로 그려진다.

J ≠ K이고 J번째 디스크와 K번째 디스크가 적어도 하나의 공통 지점이 있다면(디스크에 경계선도 포함한다고 가정한다.)
J번째 디스크와 K번째 디스크가 '교차'(intersect)한다고 말한다.

N = 6이고 A가 다음과 같다면 디스크들이 그려진 도형은 아래처럼 보여진다:
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0

11개의 디스크가 교차하는 쌍이 11개(정렬되지 않은) 있다:
디스크 1과 디스크 4는 서로 교차하고, 다른 모든 디스크들과 교체한다;
디스크 2도 디스크 0, 디스크 3과 교차한다.

함수 작성:
class Solution { public int solution(int[] A); }
위에 설명한 것 같은 N개의 디스크로 표현되는 배열 A가 주어지고, 교차되는 디스크 쌍의 갯수(정렬되지 않은)를 리턴한다.
교차 쌍이 10,000,000를 초과하면 함수는 -1을 리턴해야 한다.

위에서 본 배열 A가 주어지면, 위에서 설명한 것 처럼 함수는 11을 리턴해야한다.

가정:
- N은 [0..100,000] 범위의 정수;
- A의 각 요소는 [0..2,147,483,647] 범위의 정수.

복잡도:
- 최악의 시간 복잡도는 O(N*log(N));
- 최악의 공간 복잡도는 O(N), 입력 공간 제외.

입력된 배열의 요소는 수정할 수 있다.





62%:
https://codility.com/demo/results/trainingEYPYR6-UPQ/



100%:
https://codility.com/demo/results/trainingAF88MJ-ZAP/

[Algorithm] Codility Lesson 6 Sorting - MaxProductOfThree

A non-empty zero-indexed array A consisting of N integers is given.
The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:
    A[0] = -3
    A[1] = 1
    A[2] = 2
    A[3] = -2
    A[4] = 5
    A[5] = 6

contains the following example triplets:
    - (0, 1, 2), product is −3 * 1 * 2 = −6
    - (1, 2, 4), product is 1 * 2 * 5 = 10
    - (2, 4, 5), product is 2 * 5 * 6 = 60

Your goal is to find the maximal product of any triplet.

Write a function:
    class Solution { public int solution(int[] A); }
that, given a non-empty zero-indexed array A, returns the value of the maximal product of any triplet.

For example, given array A such that:
    A[0] = -3
    A[1] = 1
    A[2] = 2
    A[3] = -2
    A[4] = 5
    A[5] = 6
the function should return 60, as the product of triplet (2, 4, 5) is maximal.

Assume that:
    - N is an integer within the range [3..100,000];
    - each element of array A is an integer within the range [−1,000..1,000].

Complexity:
    - expected worst-case time complexity is O(N*log(N));
    - expected worst-case space complexity is O(1),
    beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.


==================================================================


N개의 정수로 구성된 비어 있지 않은 배열 A가 주어진다.
세 요소 (P, Q, R)의 'product'(곱)는 A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N)와 같다.

예를 들어 배열 A가 다음과 같다면:
    A[0] = -3
    A[1] = 1
    A[2] = 2
    A[3] = -2
    A[4] = 5
    A[5] = 6

아래의 예시 세 요소를 포함하고:
- (0, 1, 2), product 는 −3 * 1 * 2 = −6 이다.
- (1, 2, 4), product 는 1 * 2 * 5 = 10 이다.
- (2, 4, 5), product 는 2 * 5 * 6 = 60 이다.

목표는 세 요소의 product 중 가장 큰 것을 찾는 것이다.

함수 작성:
    class Solution { public int solution(int[] A); }
N개의 정수로 구성된 비어 있지 않은 배열 A가 주어지고, 세 요소의 product 중 최대 값을 리턴한다.

예를 들어, 배열 A가 다음과 같다면:
    A[0] = -3
    A[1] = 1
    A[2] = 2
    A[3] = -2
    A[4] = 5
    A[5] = 6
세 요소 (2, 4, 5)의 product 가 최대 값 이므로 함수는 60을 리턴해야 한다.

가정:
    - N은 [3..100,000] 범위의 정수이다.
    - 배열 A의 각 요소는 [−1,000..1,000] 범위의 정수이다.

복잡도:
    - 최악의 시간 복잡도는 O(N*log(N));
    - 최악의 공간 복잡도는 O(1), 입력 공간 제외

배열의 요소는 수정할 수 있다.


100%:
https://codility.com/demo/results/trainingYWMGGK-VSR/

[GitHub] GitHub Page 도메인 연결하기

다른 사람 질문에 답변하느라 진행해본 김에 필요한 사람이 있을듯 싶어 작성함

https://help.github.com/articles/setting-up-your-pages-site-repository/ 보고 진행했는데 간단히 요약하면

---

1. www.xxx.kr 로 연결 하려면

1) GitHub 쪽 준비

• 리파지토리 루트에 CNAME 라는 이름의 파일을 생성해서 www.xxx.kr 라는 내용을 추가

2) DNS 설정

• Type: CNAME / NAME: www / value: 닉네임.github.io

---

2. xxx.kr 로 연결 하려면

1) GitHub 쪽 준비

• 리파지토리 루트에 CNAME 라는 이름의 파일을 생성해서 xxx.kr 라는 내용을 추가
  

2) DNS

• Type: A / NAME: xxx.kr / value: 192.30.252.153
  
• Type: A / NAME: xxx.kr / value: 192.30.252.154 (둘 다 추가)
  

3) (선택사항) 추가로 www.xxx.kr 로도 연결하려면

• Type: CNAME / NAME: www / value: 닉네임.github.io 도 추가

---

CloudFlare 기준 설정 후 5~10분 이내에 금방 연결 확인되었다.

hangaebal.github.io <- hangaebal.tk

[Node.js] GitHub API 활용 (2)

GitHub API 활용 (2)

ajax 방식에서 페이지 갱신 방식으로 변경

routes/github.js 수정

• 데이터를 직접 리턴하던 형태에서, 뷰와 데이터를 같이 리턴하도록

...
-   res.send(data);
+   res.render('github', {data: data, q: req.query.q});
...

views/github.jade 수정

• jade를 거의 처음 사용하지만 레퍼런스 참고하니 크게 어려울 것은 없었다.
• 뷰 코드 작성 시 태그를 열고 닫는 등의 단순 반복 타이핑이 확 줄었다.

현재까지의 코드 :

https://github.com/hangaebal/dictionary-node-express/tree/github-api2

[Algorithm] Codility Lesson 6 Sorting - Distinct

Write a function
    class Solution { public int solution(int[] A); }

that, given a zero-indexed array A consisting of N integers,
returns the number of distinct values in array A.

Assume that:
    - N is an integer within the range [0..100,000];
    - each element of array A is an integer within the range [−1,000,000..1,000,000].

For example, given array A consisting of six elements such that:
    A[0] = 2    A[1] = 1    A[2] = 1
    A[3] = 2    A[4] = 3    A[5] = 1
the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.

Complexity:
    - expected worst-case time complexity is O(N*log(N));
    - expected worst-case space complexity is O(N),
    beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

==============================================================

함수 작성:
    class Solution { public int solution(int[] A); }

N개의 정수로 구성된 배열 A가 주어지고, 배열 A의 값의 수를 리턴한다.

가정:
    - N은 [0..100,000] 범위의 정수;
    - 배열의 각 요소는 [−1,000,000..1,000,000] 범위의 정수

예를 들어 다음과 같은 여섯 요소로 구성된 배열 A가 주어진다면:
    A[0] = 2    A[1] = 1    A[2] = 1
    A[3] = 2    A[4] = 3    A[5] = 1
함수는 3을 리턴 해야한다, 왜냐하면 배열 A에 별개의 값이 '1, 2, 3' 3개 있기 때문이다.

복잡도:
    - 최악의 시간 복잡도는 O(N*log(N));
    - 최악의 공간 복잡도는 O(N), 입력 공간 제외

배열의 요소는 수정할 수 있다.





100%:
https://codility.com/demo/results/trainingT5QPBD-7CC/

[Node.js] Github API 활용 (1)

만들던 앱을 활용해서 GitHub API 활용

네이버 백과사전 검색 API 결과가 기대했던 것과 달라서 계속 개선해나가기가 아쉬워졌다.
(검색 결과가 특정 길이 이상 출력되지 않고 링크로 직접 가서 확인해야 한다든지..)

다른 API 중에 괜찮은 게 없을까 찾다가 GitHub API를 선택했다.

리파지토리 검색 API 적용

• https://developer.github.com/v3/repos/ 페이지에 잘 정리되어 있다.
• 헤더에 User-Agent 값이 필수라는 것 이외에는 별다른 특이사항은 없다.
• document에서는 curl을 사용하고 있으나 curl node.js 라이브러리 중 맘에 드는 것을 찾지 못해서 기본 모듈인 https를 사용했다.

app.js 에 routes 추가

...
app.use('/github', require('./routes/github'));
...

routes/github.js 파일 생성


views/github.jade 파일 생성


현재까지의 소스
https://github.com/hangaebal/dictionary-node-express/tree/github-api1

[Node.js] Express.js 활용 사전 앱 만들기 (3)

뷰 적용 및 API 결과 처리

1. XML parser 설치
   
   • 네이버 API가 xml 형태로만 리턴하므로 XML 처리 라이브러리 설치
   • npm install --save xml2js
   
   
   
   
2. 뷰 수정
   
   • public/stylesheets/style.css (기존 css 제거)
   
   
   
   
   
   • layout.jade (bootstrap 사용을 위해 div.container 추가)
   
   
   
   
   
   • dictionary.jade (검색어 입력 부분과 ajax 호출 부분 추가)
   
   
   
   
   
3. dictionary.js 수정
   
   
   
   

현재까지의 코드 :
https://github.com/hangaebal/dictionary-node-express/tree/blog3

[Node.js] Express.js 활용 사전 앱 만들기 (2)

사전 API 적용

다음에 검색 API는 있지만 사전 검색은 없어서 사용 불가

네이버에는 사전 검색 API를 지원하고 있다. 처리한도가 25,000 / 일 이지만 개발 용도로 쓰기에 무리가 없어서 선택

---

API 개발 가이드 내용에 따라 진행해보자

1. 개인 애플리케이션을 등록한다. (ID, SECRET 발급에 필요)
   
   
   • 페이스북 계정 개발자 등록시 처럼 네이버 계정에 휴대폰 인증이 최초 1회 필요하다고 한다. 인증을 진행한다.
   • 대부분 기본적인 정보를 입력하고 사용할 API 권한관리에서 검색 API를 잊지말고 체크한다.
   • 이후 내 애플리케이션> 해당 앱 메뉴에서 Client ID / Client Secret 을 확인할 수 있다.
   
   
   
2. API 호출 코드 작성
   
   
   • dictionary.js 파일에 호출 코드를 추가한다.
   • 일단 API 정상 동작을 확인하기 위해 뷰 코드 수정 없이 서버 자체에서 임의의 텍스트(개발)로 검색한 결과를 리턴하게 해보자
   
   

   var express = require('express');
   var router = express.Router();
   
   var https = require('https');
   
   var CLIENT_ID = '발급받은 ID';
   var CLIENT_SECRET = '발급받은 SECRET';
   var API_URI = '/v1/search/encyc.xml?query=';
   
   var options = {
     host: 'openapi.naver.com',
     port: 443,
     path: API_URI,
     method: 'GET',
     headers: {'X-Naver-Client-Id':CLIENT_ID, 'X-Naver-Client-Secret': CLIENT_SECRET}
   };
   
   router.get('/', function(req, res, next) {
     var searchText = encodeURIComponent('개발');
     options.path = API_URI + searchText;
     var apiReq = https.request(options, function(apiRes) {
       console.log('STATUS: ' + apiRes.statusCode);
       apiRes.setEncoding('utf8');
       apiRes.on('data', function (chunk) {
         res.setHeader('Content-Type', 'application/xml');
         res.send(chunk);
       });
     });
     apiReq.end();
   });
   
   module.exports = router;
   

   
   
   • nodemon을 설치했다면 파일 수정시 서버가 자동으로 재시작 된다.
   
   
   
3. 접속 확인
   
   
   • http://localhost:3000/dictionary
   • 정상적으로 API가 호출 되었다면 xml 형태의 결과가 화면에 출력된다.

현재까지의 전체 소스:
- https://github.com/hangaebal/dictionary-node-express/tree/blog2

[Node.js] Express.js 활용 사전 앱 만들기 (1)

개발 환경 준비

1. 먼저 기본 앱 구조를 편하게 잡기 위해 Express generator를 사용한다.
   
   • 이전 글 참조
2. 개발 중 소스 수정시마다 서버 재시작하려면 불편하니 nodemon을 이용
   
   • 개발 dependency로 설정하기 위해 --save-dev 옵션 사용
   • package.json파일에 devDependencies로 따로 관리된다.

   $ npm install nodemon --save-dev
   

   이후 서버 구동은
   

   $ nodemon
   

3. Code Style 확인을 위해 Linter를 사용
   
   • 편집기로 SublimeText3를 사용하고 있어서 SublimeLinter를 선택했다.
   • 설치 순서 : https://github.com/roadhump/SublimeLinter-eslint
   • 설치 후 설정에서 Lint Mode를 Save only로 해두면 저장할 때마다 표시를 해준다.
4. 의존성 관리를 위해 bower를 설치
   

   $ npm install bower --save
   

   • bower 패키지 관리를 위해 bower init 커맨드로 bower.json 파일 생성

   $ bower init
   

1. bower를 이용해서 bootstrap(+jquery) 설치
   
   • bootstrap 의존성에 jquery 2.2.4 버전이 포함되어있어서 같이 설치 된다.

   $ bower install bootstrap
   

---

코드 작성

1. app에서 bower_components 디렉토리에 접근 가능하도록 app.js에 아래 내용을 추가
   

   app.use(express.static(path.join(__dirname, 'bower_components')));
   

2. 레이아웃에 bootstrap.css 와 jquery를 추가
   
   • views/layout.jade 파일 수정

   doctype html
   html
   head
       title= title
       link(rel='stylesheet', href='/bootstrap/dist/css/bootstrap.min.css')
       link(rel='stylesheet', href='/stylesheets/style.css')
       script(src='/jquery/dist/jquery.min.js')
   body
       block content
   

3. /dictionary 경로로 접근 가능하도록 routes와 view를 추가
   
   1. app.js 파일에 아래 내용 추가 javascript app.use('/dictionary', require('./routes/dictionary'));
   2. routes/dictionary.js 파일 추가 (index.js를 복사해서 약간 수정한다.)
      

      var express = require('express');
      var router = express.Router();
      
      router.get('/', function(req, res, next) {
      res.render('dictionary', {title: 'dic'});
      
      });
      
      module.exports = router;
      

   3. view/dictionary.jade 파일 추가 (마찬가지로 index.jade를 복사해서 수정한다.)
      

      extends layout
      
      block content
        h1 사전
        p Welcome to #{title}
      

4. 접속 확인
   
   • http://localhost:3000/dictionary

아직 사전 관련 기능은 하나도 없지만...일단 앱 기본 토대가 완료 되었다.
현재까지의 소스 https://github.com/hangaebal/dictionary-node-express/tree/blog1

[Algorithm] Codility Lesson 6 Sorting - Triangle

A zero-indexed array A consisting of N integers is given.
A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
    - A[P] + A[Q] > A[R],
    - A[Q] + A[R] > A[P],
    - A[R] + A[P] > A[Q].

For example, consider array A such that:
    A[0] = 10    A[1] = 2    A[2] = 5
    A[3] = 1     A[4] = 8    A[5] = 20
Triplet (0, 2, 4) is triangular.

Write a function:
    class Solution { public int solution(int[] A); }

that, given a zero-indexed array A consisting of N integers,
returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:
    A[0] = 10    A[1] = 2    A[2] = 5
    A[3] = 1     A[4] = 8    A[5] = 20

the function should return 1, as explained above. Given array A such that:
    A[0] = 10    A[1] = 50    A[2] = 5
    A[3] = 1
the function should return 0.

Assume that:
    - N is an integer within the range [0..100,000];
    - each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:
    - expected worst-case time complexity is O(N*log(N));
    - expected worst-case space complexity is O(N),
    beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.


====================================================================


정수 N개로 구성된 배열 A가 주어진다.
만약 3요소 (P, Q, R)가 0 ≤ P < Q < R < N 이고 다음과 같다면 'triangular' 라고 할 수 있다:
    - A[P] + A[Q] > A[R],
    - A[Q] + A[R] > A[P],
    - A[R] + A[P] > A[Q].

예를 들어 배열 A가 다음과 같다면:
    A[0] = 10    A[1] = 2    A[2] = 5
    A[3] = 1     A[4] = 8    A[5] = 20
3요소 (0, 2, 4) 는 triangular 이다.

함수 작성:
    class Solution { public int solution(int[] A); }

정수 N개로 구성된 배열 A가 주어지고, triangular인 3요소가 있다면 1을 리턴, 그렇지 않다면 0을 리턴한다.

예를 들어 배열 A가 다음과 같이 주어지면:
    A[0] = 10    A[1] = 2    A[2] = 5
    A[3] = 1     A[4] = 8    A[5] = 20

함수는 위에 설명한대로 1을 리턴해야한다. 주어진 배열 A 가 다음과 같다면:
    A[0] = 10    A[1] = 50    A[2] = 5
    A[3] = 1
함수는 0을 리턴해야 한다.

가정:
- N은 [0..100,000] 범위의 정수;
- 배열 A의 각 요소는 [−2,147,483,648..2,147,483,647] 범위의 정수

복잡도:
- 최악의 시간 복잡도는 O(N*log(N)).
- 최악의 공간 복잡도는 O(N), (입력 공간 제외)

배열의 요소는 수정할 수 있다.





93%:
https://codility.com/demo/results/trainingYNR6RF-E4N/

100%:
https://codility.com/demo/results/trainingTDQPVB-PZ7/

[npm] 개발 전용으로 npm install (npm install --save develop)

개발 전용으로 npm install 하려면

$ npm install --save-dev 패키지명

package.json에 devDependencies 부분에 따로 관리된다.
 




 


- npm install dev save
- npm install --save dev
- npm install --save 개발


참고:
https://docs.npmjs.com/cli/install

[Algorithm] Codility Lesson 5 Prefix Sums - MinAvgTwoSlice

A non-empty zero-indexed array A consisting of N integers is given.
A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A
(notice that the slice contains at least two elements).
The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice.
To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

For example, array A such that:
    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

contains the following example slices:
- slice (1, 2), whose average is (2 + 2) / 2 = 2;
- slice (3, 4), whose average is (5 + 1) / 2 = 3;
- slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

The goal is to find the starting position of a slice whose average is minimal.

Write a function:
class Solution { public int solution(int[] A); }

that, given a non-empty zero-indexed array A consisting of N integers,
returns the starting position of the slice with the minimal average.
If there is more than one slice with a minimal average,
you should return the smallest starting position of such a slice.

For example, given array A such that:
    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

the function should return 1, as explained above.

Assume that:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−10,000..10,000].

Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

=============================================================================

N개의 정수로 구성된 비어있지 않은 배열 A가 주어진다. 0 ≤ P < Q < N 인 정수 쌍(P, Q)은 배열 A의 'slice'라고 부른다.
(slice 는 최소 두 요소를 포함 한다는 것을 참고)
slice (P, Q)의 평균은 A[P] + A[P + 1] + ... + A[Q] 를 slice의 길이로 나눈 것이다.
정확하게는  (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1) 이다.

예를 들어 배열 A가 다음과 같다면:
    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

다음과 같은 예시 slice를 포함한다.
- slice (1, 2), 평균은 (2 + 2) / 2 = 2;
- slice (3, 4), 평균은 (5 + 1) / 2 = 3;
- slice (1, 4), 평균은 (2 + 2 + 5 + 1) / 4 = 2.5.

목표는 평균이 최소인 slice 의 시작 지점을 찾는것이다.

함수 작성:
class Solution { public int solution(int[] A); }

N개의 정수로 구성된 비어있지 않은 배열 A가 주어지고, 최소 평균을 가지는 slice의 시작 지점을 리턴한다.
만약 최소 평균인 slice가 한 개 이상이라면, slice의 가장 작은 시작 지점을을 리턴해야 한다.

예를 들어 배열 A가 다음과 같다면:
    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

위에서 설명한대로 함수는 1을 리턴해야 한다.

가정:
- N은 [2..100,000] 사이의 정수
- 배열 A의 각 요소는 [−10,000..10,000] 사이의 정수

복잡도:
- 최악의 시간복잡도는 O(N);
- 최악의 공간복잡도는  O(N), (입력 공간 제외)





60%:
https://codility.com/demo/results/trainingMSQBM8-JVJ/

*** length 2 or 3의 슬라이스에서 최소 평균이 나온다는 증명을 활용
(https://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/)

100%:
https://codility.com/demo/results/trainingMQ2A8R-9W2/

[Algorithm] Codility Lesson 5 Prefix Sums - GenomicRangeQuery

DNA 서열은 연속적인 뉴클레오티드의 종류에 대응하여 문자 A ,C, G, T로 구성된 문자열로 나타낼 수 있다.
각 뉴클레오티드는 정수인 'impact factor'를 가지고 있다.
뉴클레오티드 종류 A, C, G, T는 각각 1, 2, 3, 4의 'impact factor'를 가지고 있다.
당신은 다음 몇 가지 쿼리에 답 할 것이다:
주어진 DNA 서열의 특정 부분에 포함 되어있는 뉴클레오티드의 가장 작은 'impact factor'는 무엇인가?

DNA 서열은 N개의 문자로 구성 된 비어있지 않은 문자열 S = S[0]S[1]...S[N-1] 로 주어진다.
각 M개의 정수로 구성된 비어있지 않은 배열 P, Q 안에 M개의 쿼리가 있다.
K번째 쿼리(0 ≤ K < M)는
P[K]와 Q[K] 사이의 DNA 서열이 포함된 뉴클레오티드의 가장 작은 'impact factor'를 찾기를 요구한다.

예를 들어 문자열 S = CAGCCTA 이고 array P, Q 가 다음과 같다면:
    P[0] = 2    Q[0] = 4
    P[1] = 5    Q[1] = 5
    P[2] = 0    Q[2] = 6

M = 3 쿼리들의 답변들은 다음과 같을 것이다:
- 2와 4 사이의 DNA는 뉴클레오티드 G 와 C(두 번)를 포함하고 있다.
'impact factor'는 각각 3, 2이므로 답변은 2이다.
- 5와 5 사이에는 단일 뉴클레오티드 T를 포함하고, 'impact factor'는 4 이므로 답변은 4 이다.
- 0과 6 사이(전체 문자열)에는 모든 뉴클레오티드를 포함하고,
뉴클레오티드 A의 'impact factor'는 1 이므로 답변은 1 이다.

함수 작성:
class Solution { public int[] solution(String S, int[] P, int[] Q); }

N개의 문자로 구성된 비어있지 않은 문자열 S와 M개의 정수로 구성 된 비어있지 않은 배열 P, Q 두 개가 주어지면
모든 쿼리에 대한 연속적인 답변을 나타내는 M개의 정수로 구성된 배열을 리턴한다.

숫자열은 다음과 같아야 한다:
- 구조체 (C),
- 정수 벡터 (C++),
- 레코드 (Pascal),
- 정수 배열 (그 밖의 다른 프로그래밍 언어).

예를 들어 문자열 S = CAGCCTA 이고 array P, Q 가 다음과 같다면:
    P[0] = 2    Q[0] = 4
    P[1] = 5    Q[1] = 5
    P[2] = 0    Q[2] = 6
함수는 위에서 설명한 대로 [2, 4, 1]를 리턴해야 한다.

가정 :
- N 은 [1..100,000] 범위의 정수;
- M 은 [1..50,000] 범위의 정수;
- 배열 P, Q의 각 요소는 [0..N − 1] 범위의 정수;
- 0 ≤ K < M라면 P[K] ≤ Q[K];
- 문자열 S는 알파벳 대문자 A, C, G, T로만 구성된다.

복잡도 :
최악의 시간복잡도는 O(N+M);
최악의 공간복잡도는 O(N) (입력 공간 제외)

배열의 요소는 수정할 수 있다.





75%:
https://codility.com/demo/results/trainingSCPXKP-K28/

100% :
https://codility.com/demo/results/trainingFQSN7X-U64/

[Algorithm] Codility Lesson 5 Prefix Sums - CountDiv

 함수 작성:
 class Solution { public int solution(int A, int B, int K); }
 정수 A, B, K가 주어지고, 범위 [A..B] 안에서 K로 나누어 떨어지는 정수의 값을 리턴
 즉 : { i : A ≤ i ≤ B, i mod K = 0 }

 예를 들어 A = 6, B = 11, K = 2 면, 함수는 3을 리턴해야 한다.
 왜냐하면 범위 [6..11] 안에 2로 나누어 떨어지는 숫자가 6, 8, 10 3개 있기 때문이다.

 가정:
 A,B는 [0..2,000,000,000] 범위의 정수;
 K는 [1..2,000,000,000] 범위의 정수;
 A ≤ B.

 복잡도:
 최악의 시간복잡도는 O(1);
 최악의 공간복잡도는 O(1);





https://codility.com/demo/results/trainingBTWCPP-XMG/

[Algorithm] Codility Lesson 5 Prefix Sums - Prefix Sums

N개의 정수로 구성된 비어있지 않은 배열 A가 주어진다.
배열 A의 연속된 요소는 길 위의 연속된 자동차를 나타낸다.

배열 A는 0,1 만 포함한다:
- 0 은 자동차가 동쪽으로 이동중임을 나타내고,
- 1 은 자동차가 서쪽으로 이동중임을 나타낸다.

목표는 통과하는 자동차를 세는것이다.
자동차 한 쌍(P,Q)은 0 ≤ P < Q < N이고 P는 동쪽으로 이동하고 Q 는 서쪽으로 이동하며 통과할 때를 말한다.

예를 들어 배열 A가 다음과 같다고 하면:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
우리는 통과하는 차 중에 다섯 쌍을 가지고 있다 : (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

함수 작성:
class Solution { public int solution(int[] A); }
정수 N개의 비어있지 않은 배열 A가 주어지고, 통과하는 차의 쌍 수를 리턴한다.

통과하는 차의 쌍 수가 1,000,000,000를 초과하면 함수는 -1을 리턴해야 한다.

예를들어 다음과 같이 주어진다면:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
위에서 설명한대로 함수는 5를 리턴해야 한다.

가정:
- N은 [1..100,000] 범위의 정수이다.
- 배열 A의 각 요소는 0, 1 중 하나의 값만을 가질 수 있다.

복잡도:
- 최악의 시간복잡도는 O(N);
- 최악의 공간복잡도는 O(1), 입력 값 제외

배열의 요소는 수정할 수 있다.





90%
https://codility.com/demo/results/trainingBN4EAQ-52Q/

100%
https://codility.com/demo/results/trainingVNJ5UB-TCQ/

[Algorithm] Codility Lesson 4 Counting Elements - MaxCounters

0으로 초기화 되어있는 N개의 카운터가 주어지고, 두 가지 연산이 있다.
- increase(X) − 카운터 X 를 1 증가시킨다.
- max counter − 모든 카운터를 카운터 최대값으로 설정한다.

M개의 정수로 구성된 비어있지 않은 배열 A가 주어진다. 이 배열은 다음의 연속적인 연산을 나타낸다.
- 만약 A[K] = X 가 1 ≤ X ≤ N 면 연산 K는 increase(X)이고,
- 만약 A[K] = N + 1 이면 연산 K 는 max counter 이다.

예를 들어, N = 5 이고 배열 A가 다음과 같이 주어진다면
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

연속되는 각각의 연산 후에 카운터들의 값은 다음과 같을 것이다.
(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

목표는 모든 연산 후에 모든 카운터의 값을 산출하는 것이다.

함수 작성:
class Solution { public int[] solution(int N, int[] A); }
정수 N과 M개의 정수로 구성된 비어있지 않은 배열 A가 주어지고
카운터들의 값을 나타낸 연속된 정수를 리턴한다.

수열은 다음과 같아야 한다:
- 구조체 (C),
- 정수 벡터 (C++),
- 레코드 (Pascal),
- 정수 배열 (그 밖의 다른 프로그래밍 언어).

예를들어 다음과 같이 주어진다면
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

위에서 설명한대로 함수는 [3, 2, 2, 4, 2]를 리턴해야 한다.

가정:
N 과 M은 [1..100,000] 범위의 정수이다.
배열 A의 각 요소는 [1..N + 1] 범위의 정수이다.

복잡도:
최악의 시간복잡도는 O(N+M);
최악의 공간복잡도는 O(N), 입력 공간 제외.

입력된 배열의 요소는 수정 될 수 있다.





88%
https://codility.com/demo/results/trainingUKVD8F-3R7/

100%
https://codility.com/demo/results/trainingFVZK33-75M/