[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/