코딩 테스트(JS)_정렬과 알고리즘, 탐색

1. 좌표 정렬

· 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, 
  x좌표가 같으면 y좌표가 증가하는 순서로 정렬하여 출력하는 프로그램을 작성하시오.

 

 

 

 

· 입력: 첫 번째 행에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 
  두 번째 행부터 x, y 좌표가 주어진다. 단, 위치가 같은 두 점은 없다.

  (-100,000 ≤ xi, yi ≤ 100,000) 
· 출력: 조건에 따라 정렬한 결과를 출력한다.

 

 

 

 

 

let fs = require('fs');
let input = fs.readFileSync('sort_05.txt')
            .toString().split('\n');
 
// 전체 자료 개수를 n에 저장
let n = Number(input[0]);
 
// 신규 배열 생성
let data = [];
for(let i=1; i<=n; i++){
    let [x, y] = input[i].split(' ').map(Number);
    data.push([x, y]);
}
 
data.sort(compare);
 
function compare(a, b){
    if(a[0] != b[0]){
        return a[0] - b[0];  // x좌표 오름 기준
    }else{
        return a[1] - b[1];  // y좌표 오름 기준
    }
}
 
let result ='';
for(let item of data){
    result = result + item[0] + ' ' + item[1] + '\n';
}
console.log(result);

 

2. 단어 정렬

· 알파벳 소문자로 이루어진 N개의 단어가 주어진다. 길이가 짧은 것부터, 길이가 같으면 사전 순으로 정렬한다.
· 단, 중복된 단어는 하나만 남기고 제거해야 한다.

 

 

 

· 입력: 첫 번째 행에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 
  두 번째 행부터 N개의 줄에 걸쳐 소문자로 이루어진 단어가 주어진다. 
  단, 문자열의 길이는 50을 넘지 않는다.
· 출력: 조건에 따라 정렬하여 단어들을 출력한다.

 

 

 

 

 

 

 

let fs = require('fs');
let input = fs.readFileSync('sort_06.txt')
            .toString().split('\n');
 
// 전체 자료 개수를 n에 저장
let n = Number(input[0]);
 
// 신규 배열 생성
let data = [];
for(let i=1; i<=n; i++){
    data.push(input[i]);
}
 
// 중복 제거 - set 이용!
data = [... new Set(data)];
 
// 정렬 작업
data.sort(compare);
function compare(a, b){
    // 길이의 오름차순
    if(a.length != b.length){
        return a.length - b.length;
    }else{
        // 사전식 오름차순 정렬
        if(a < b) return -1;
        if(a > b) return 1;
        else return 0;
    }
}
 
for(let item of data){
    console.log(item);
}

3. 값의 상대적 순위 구하기

· 여러 개의 값을 입력받아 작은 값부터 큰 값의 상대 순위를 구하시오.

 

 

· 입력: 첫 번째 행에 N이 주어진다.
  두 번째 행에는 공백 한 칸으로 구분된

  X1, X2, ..., XN이 주어진다.
· 출력: X'1, X'2, ..., X'N 공백을 두고 출력한다.

 

 

let fs = require('fs');
let input = fs.readFileSync('sort_07.txt')
            .toString().split('\n');
 
// 전체 자료 개수를 n에 저장
let n = Number(input[0]);
 
// 신규 배열 생성
let data = input[1].split(' ').map(Number);
 
// set으로 변경 후 정렬
let setData = [... new Set(data)].sort((a,b)=> a-b);
 
// map으로 전환
let mapData = new Map();
// setData를 mapData로 변환
for(let i=0; i<setData.length; i++){
    mapData.set(setData[i], i);
}
 
// data 배열을 순회하면서 mapData의 키와 매핑된 value 값 출력
let result = '';
for(let x of data){
    result = result + mapData.get(x) + ' ';
}
console.log(result);

 

4. 숫자 정렬

· 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

 

 

 

· 입력: 첫 번째 행에 정렬하려고 하는 수 N이 주어진다. 
  N은 1,000,000,000보다 작거나 같은 자연수이다.
· 출력: 자리수를 내림차순으로 정렬한 수를 출력한다.

 

 

let fs = require('fs');
let input = fs.readFileSync('sort_08.txt')
            .toString().split('\n');
 
// 배열로 선언
let data = input[0].split('').map(Number);
 
// Array(개수).fill(지정 숫자로 채움)
let count = new Array(10).fill(0);
 
// data를 순회하면서 count 요소에 더하기
for(let i=0; i<=data.length; i++){
    count[data[i]]++;
}
 
let result = '';
// count 배열을 뒤에서 인덱스를 갯수만큼 출력
for(let i=count.length; i>=0; i--){
    for(let j=0; j<count[i]; j++){
        result = result + i;
    }
}
console.log(result);

 

※ 탐욕 알고리즘(Greedy Algorithm)

· 현재 상황에서 당장 가장 좋아 보이는 상황만을 선택하는 알고리즘
· 최적의 해를 구하기 위한 근사적인 방법으로 사용될 때가 많다.
· 알고리즘 접근 방법
  ⓐ 방법 고안하기 : 현재 상황에서 어떤 것을 선택할지 고안
  ⓑ 정당성 확인 : 고안한 알고리즘이 최적의 해를 보장하는지 확인

 

5. 동전 문제

· 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
  동전을 적절히 사용해서 그 가치의 합 K를 만들려고 한다. 
· 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

 

 

· 입력: 첫 번째 행에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
  두 번째 행부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. 
  (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
· 출력: K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

 

 

 

let fs = require('fs');
let input = fs.readFileSync('greedy_01.txt')
            .toString().split('\n');
 
let [arr, money] = input[0].split(' ').map(Number);
 
let count = 0;
for(let i=arr; i>=1; i--){
    if(money != 0 && input[i] <= money){
        count += parseInt(money/input[i]);
        money = money % input[i];
    }
}
console.log(count);

6. 이진 탐색(Binary Search)

· 탐색을 위한 복잡도 : O(logN)

· 아래 리스트에서 7를 찾고자 한다.탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.
· 입력: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19

 

let arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
 
//찾을 값
let target = 7;
// bS(배열,left, right, 찾을값);
// binarySearch 함수의 return 값을 받기 위해 searchIndex 설정
let searchIndex=binarySerch(arr, 0, arr.length-1, target);
 
if(searchIndex == -1){
    console.log(`찾는 값 : ${target}은 없습니다.`)
} else {
    console.log(`찾는 값 : ${target}, 인덱스 : ${searchIndex}`)
}
 
function binarySerch(arr, left, right, target){
    if(left > right) return -1;
    let mid = parseInt((left+right)/2);
    // 찾은 경우
    if(arr[mid]==target) {
        return mid;}
    else if(arr[mid] > target){
        // 찾는 값이 배열의 좌측에 있는 경우
        return binarySerch(arr, left, mid-1, target);
    } else {
        // 찾는 값이 배열의 우측에 있는 경우
        return binarySerch(arr, mid+1, right, target);
    }
}

7. 파라메트릭 서치

· 특정 조건을 만족하는 값을 가장 빠르게 찾는 최적화 문제
· 국가의 역할 중 하나는 여러 지방의 예산 요청을 심사하여 예산을 분배하는 것이다. 
  정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.
  모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
  모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 
  모두 상한액을 배정한다. 상한액 이하의 예산 요청에 대해서는 요청한 금액을 그대로 배정한다. 
  예를 들어, 전체 국가예산이 485이고 4개 지방의 예산 요청이 각각 120, 110, 140, 150이라고 하자. 
  이 경우, 상한액을 127로 잡으면, 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.
  여러 지방의 예산 요청과 국가예산의 총액이 주어졌을 때, 조건을 만족하도록 예산을 배정하는 프로그램을 작성하시오.

· 입력: 첫 번째 행에는 지방의 수 정수 N이 주어진다.

  두 번째 행에는 각 지방의 예산 요청을 표현하는

  N개의 정수가 공백을 두고 주어진다.
  세 번째 행에는 총 예산을 나타내는 정수 M이 주어진다. 
· 출력: 배정된 예산들 중 최댓값인 정수를 출력한다.

 

 

let fs = require('fs');
let input = fs.readFileSync('parametric_search.txt')
            .toString().split('\n');
 
// 전체 데이터 수
let n = Number(input[0]);
// 지방 재정요청 배열
let arr = input[1].split(' ').map(Number);
// 총 예산
let m = Number(input[2]);
// 시작 값, 종료 값
let start = 1;
let end = arr.reduce((x,y)=> Math.max(x,y));
 
// 결과 담을 변수
let result = 0;
// 루프, 값을 찾는다.
while(start <= end){
    let mid = parseInt((start+end)/2);
    // 임시예산의 합을 구할 변수
    let total = 0;
    for(let x of arr){
        total = total + Math.min(x,mid);
    }
    if(total <= m){
        // 찾는 값이 오른쪽에 있는 경우
        result = mid;
        start = mid + 1;
    }else{
        end = mid - 1;
    }
}
console.log(result);