Homile

https://www.acmicpc.net/problem/20186

5 3
2 3 1 2 1

4

6 2
4 1 5 2 6 3

10

n개의 수 중 k개를 고를 때, 전체 점수의 최댓값을 구하는 문제이다.
최댓값을 구하는 문제이기때문에 내림차순으로 정렬한뒤 큰 수 k개를 찾으면 될 것이다.
마지막으로 가장 큰 K개의 숫자의 합에서 K개의 숫자를 이루는 연속된 자연수의 합을 뺀 값을 구하면된다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [n, k] = input.shift().split(" ").map(Number);
const arr = input[0]
  .split(" ")
  .map(Number)
  .sort((a, b) => b - a);

let answer = 0;

for (let i = 0; i < k; i++) {
  answer += arr[i];
}

// 가장 큰 K개의 숫자의 합에서 K개의 숫자를 이루는 연속된 자연수의 합을 뺀 값
console.log(answer - (k * (k - 1)) / 2);

https://www.acmicpc.net/problem/9417

3
10 20 30 40
7 5 12
125 15 25

20
1
25

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());

const result = [];

const getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

for (let i = 0; i < N; i++) {
  const numbers = input[i].split(" ").map(BigInt);
  let max = 0;
  for (let j = 0; j < numbers.length; j++) {
    for (let k = j + 1; k < numbers.length; k++) {
      let gcd = getGCD(numbers[j], numbers[k]);
      if (gcd > max) max = gcd;
    }
  }
  result.push(max.toString());
}

console.log(result.join("\n"));

https://www.acmicpc.net/problem/1337

3
5
6
7

2

6
5
7
9
8492
8493
192398

2

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const getMaxContinuousNum = (numbers) => {
  let max = 0;

  for (let i = 0; i < numbers.length; i++) {
    const set = new Set([numbers[i] + 1, numbers[i] + 2, numbers[i] + 3, numbers[i] + 4]);
    let cnt = 0;

    for (let j = 0; j < numbers.length; j++) {
      if (set.has(numbers[j])) {
        cnt++;
      }
    }

    max = Math.max(max, cnt);
  }

  return max;
};

const [N, ...numbers] = input.map(Number);
numbers.sort((a, b) => a - b);

console.log(4 - getMaxContinuousNum(numbers));

https://www.acmicpc.net/problem/13706

36

6

81

9

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let number = BigInt(require("fs").readFileSync(filePath).toString().trim());

console.log(Math.sqrt(number.toString()));

문제풀이(2)

알고리즘이 잘 생각나지 않아서 검색한 결과 이진탐색으로 풀 수 있다는 것을 알았다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let number = BigInt(require("fs").readFileSync(filePath).toString().trim());

const binarySearch = (number) => {
  let low = 1n;
  let high = BigInt(number);

  while (low <= high) {
    let mid = (low + high) / 2n;

    if (mid ** 2n > number) {
      high = mid - 1n;
    } else if (mid ** 2n < number) {
      low = mid + 1n;
    } else {
      return mid;
    }
  }
};

console.log(binarySearch(number).toString());

https://www.acmicpc.net/problem/28279

11
6
1 3
1 8
7
8
3
2 5
1 2
5
4
4

1
8
3
8
3
5
3

문제풀이(1)

위의 데크로직을 구현하면 되는 문제이다. 시간이 다소 소요됐다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");
const N = Number(input.shift());

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  unshift(value) {
    // 정수 X를 덱의 앞에 넣는다.
    const node = new Node(value);
    if (!this.head) {
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
    }
    this.head = node;
    this.size++;
  }

  push(value) {
    // 정수 X를 덱의 뒤에 넣는다.
    const node = new Node(value);
    if (!this.tail) {
      this.head = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }

  shift() {
    // 맨 앞의 정수를 빼고 출력한다.
    if (!this.head) {
      return -1;
    }
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head) {
      this.head.prev = null;
    } else {
      this.tail = null;
    }
    this.size--;
    return value;
  }

  pop() {
    // 맨 뒤의 정수를 빼고 출력한다.
    if (!this.tail) {
      return -1;
    }
    const value = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) {
      this.tail.next = null;
    } else {
      this.head = null;
    }
    this.size--;
    return value;
  }

  length() {
    // 덱에 들어있는 정수의 개수를 출력한다.
    return this.size;
  }

  isEmpty() {
    // 덱이 비어있으면 1, 아니면 0을 출력한다.
    return this.size === 0 ? 1 : 0;
  }

  getFront() {
    // 덱에 정수가 있다면 맨 앞의 정수를 출력한다.
    return this.head ? this.head.value : -1;
  }

  getBack() {
    // 덱에 정수가 있다면 맨 뒤의 정수를 출력한다.
    return this.tail ? this.tail.value : -1;
  }
}

const deque = new Deque();

let answer = "";

for (let i = 0; i < N; i++) {
  const [command, value] = input[i].split(" ").map(Number);

  // unshift, push, shift, pop, length, isEmpty, getFront, getBack
  switch (command) {
    case 1:
      deque.unshift(value);
      break;
    case 2:
      deque.push(value);
      break;
    case 3:
      answer += `${deque.shift()}\n`;
      break;
    case 4:
      answer += `${deque.pop()}\n`;
      break;
    case 5:
      answer += `${deque.length()}\n`;
      break;
    case 6:
      answer += `${deque.isEmpty()}\n`;
      break;
    case 7:
      answer += `${deque.getFront()}\n`;
      break;
    case 8:
      answer += `${deque.getBack()}\n`;
      break;
    default:
      break;
  }
}

console.log(answer.trim());

https://www.acmicpc.net/problem/15649

3 1

1
2
3

4 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

자신과 같거나 방문했던 노드는 선택하지 않는 점에서 DFS로 풀어야 한다고 생각했다.
찾아보니 이와 같은 문제를 백트래킹 문제라고 한다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, M] = require("fs").readFileSync(filePath).toString().trim().split(" ").map(Number);

let result = "";
const answer = [];
const visited = new Array(N).fill(false);

const dfs = (count) => {
  if (count === M) {
    return (result += `${answer.join(" ")}\n`);
  }

  for (let i = 0; i < N; i++) {
    if (!visited[i]) {
      visited[i] = true;
      answer.push(i + 1);
      dfs(count + 1);
      answer.pop();
      visited[i] = false;
    }
  }
};

dfs(0);

console.log(result.trim());