Homile

문제

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.

여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤  j ≤ N (X[i]+...+X[j])를 구하자.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)

그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

출력

각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

2
5
1 2 3 4 5
5
2 1 -2 3 -5

15
4

문제풀이(1)

DP문제
1. 현재값, 현재값 + 이전값 중 큰수를 쌓아준다.
2. 테스트 케이스별로 최대값을 구한다.

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

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

const answer = [];

for (let i = 0; i < T; i++) {
  const N = Number(input.shift());
  const nums = input.shift().split(" ").map(Number);
  for (let i = 1; i < nums.length; i++) {
    nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
  }

  answer.push(Math.max(...nums));
}

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

문제

N(3≤N≤999, N은 홀수)명의 학생들이 원 모양으로 둘러앉아 있다. 각 학생들은 모두 몇 개의 사탕(≤100,000)을 가지고 있는데 그 개수는 사람마다 다를 수 있고, 사탕을 아예 가지고 있지 않을 수도 있다. 물론 사탕의 개수는 음이 아닌 정수이다.

편의상 학생들에게 번호를 매기는데, 반시계 방향으로 1번 학생, 2번 학생, …, N번 학생으로 번호를 매겼다. 1번 학생 오른쪽엔 2번 학생, 2번 학생 오른쪽엔 3번 학생이 앉아 있는 것이고, 마지막 N번 학생 오른쪽엔 1번 학생이 앉아 있게 된다.

우리는 인접한 두 학생이 가지고 있는 사탕의 수의 합을 안다. 즉 1번 학생과 2번 학생이 가지고 있는 사탕의 수의 합, 2번 학생과 3번 학생이 가지고 있는 사탕의 수의 합, …, N-1번 학생과 N번 학생이 가지고 있는 사탕의 수의 합, 마지막으로 N번 학생과 1번 학생의 가지고 있는 사탕의 수의 합을 안다. 이때, 각 학생이 가지고 있는 사탕의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(3 ≤ N ≤ 999, N은 홀수)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 1번 학생과 2번 학생이 가지고 있는 사탕의 수의 합, 2번 학생과 3번 학생이 가지고 있는 사탕의 수의 합, …, N-1번 학생과 N번 학생이 가지고 있는 사탕의 수의 합, 마지막으로 N번 학생과 1번 학생의 가지고 있는 사탕의 수의 합이 순서대로 주어진다.

출력

첫째 줄부터 N개의 줄에 걸쳐 1번 학생이 가지고 있는 사탕의 수, 2번 학생이 가지고 있는 사탕의 수, …, N번 학생이 가지고 있는 사탕의 수를 순서대로 출력한다. 출력하는 수는 음이 아닌 정수들이어야 하며, 항상 답이 존재하는 경우만이 입력으로 주어진다고 가정해도 좋다.

3
5
7
6

2
3
4

문제풀이(1)

문제

숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10)

이미지 I는 크기가 R × C인 2차원 픽셀이다. (3 ≤ R ≤ 40, 3 ≤ C ≤ 40) 각 픽셀은 어두운 정도 V를 나타낸다. (0 ≤ V ≤ 255)

중앙 필터는 이미지에 있는 노이즈를 제거하는 필터이다. 필터의 크기는 3 × 3이고, 이미지의 중앙값을 찾으면서 잡음을 제거한다.

예를 들어, 아래와 같은 6 × 5 이미지가 있다.

필터링된 이미지의 크기는 4 × 3이고, 아래와 같다.

가장 왼쪽 윗 행에 필터를 두고, 오른쪽으로 움직이면서 중앙값을 찾는다. 한 행을 모두 이동했으면, 다음 행으로 이동해 다시 중앙값을 찾는다. 아래와 같은 순서를 가진다.

위의 그림에서 각각의 중앙값은 36, 36, 21이 된다. 이 값은 필터링된 이미지 J의 첫 행과 같다. 

이미지 I가 주어졌을 때, 필터링 된 이미지 J를 구하고, 값이 T보다 크거나 같은 픽셀의 수를 구하는 프로그램을 작성하시오.

예를 들어, T = 40일 때, 위의 예에서 정답은 7이다. 

입력

첫째 줄에 이미지의 크기 R과 C가 주어진다. 그 다음 R개의 각 줄에는 C개의 픽셀 값이 주어진다. 마지막 줄에는 T값이 주어진다.

출력

첫째 줄에 필터링 된 이미지 J의 각 픽셀 값 중에서 T보다 크거나 같은 것의 개수를 출력한다.

문제

소문자로 이루어진 단어 N개가 주어졌을 때, 단어가 총 최소 몇 개의 그룹으로 이루어져 있는지 구하는 프로그램을 작성하시오.

그룹에 속한 단어는 모두 같은 알파벳으로 이루어져 있어야 하고, 개수도 같아야 한다. 즉, 단어를 구성하는 알파벳의 순서만 달라야 한다.

입력

첫째 줄에 단어의 개수 N이 주어진다. (2 ≤ N ≤ 100) 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다.

출력

첫째 줄에 그룹의 최소 개수를 출력한다.

2
a
a

1

문제풀이(1)

1. 정해진 단어들을 오름차순으로 정렬한다.
2. set 객체를 활용하여 중복되는 단어들을 제거한다.
3. 중복이 제거된 set 객체의 size를 출력한다.

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

const setArr = new Set();

arr.forEach((el) => {
  setArr.add(el.split("").sort().join(""));
});

console.log(setArr.size);

문제

동아리방이 가지고 싶었던 병찬이는 LINK 사업단에 문의하여 N개의 방 중의 하나를 얻을 기회를 얻었다. 일자로 되어있는 건물에 N개의 방은 일직선상에 존재하며, 각 방에는 번호가 매겨져 있다. 맨 왼쪽 방의 번호는 1번이며, 순서대로 증가하여 맨 오른쪽 방의 번호가 N번이다. 각 방 사이에는 방을 구분하는 벽이 존재한다.

물론 병찬이 외에도 많은 사람이 동아리방을 원한다. 다행히 방은 충분했기에 병찬이는 안심하고 있었지만…

그때였다.

빅-종빈빌런이 나타나 건물 벽을 허물기 시작한 것이다! 빅-종빈빌런은 다음과 같은 규칙으로 벽을 무너뜨린다.

• x < y 를 만족하는 두 방에 대해서 x번 방부터 y번 방 사이에 있는 모든 벽을 허문다.
• 두 방 사이의 벽이 허물어지면 두 방은 하나의 방으로 합쳐진다.
• 이미 허물어진 벽이 존재한다면 무시하고 다음 벽을 허문다.
• 빅-종빈빌런은 건물이 무너지는 걸 원치 않기 때문에, 1번 방의 왼쪽 벽과 N번 방의 오른쪽 벽(즉, 바깥과 연결된 벽)은 허물지 않는다.

동아리 방의 개수가 점점 줄어들자 병찬이는 초조해졌다. 이에 병찬이는 동아리방을 얻을 수 있는지에 대한 확률을 계산하기 위해 남는 동아리방의 수를 구하고 싶어 한다. 병찬이를 위해 빅-종빈빌런의 행동 횟수 M과 동방의 개수 N이 주어졌을 때, 남은 동아리방의 수를 구해주자.

입력

첫 번째 줄에는 동아리방의 개수를 나타내는 양의 정수 N(2 ≤ N ≤ 100) 이 주어진다. 두 번째 줄에는 빅-종빈빌런의 행동 횟수를 나타내는 음이 아닌 정수 M(0 ≤ M ≤ 100) 이 주어진다. 세 번째 줄부터 M개의 줄에 걸쳐 빅-종빈빌런의 행동이 양의 정수 x, y(1 ≤ x < y ≤ N) 로 주어진다. 여기서 행동이란 x번 방부터 y번 방 사이의 벽을 무너뜨리는 것을 의미한다.

빅-종빈빌런은 매우 허당이기 때문에 동일한 행동을 여러 번 할 수 있음에 유의하라.

출력

빅-종빈빌런의 모든 행동이 끝난 후 남아있는 동방의 개수를 한 줄에 출력한다.

5
1
1 5

1

문제풀이(1)

동아리방의 개수 = 5, 빅-종빈빌런의 행동횟수 = 2,
빅-종빈빌런의 행동 양의정수 x = 1, 2, y = 2, 4
true, true, true, true, true이고, x < y 일 때, 사이의 방을부순다.
2번의 행동 모두 위의 조건을 만족하기 때문에 사이의 벽을 부순다.
첫번째 행동: true, false, true, true, true
두번째 행동: true, false, false, false, true
벽이 사라진다는 것은 x < 부숴지는 방 <= y 이다.

1. N만큼의 배열의 공간에 true로 방을 만든다.
2. 시작방과 끝방-1만큼 반복문을 순회하며 false로 방을 제거한다.
3. 남아있는 방의 개수를 카운트한다.

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 M = Number(input.shift());

// true = 부숴지지 않은 벽, false = 부숴진 벽
const walls = Array.from({ length: N }).fill(true);

for (let i = 0; i < M; i++) {
  const [startRoom, endRoom] = input[i].split(" ").map(Number);

  for (let j = startRoom; j < endRoom; j++) {
    walls[j] = false;
  }
}

console.log(walls.filter((el) => el === true).length);