문제 정의

• N x N 크기의 바둑판이 있고, 각 칸에는 숫자 또는 연산자가 들어 있습니다.
• (1,1)에서 시작하여 (N,N)까지 최단 경로로 이동해야 합니다(오른쪽 또는 아래로만 이동).
• 경로에서 만나는 숫자와 연산자를 순서대로 적용하여 최종 결과를 계산합니다.
• 연산자 우선순위는 고려하지 않고 순서대로 계산합니다.
• 가능한 모든 경로 중에서 결과값의 최대값과 최소값을 구해야 합니다.

접근 방법

• DFS로 모든 가능한 경로를 탐색
• 각 경로마다 숫자와 연산자를 순서대로 적용하여 결과값을 계산
• 모든 경로 중에서 최대값과 최소값을 탐색

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0]);
const board = [];

for (let i = 1; i <= N; i++) {
  board.push(input[i].split(' '));
}

const findMinMaxValues = () => {
  let maxVal = -Infinity;
  let minVal = Infinity;

  // DFS를 통해 모든 가능한 경로를 탐색
  function dfs(r, c, values = []) {
    // 현재 위치의 값 추가
    const currentValue = board[r][c];
    const newValues = [...values, currentValue];

    // 학교에 도착한 경우 결과 계산
    if (r === N - 1 && c === N - 1) {
      // 표현식 계산
      let result = calculate(newValues);

      maxVal = Math.max(maxVal, result);
      minVal = Math.min(minVal, result);
      return;
    }

    // 오른쪽으로 이동
    if (c + 1 < N) {
      dfs(r, c + 1, newValues);
    }

    // 아래쪽으로 이동
    if (r + 1 < N) {
      dfs(r + 1, c, newValues);
    }
  }

  // 표현식 계산 함수
  const calculate = (values) => {
    let result = parseInt(values[0]); // 첫 번째 값은 항상 숫자

    for (let i = 1; i < values.length; i += 2) {
      if (i + 1 < values.length) {
        const op = values[i];
        const num = parseInt(values[i + 1]);

        switch (op) {
          case '+': result += num; break;
          case '-': result -= num; break;
          case '*': result *= num; break;
        }
      }
    }

    return result;
  }

  // DFS 시작
  dfs(0, 0);

  return { maxVal, minVal };
}

const result = findMinMaxValues();
console.log(`${result.maxVal} ${result.minVal}`);

문제: https://www.acmicpc.net/problem/28069 알고리즘 분류: 너비 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

문제 정의

최대 K번의 행동으로 N번 계단에 도달할 수 있는가 N번 계단에 도달하는 데 필요한 최소 행동 수가 K 이하인가

DP접근법

각 위치마다 도달하는 데 필요한 최소 행동 수만 기록하면 되고, 마지막에 dp[N] ≤ K인지만 확인

코드

const fs = require('fs');
const [N, K] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

const dp = new Array(N + 1).fill(Infinity);
dp[0] = 0;

for (let i = 0; i <= N; i++) {

  if (i + 1 <= N) {
    dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
  }

  const jump = i + Math.floor(i / 2);
  if (jump <= N) {
    dp[jump] = Math.min(dp[jump], dp[i] + 1);
  }
}

console.log(dp[N] <= K ? 'minigimbob' : 'water');

문제: https://www.acmicpc.net/problem/27971 알고리즘 분류: 너비 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

문제 정의

• 호무라는 정확히 N마리의 강아지를 키우고 싶습니다.
• 두 가지 마법을 사용할 수 있습니다: A마리 또는 B마리의 강아지를 생성하는 마법
• 제약 사항: 특정 닫힌 구간 [L,R]에 해당하는 수의 강아지가 만들어지면 모두 사라집니다.
• 처음에는 강아지가 0마리 있습니다.
• 최소 행동 횟수로 정확히 N마리를 만들어야 합니다.

문제 접근 방식

최단 경로 문제 → BFS

1. 0부터 N까지의 강아지 수를 노드로 생각하고, A마리나 B마리를 추가하는 것을 간선으로 볼 수 있다.

2. 제약 구간에 포함되는 상태는 갈 수 없는 노드이다.

3. BFS(너비 우선 탐색)를 사용하여 최소 행동 횟수를 찾을 수 있다:

   • 초기 상태는 0마리에서 시작
   • 각 상태에서 A마리 또는 B마리를 추가했을 때의 새로운 상태를 검사
   • 제약 구간에 포함되는 상태는 방문하지 않음
   • N마리에 도달하면 해당 시점의 행동 횟수가 답

내 코드

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M, A, B] = input[0].split(' ').map(Number);

// 제약 구간
const restrictedRanges = [];
for (let i = 1; i <= M; i++) {
    const [L, R] = input[i].split(' ').map(Number);
    restrictedRanges.push([L, R]);
}

// 특정 수가 제약 구간에 포함되는지 검사
const isRestricted = (num) => {
    for (const [L, R] of restrictedRanges) {
        if (num >= L && num <= R) {
            return true;
        }
    }
    return false;
}

// BFS로 최소 행동 횟수 계산
const findMinActions = () => {
    // N이 제약 구간에 포함되면 불가능
    if (isRestricted(N)) {
        return -1;
    }

    // 방문 배열 (각 강아지 수에 도달하기 위한 최소 행동 횟수 저장)
    const visited = new Array(N + 1).fill(-1);
    visited[0] = 0; // 초기 상태: 0마리

    // BFS를 위한 큐
    const queue = [0];

    while (queue.length > 0) {
        const current = queue.shift();

        // N에 도달했으면 최소 행동 횟수 반환
        if (current === N) {
            return visited[current];
        }

        // A마리 추가하는 경우
        const addA = current + A;
        if (addA <= N && !isRestricted(addA) && visited[addA] === -1) {
            visited[addA] = visited[current] + 1;
            queue.push(addA);
        }

        // B마리 추가하는 경우
        const addB = current + B;
        if (addB <= N && !isRestricted(addB) && visited[addB] === -1) {
            visited[addB] = visited[current] + 1;
            queue.push(addB);
        }
    }

    // N에 도달할 수 없는 경우
    return -1;
}

console.log(findMinActions());

시간(time) 복잡도:

BFS의 시간 복잡도: O(V+E)

• V는 노드 수(최대 N), E는 간선 수(최대 2N)
• 각 상태에서 제약 구간 검사: O(M)

전체 시간 복잡도: O(N*M)

공간(space) 복잡도:

방문 배열: O(N) 큐: O(N) 전체 공간 복잡도: O(N)

제한 조건(N ≤ 100,000, M ≤ 100)을 충분히 만족

문제: https://www.acmicpc.net/problem/18126 알고리즘 분류: 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

문제 접근

트리 구조에서 루트(1번 입구)에서 가장 먼 노드를 찾는 문제

입력

4
1 2 3
2 3 2
2 4 4

출력

7

내 코드 (초기)

const fs = require('fs');
const [N, ...edges] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const numN = Number(N);
const graph = Array.from({ length: numN + 1 }, () => []);

for(let i = 0; i < edges.length; i++){
    const [a, b, c] = edges[i].split(' ').map(Number);
    graph[a].push({ node: b, distance: c });
    graph[b].push({ node: a, distance: c });
}

const findFarthestRoom = (start) => {
    const distances = Array(numN + 1).fill(-1);
    distances[start] = 0;

    const queue = [start];
    let maxDistance = 0;
    let farthestRoom = start;

    while(queue.length > 0){
        const current = queue.shift();
        for(const {node, distance } of graph[current]){
            if(distances[node] === -1){
                distances[node] = distances[current] + distance;
                queue.push(node);
            }
            // 더 먼 방을 찾으면 업데이트
            if(distances[node] > maxDistance){
                maxDistance = distances[node];
                farthestRoom = node;
            }
        }
    }
    return { maxDistance, farthestRoom };
}

const result = findFarthestRoom(1);
console.log(result.maxDistance);

개선

const fs = require('fs');
const [N, ...edges] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const numN = Number(N);
const graph = Array(numN + 1).fill().map(()=>[]); // 인접리스틀로 그래프 표현

for(let i = 0; i < edges.length; i++){
    const [a, b, c] = edges[i].split(' ').map(Number);
    graph[a].push([b, c]); // 배열사용: 객체생성 오버헤드 제거
    graph[b].push([a, c]);
}

const findFarthestRoom = (start) => {
    const distances = Array(numN + 1).fill(-1);
    distances[start] = 0;

    const queue = [start];
    let maxDistance = 0;
    let farthestRoom = start;

    let queueIndex = 0; // shift() 댓신 인덱스 사용 => 성능향상

    while(queueIndex < queue.length){
        const current = queue[queueIndex++];

        for(const [nextNode, dist] of graph[current]){
            if(distances[nextNode] === -1){
                const newDistance = distances[current] + dist;
                distances[nextNode] = newDistance;
                queue.push(nextNode);

                // 더 먼 방을 찾으면 업데이트
                if(newDistance > maxDistance){
                    maxDistance = newDistance;
                    farthestRoom = nextNode;
                }
            }
        }
    }
    return maxDistance;
}
console.log(findFarthestRoom(1));

문제: https://school.programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT

접근방법:

단계별 조건에 따라 구현한다 정규식 / 자바스크립트 내장함수 / 문자열 조작 순서를 공부해야 한다

• 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
• 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
• 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
• 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
• 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
• 6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
• 7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

내 코드

function solution(new_id) {
    new_id = new_id.toLowerCase(); // 1단계

    let result = ''; // 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)만 남길 문자열
    for(let i = 0; i < new_id.length; i++){
        const char = new_id[i];
        if((char >= 'a' && char <= 'z')||
           (char >= '0' && char <= '9')||
           (char === '-') ||
           (char === '_')||
           (char === '.')
          ){
            result += char;
        }
    }
    new_id = result;

    result = ''; // 초기화
    for(let i = 0; i < new_id.length; i++){
        if(new_id[i] === '.' && new_id[i+1] === '.'){
            continue;
        }
        result += new_id[i];
    }

    new_id = result;


    if(new_id.length > 0 && new_id[0] === '.') {
        new_id = new_id.substring(1);
    }
    if(new_id.length > 0 && new_id[new_id.length - 1] === '.'){
        new_id = new_id.substring(0, new_id.length - 1);
    }

    if(new_id === ''){
        new_id = 'a';
    }

    if(new_id.length >= 16){
        new_id = new_id.substring(0, 15);
        if(new_id[new_id.length - 1] === '.'){
            new_id = new_id.substring(0, new_id.length - 1);
        }
    }

    while(new_id.length <= 2){
        new_id += new_id[new_id.length - 1];
    }

    return new_id;
}

정규식을 활용한 개선된 코드

function solution(new_id) {
    // 1단계: 대문자를 소문자로 치환
    new_id = new_id.toLowerCase();

    // 2단계: 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자 제거
    new_id = new_id.replace(/[^\w\-\.]/g, '');
    // \w는 알파벳, 숫자, 밑줄(_)을 포함하는 문자 클래스
    // \-는 빼기 기호, \.는 마침표를 나타냄

    // 3단계: 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표로 치환
    new_id = new_id.replace(/\.{2,}/g, '.');

    // 4단계: 마침표(.)가 처음이나 끝에 위치한다면 제거
    new_id = new_id.replace(/^\.|\.$/g, '');

    // 5단계: 빈 문자열이라면, "a"를 대입
    if (new_id === '') {
        new_id = 'a';
    }

    // 6단계: 길이가 16자 이상이면, 첫 15개 문자를 제외한 나머지 문자들을 모두 제거
    if (new_id.length >= 16) {
        new_id = new_id.slice(0, 15);
        // 제거 후 마침표(.)가 끝에 위치한다면 제거
        new_id = new_id.replace(/\.$/, '');
    }

    // 7단계: 길이가 2자 이하라면, 마지막 문자를 길이가 3이 될 때까지 반복해서 붙임
    while (new_id.length <= 2) {
        new_id += new_id.charAt(new_id.length - 1);
    }

    return new_id;
}

개선된 최종 코드

메서드 체이닝과 자바스크립트 내장함수 .padEnd()를 이용해 조금더 코드를 간결하게 개선할 수 있다.

function solution(new_id) {
    return new_id
        .toLowerCase()                       // 1단계: 소문자로 변환
        .replace(/[^\w\-\.]/g, '')           // 2단계: 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자 제거
        .replace(/\.{2,}/g, '.')             // 3단계: 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표로 치환
        .replace(/^\.|\.$/g, '')             // 4단계: 처음과 끝의 마침표 제거
        .replace(/^$/, 'a')                  // 5단계: 빈 문자열이면 'a' 대입
        .slice(0, 15)                        // 6단계: 길이가 16자 이상이면, 첫 15개 문자만 남김
        .replace(/\.$/, '')                  // 6단계: 끝에 마침표가 있으면 제거
        .padEnd(3, new_id.slice(-1) || 'a'); // 7단계: 길이가 2자 이하라면, 마지막 문자를 길이가 3이 될 때까지 반복
}

허용되지 않은 문자 제거 replace(/[^\w\-\.]/g, '')

\w: 알파벳, 숫자, 밑줄(_)을 포함하는 문자 클래스 \-\.: 빼기(-), 마침표(.) [^...]: 괄호 안의 문자를 제외한 모든 문자와 매칭

따라서, 허용된 문자 외의 모든 것이 제거 됨

연속된 마침표 치환 replace(/\.{2,}/g, '.')

\.{2,}: 마침표가 2번 이상 연속된 부분 → 이를 하나의 마침표로 치환

처음과 끝의 마침표 제거 replace(/^\.|\.$/g, '')

^\.: 문자열 시작의 마침표 \.$: 문자열 끝의 마침표

이 두 가지 경우를 모두 빈 문자열로 대체

빈 문자열 처리 replace(/^$/, 'a')

^$: 빈 문자열에 매칭

빈 문자열인 경우 'a'로 대체

길이 제한 slice(0, 15)

문자열을 처음부터 15자까지만 남긴다 길이가 15 미만이면 전체 문자열이 그대로 유지한다

끝의 마침표 제거 replace(/\.$/, '')

길이 제한 후 끝에 마침표가 있다면 제거

길이 보완 padEnd(3, new_id.slice(-1) || 'a')

padEnd(3, ...): 문자열 길이가 3이 될 때까지 지정된 문자로 채운다 new_id.slice(-1) || 'a': 마지막 문자(없으면 'a'를 사용)길이가 1이나 2인 경우 마지막 문자를 반복해 길이가 3이 되게 한다

✅ 주의할 점

7단계에서 new_id.slice(-1)은 원본 new_id의 마지막 문자를 가져오는 것이 아니라, 체이닝 과정에서 현재 변환된 문자열의 마지막 문자를 가져온다

빈 문자열이 될 경우 slice(-1)은 빈 문자열을 반환하므로, || 'a'를 통해 기본값 'a'를 제공해야 한다

문제: https://www.acmicpc.net/problem/17271 알고리즘 분류: 다이나믹 프로그래밍, DP

문제 이해

• N초 동안 스킬을 사용한다
• A 스킬은 1초 소요, B 스킬은 M초 소요
• 빈 시간 없이 스킬을 연속해서 사용해야 한다
• 가능한 모든 스킬 조합의 수를 찾아야 한다

접근 방법: 다이나믹 프로그래밍

dp[i] = "i초까지 가능한 모든 스킬 조합의 수"

i초에서 두 가지 경우의 수:

• 마지막에 A 스킬(1초)을 사용하는 경우: dp[i-1]
• 마지막에 B 스킬(M초)을 사용하는 경우: dp[i-M]

점화식은, dp[i] = dp[i-1] + dp[i-M]

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);

// 다이나믹 프로그래밍 배열 초기화
const dp = Array(N + 1).fill(0);
const MOD = 1000000007;

// 초기값 설정
dp[0] = 1; // 0초일 때는 아무 스킬도 사용하지 않는 한 가지 경우

// 점화식 적용
for (let i = 1; i <= N; i++) {
    // A 스킬을 사용하는 경우 (1초 전의 상태에서 가능한 조합 수)
    if (i >= 1) {
        dp[i] = (dp[i] + dp[i - 1]) % MOD;
    }

    // B 스킬을 사용하는 경우 (M초 전의 상태에서 가능한 조합 수)
    if (i >= M) {
        dp[i] = (dp[i] + dp[i - M]) % MOD;
    }
}

console.log(dp[N]);

참고 참고링크1 참고링크2

문제: https://www.acmicpc.net/problem/17484 알고리즘 분류: 3차원 다이나믹 프로그래밍, 브루트포스

어렵다.. DP 유형 많이 풀어봐야 겠다

문제 파악

최소 연료 소비로 달까지 가는 경로 구하는 문제

• N×M 행렬에서 첫 행(지구)에서 출발해 마지막 행(달)에 도착해야 함
• 우주선은 왼쪽 아래(↙️), 아래(⬇️), 오른쪽 아래(↘️) 방향으로만 이동 가능
• 같은 방향으로 두 번 연속 이동할 수 없음
• 목표: 최소한의 연료로 도착하기

문제 접근: 다이나믹 프로그래밍

다이나믹 프로그래밍으로 접근한 이유

1. 최적 부분 구조(Optimal Substructure): 어떤 위치에서의 최소 연료는 이전 위치들의 최소 연료에 기반
2. 중복되는 부분 문제(Overlapping Subproblems): 여러 경로가 같은 중간 지점을 지날 수 있다
3. 방향 제약 조건: 이전 이동 방향을 기억해야 한다는 제약이 있어서 상태를 저장해야 한다

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);  // N: 행, M: 열
const space = [];  // 연료 소비량을 저장할 2차원 배열
for (let i = 1; i <= N; i++) {
    space.push(input[i].split(' ').map(Number));
}

const LEFT_DOWN = 0;   // 왼쪽 아래 ↙️
const DOWN = 1;        // 아래 ⬇️
const RIGHT_DOWN = 2;  // 오른쪽 아래 ↘️

// DP 배열 초기화: dp[row][col][dir]
// - row, col: 현재 위치 (0부터 시작)
// - dir: 이전에 움직인 방향 (0: 왼쪽 아래, 1: 아래, 2: 오른쪽 아래)
// - 초기값은 무한대(도달할 수 없음)로 설정
const dp = Array(N).fill().map(() => 
    Array(M).fill().map(() => 
        Array(3).fill(Infinity)
    )
);

// 첫 번째 행(지구)의 모든 위치에서 시작 가능
// 첫 번째 행에서는 이전 방향이 없으므로 모든 방향에서 해당 위치의 연료만큼 초기화
for (let j = 0; j < M; j++) {
    // 첫 행의 각 위치에 도달하는 초기 비용은 그 위치의 연료 소비량과 동일
    dp[0][j][LEFT_DOWN] = space[0][j];
    dp[0][j][DOWN] = space[0][j];
    dp[0][j][RIGHT_DOWN] = space[0][j];
}

// 두 번째 행부터 시작
for (let i = 1; i < N; i++) {
    for (let j = 0; j < M; j++) {

        // 1. 왼쪽 아래로 오는 경우
        if (j < M - 1) { // j+1이 배열 범위 내에 있어야 함 (오른쪽 끝 열이 아닌 경우)
            // 이전 위치 (i-1, j+1)에서 아래(1) 또는 오른쪽 아래(2) 방향으로 왔을 때의 최소값
            // 같은 방향(왼쪽 아래=0)으로 연속 이동할 수 없으므로 제외
            dp[i][j][LEFT_DOWN] = Math.min(
                dp[i-1][j+1][DOWN],       // 이전에 아래로 움직였던 경우
                dp[i-1][j+1][RIGHT_DOWN]  // 이전에 오른쪽 아래로 움직였던 경우
            ) + space[i][j];  
        }

        // 2. 아래로 오는 경우
        // 이전 위치 (i-1, j)에서 왼쪽 아래(0) 또는 오른쪽 아래(2) 방향으로 왔을 때의 최소값
        // 같은 방향(아래=1)으로 연속 이동할 수 없으므로 제외
        dp[i][j][DOWN] = Math.min(
            dp[i-1][j][LEFT_DOWN],    // 이전에 왼쪽 아래로 움직였던 경우
            dp[i-1][j][RIGHT_DOWN]    // 이전에 오른쪽 아래로 움직였던 경우
        ) + space[i][j];  

        // 3. 오른쪽 아래로 오는 경우
        if (j > 0) { // j-1이 배열 범위 내에 있어야 함 (왼쪽 끝 열이 아닌 경우)
            // 이전 위치 (i-1, j-1)에서 왼쪽 아래(0) 또는 아래(1) 방향으로 왔을 때의 최소값
            // 같은 방향(오른쪽 아래=2)으로 연속 이동할 수 없으므로 제외
            dp[i][j][RIGHT_DOWN] = Math.min(
                dp[i-1][j-1][LEFT_DOWN], // 이전에 왼쪽 아래로 움직였던 경우
                dp[i-1][j-1][DOWN]       // 이전에 아래로 움직였던 경우
            ) + space[i][j]; 
        }
    }
}

// 마지막 행(달)에 도착했을 때 최소 연료(minFuel) 계산
// 어느 위치든 도착할 수 있으므로 마지막 행의 모든 열에 대해 최소값 찾기
let minFuel = Infinity;
for (let j = 0; j < M; j++) {
    // 세 가지 가능한 방향 중 최소값 찾기
    minFuel = Math.min(
        minFuel,
        dp[N-1][j][LEFT_DOWN],   // 왼쪽 아래로 마지막에 도착한 경우
        dp[N-1][j][DOWN],        // 아래로 마지막에 도착한 경우
        dp[N-1][j][RIGHT_DOWN]   // 오른쪽 아래로 마지막에 도착한 경우
    );
}
console.log(minFuel);

문제: https://school.programmers.co.kr/learn/courses/30/lessons/12951 타입: 문자열 조작 구현

문제 설명

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고) 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

제한 조건

s는 길이 1 이상 200 이하인 문자열입니다. s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다. 숫자는 단어의 첫 문자로만 나옵니다. 숫자로만 이루어진 단어는 없습니다. 공백문자가 연속해서 나올 수 있습니다.

내 코드

function solution(s) {
    return s.split(" ").map(word => {
            if (word === "") return "";
            return word.charAt(0).toUpperCase() + word.slice(1).toLowerCase();
        })
        .join(" ");
}

내장 메서드

split(separator)

문자열을 지정된 구분자(separator)를 기준으로 나눠서 배열로 반환 s.split(" ")는 공백 문자를 기준으로 문자열 s를 여러 단어로 나눔 예: "hello world".split(" ") → ["hello", "world"] 연속된 구분자가 있으면 빈 문자열이 포함 됨 예: "hello world".split(" ") → ["hello", "", "world"]

map(callback)

배열의 각 요소에 주어진 함수(callback)를 적용하여 새 배열을 생성 원본 배열의 각 요소를 변환하는 데 사용 예: [1, 2, 3].map(x => x * 2) → [2, 4, 6]

charAt(index)

문자열에서 지정된 인덱스에 있는 문자를 반환 word.charAt(0)은 단어의 첫 번째 문자를 가져옴 예: "hello".charAt(0) → "h"

toUpperCase()

문자열의 모든 문자를 대문자로 변환 word.charAt(0).toUpperCase()는 단어의 첫 번째 문자를 대문자로 변환 숫자나 특수 문자에 적용해도 변화가 없음 예: "hello".toUpperCase() → "HELLO"

slice(start, end)

문자열의 일부를 추출하여 새 문자열로 반환 start 인덱스부터 end 인덱스 전까지의 부분을 잘라냄 end를 생략하면 문자열의 끝까지 추출 word.slice(1)은 두 번째 문자부터 끝까지의 부분 문자열을 가져옴 예: "hello".slice(1) → "ello"

toLowerCase()

문자열의 모든 문자를 소문자로 변환 word.slice(1).toLowerCase()는 단어의 두 번째 문자부터 끝까지를 소문자로 만듬 예: "HELLO".toLowerCase() → "hello"

join(separator)

배열의 모든 요소를 연결해 하나의 문자열로 만듬 요소 사이에는 지정된 구분자(separator)가 삽입 .join(" ")는 배열의 각 요소를 공백으로 구분하여 하나의 문자열로 합침 예: ["hello", "world"].join(" ") → "hello world"

참고 https://bedecked-operation-4d1.notion.site/99-13-TIL-JavaScript-sort-method-1d7eb405261e80a6a2b3d3c2186c7fc5 https://velog.io/@deun/99%ED%81%B4%EB%9F%BD-%EC%BD%94%ED%85%8C-%EC%8A%A4%ED%84%B0%EB%94%94-13%EC%9D%BC%EC%B0%A8-TIL-JadenCase-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%A0%95%EA%B7%9C%ED%91%9C%ED%98%84%EC%8B%9D

문제: https://www.acmicpc.net/problem/2156 알고리즘 분류: 다이나믹 프로그래밍, DP

문제 파악

• 포도주 잔을 선택하면 그 잔의 포도주는 모두 마셔야 함
• 연속으로 3잔을 모두 마실 수 없음
• 가능한 많은 양의 포도주를 마시는 것이 목표

접근 방법: 동적 프로그래밍

• 계산이 진행되면서 바뀌는 상황에서, 최적의 전략
• 계산했던 걸 저장해서 재사용

각 위치에서 최대로 마실 수 있는 포도주의 양 구하기

경우의 수

1. 현재 포도주를 마시고, 이전 포도주도 마신 경우 (2연속)
2. 현재 포도주를 마시고, 이전 포도주는 마시지 않은 경우
3. 현재 포도주를 마시지 않는 경우

DP 상태 dp[i][j]: i번째 포도주까지 고려했을 때, j개의 연속된 포도주를 마셨을 때의 최대 양

• dp[i][0]: i번째 잔을 마시지 않았을 때의 최대값
• dp[i][1]: i번째 잔을 마시고, i-1번째 잔은 마시지 않았을 때의 최대값
• dp[i][2]: i번째 잔을 마시고, i-1번째 잔도 마셨을 때의 최대값

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);

const n = input[0];  // 포도주 잔의 개수
const wines = [0];  // 포도주의 양 (인덱스를 1부터 시작하기 위해 0 추가)

// 포도주 양 입력 처리
for (let i = 1; i <= n; i++) {
    wines.push(input[i]);
}

// 동적 프로그래밍 배열 초기화
// dp[i][j]: i번째 잔까지 고려했을 때, j개 연속으로 마셨을 때의 최대 양
// dp[i][0]: i번째 포도주를 마시지 않은 경우
// dp[i][1]: i번째 포도주를 마시고, i-1번째는 마시지 않은 경우
// dp[i][2]: i번째 포도주를 마시고, i-1번째도 마신 경우
const dp = Array.from({ length: n + 1 }, () => Array(3).fill(0));

// 초기값 설정
dp[1][0] = 0;             // 첫 번째 포도주를 마시지 않음
dp[1][1] = wines[1];      // 첫 번째 포도주를 마심

for (let i = 2; i <= n; i++) {
    dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1], dp[i-1][2]);  
    dp[i][1] = dp[i-1][0] + wines[i];
    dp[i][2] = dp[i-1][1] + wines[i];
}

// 최대값 계산
const maxAmount = Math.max(dp[n][0], dp[n][1], dp[n][2]);
console.log(maxAmount);

각 상태 점화식

dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) → 현재 잔을 마시지 않으면 이전 상태 중 최대값 선택 dp[i][1] = dp[i-1][0] + wines[i] → 현재 잔을 마시고, 이전 잔은 마시지 않은 경우 dp[i][2] = dp[i-1][1] + wines[i] → 현재 잔과 이전 잔을 연속으로 마시는 경우

참고 deun블로그 https://bedecked-operation-4d1.notion.site/99-12-TIL-DP-2156-1d6eb405261e8085b424f799344a670d

문제: https://www.acmicpc.net/problem/16401 알고리즘 분류: 이분 탐색, 매개 변수 탐색

문제 파악

주어진 과자들을 특정 길이로 잘라서, 조카들에게 나눠줄 수 있는 최대 길이를 찾는 문제

• M명의 조카와 N개의 과자

• 모든 조카에게 같은 길이의 과자를 나눠줘야 한다

• 과자는 여러 조각으로 나눌 수 있지만, 합칠 수는 없다

• 조카 1명에게 줄 수 있는 과자의 최대 길이 구하기

접근 방법: 이진 탐색 (Binary Search)

결정 문제(Decision Problem) "과자 길이가 mid일 때, M명의 조카에게 나눠줄 수 있어?"

1. 가능한 과자 길이의 범위: 1 부터 가장 긴 과자 길이까지

2. 특정 길이 mid로 자를 때, 만들 수 있는 과자 조각의 수 count 계산

3. count가 M 이상 ➡️ 더 긴 길이를 찾아

4. count가 M 미만 ➡️ 더 짧은 길이 찾아

예시 ✅

조카M 3명, 과자길이snacks = [1,2,3,4,5,6,7,8,9,10]

이진 탐색 과정:

1. 첫 번째 시도 할 과자길이 mid = 5 (1~10의 중간값) 총 조각 수count = 7개 >= 3명(가능) → 더 긴 길이로 시도 → left = mid + 1 = 6, right = 10

2. 두 번째 시도 할 과자길이 mid = 8 (6~10의 중간값) 총 조각 수count = 3개 >= 3명(가능) → 더 긴 길이로 시도 → left = mid + 1 = 9, right = 10

3. 세 번째 시도 할 과자길이 mid = 9 (9~10의 중간값) 총 조각 수count = 2개 < 3명(불가능) → 더 짧은 길이로 시도 → left = 9, right = mid - 1 = 8 → 종료

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [M, N] = input[0].split(' ').map(Number); 
const snacks = input[1].split(' ').map(Number); 

const findMaxSnackLength = (nephews, snacks) => {
    let left = 1;
    let right = Math.max(...snacks);
    let result = 0;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2); 
        let count = 0;
        for (const snack of snacks) {
            count += Math.floor(snack / mid); 
        }

        if (count >= nephews) {
            result = mid; 
            left = mid + 1; 
        } else {
            right = mid - 1;
        }
    }

    return result;
}

const answer = findMaxSnackLength(M, snacks);
console.log(answer);

시간 복잡도

• 이진 탐색: O(log(max_length))
• 각 단계에서 모든 과자를 검사: O(N)
• 전체 시간 복잡도: O(N * log(max_length))

과자의 최대 길이가 10^9이므로, 이진 탐색은 최대 약 30번 정도의 반복으로 결과 도출

참고 https://bedecked-operation-4d1.notion.site/99-11-TIL-16401-1d5eb405261e80c1a245db9ed837464f

문제: https://www.acmicpc.net/problem/1783 알고리즘 분류: 많은 조건 분기, 그리디 알고리즘, 구현

문제 파악

병든 나이트🐴가 체스판에서 최대한 많은 칸을 방문하는 문제

주요 조건:

1. N × M 크기의 체스판에서 가장 왼쪽 아래 칸에서 시작
2. 병든 나이트는 4가지 이동 방법만 가능

• 2칸 위로, 1칸 오른쪽
• 1칸 위로, 2칸 오른쪽
• 1칸 아래로, 2칸 오른쪽
• 2칸 아래로, 1칸 오른쪽

3. 이동 횟수가 4번 이상이면 모든 이동 방법을 한 번씩 사용해야 함
4. 이동 횟수가 4번 미만이면 제약 없음

접근 방법: 그리디(Greedy) 알고리즘

1. 체스판 크기에 따라 가능한 이동 횟수가 제한 됨
2. 최대 방문 칸 수는, 처음 위치 포함하여 이동 횟수 + 1
3. 이동 방향:

• 모든 이동은 오른쪽으로 이동
• 위/아래 이동은 체스판 경계에 영향을 받는다

4. 4번 이상 이동할 때는 최소 한번씩 모든 방향으로 이동해야 한다

단계별 접근

1. 체스판의 크기에 따라 가능한 최대 이동 횟수를 계산
2. 이동 횟수가 4번 미만인 경우와 4번 이상인 경우를 나누어 처리
3. 4번 이상일 때는 모든 방향을 한 번씩 써야 하므로, 체스판을 벗어나지 않게 이동 방법을 결정해야 함

특수 케이스 처리

N = 1 또는 M = 1인 경우:

체스판이 한 줄짜리면 시작 위치 외에 더 이동할 수 없으므로 1을 반환

N = 2인 경우:

세로가 2칸인 경우 1칸 위로, 2칸 오른쪽과 1칸 아래로, 2칸 오른쪽 두 가지 방법만 사용 가능 ➡️ 이 경우 가로로 최대 (M+1)/2 칸까지 이동 가능하지만, 4번까지만 허용 됨

N ≥ 3, M < 7인 경우:

가로 길이가 충분하지 않아 제약 조건을 만족하기 어려운 경우 최대 M개 칸까지 방문 가능하지만, 4칸으로 제한 됨

N ≥ 3, M ≥ 7인 경우:

충분히 큰 체스판에서는 모든 이동 방법을 한 번씩 사용하고 나서도 최적의 방법으로 이동 가능 모든 이동 방법을 한 번씩 사용하면 오른쪽으로 총 6칸 이동하게 됨 그 후로는 1칸 위, 2칸 오른쪽과 1칸 아래, 2칸 오른쪽을 번갈아 사용하여 오른쪽으로 이동 ➡️ 결과적으로 M-2개의 칸을 방문할 수 있음

내 코드

const fs = require('fs');
const [N, M] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

function solution(N, M) {
    // 시작 위치 포함하여 최소 1개의 칸은 방문
    if (N === 1 || M === 1) {
        return 1;
    }

    // 세로 길이가 1 초과, 가로 길이가 1일 때는 방문할 수 없음
    if (N > 1 && M === 1) {
        return 1;
    }

    // 세로 길이가 2일 때는 특별한 경우
    if (N === 2) {
        // 가로로 움직일 수 있는 최대 횟수 (1칸 위로, 2칸 오른쪽 / 1칸 아래로, 2칸 오른쪽만 사용 가능)
        // 이동 횟수는 (M-1)/2 이하이고 최대 4회까지 가능
        return Math.min(4, Math.floor((M + 1) / 2));
    }

    // N >= 3, M < 7인 경우 최대 4칸까지만 이동 가능
    if (M < 7) {
        return Math.min(4, M);
    }

    // 일반적인 경우, N >= 3, M >= 7
    // 4번 이상 이동할 때 모든 이동 방법을 한 번씩 사용해야 함
    // 모든 이동 방법을 한 번씩 사용하면 오른쪽으로 총 6칸 이동
    // 그 후로는 1칸 위, 2칸 오른쪽 + 1칸 아래, 2칸 오른쪽 조합으로 반복
    return M - 2;
}

console.log(solution(N, M));

참고 https://bedecked-operation-4d1.notion.site/99-10-TIL-1783-1d2eb405261e803fb153f95bec2f86a1

문제: https://www.acmicpc.net/problem/2437 알고리즘 분류: 그리디 알고리즘, 정렬

문제 파악

그리디 알고리즘을 활용해 풀 수 있는 문제 주어진 저울추로 측정할 수 없는 가장 작은 양의 정수를 찾아야 함

문제 접근

저울추를 오름차순으로 정렬한 뒤, 현재까지 만들 수 있는 최대 무게를 계속 추적

1. 저울추를 오름차순으로 정렬

2. 변수 target을 1로 초기화 → 현재까지 1부터 target-1까지의 모든 무게를 만들 수 있다

3. 각 저울추를 순회하며: 만약 현재 저울추의 무게가 target보다 크다면, target이 만들 수 없는 최소 무게이므로 반복을 종료 그렇지 않다면, 현재 저울추를 사용하여 target에 현재 저울추의 무게를 더함 → 1부터 target + weightArr[i] - 1까지의 모든 무게를 만들 수 있음

4. 모든 저울추를 처리한 후, target은 만들 수 없는 최소 무게가 됩니다.

예제 입력값 3 1 6 2 7 30 1에 대해:

오름차순 정렬: [1, 1, 2, 3, 6, 7, 30]

초기 target = 1
첫 번째 추(1): target = 1 + 1 = 2 (1까지 만들 수 있음)
두 번째 추(1): target = 2 + 1 = 3 (2까지 만들 수 있음)
세 번째 추(2): target = 3 + 2 = 5 (4까지 만들 수 있음)
네 번째 추(3): target = 5 + 3 = 8 (7까지 만들 수 있음)
다섯 번째 추(6): target = 8 + 6 = 14 (13까지 만들 수 있음)
여섯 번째 추(7): target = 14 + 7 = 21 (20까지 만들 수 있음)
일곱 번째 추(30): target = 21 + 30 = 51 (50까지 만들 수 있음)

최종적으로 측정할 수 없는 가장 작은 양의 정수: 21

내 코드

const fs = require('fs');
const [n, weights] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const weightArr = weights.split(' ').map(Number).sort((a, b) => a - b);

let target = 1;

for (let i = 0; i < weightArr.length; i++) {
  // 현재 저울추의 무게가 target보다 크면, target이 만들 수 없는 최소 무게
  if (weightArr[i] > target) {
    break;
  }

  // 현재 저울추를 사용해 target을 업데이트
  // target + weightArr[i]까지의 모든 무게를 만들 수 있게 됨
  target += weightArr[i];
}

console.log(target);

그리디 알고리즘(Greedy Algorithm)

• 매 선택 단계에서 현재 상황에서 가장 최적인 선택(locally optimal choice)을 하는 알고리즘

• 예) 거스름돈 문제: 최소한의 동전 개수로 거스름돈을 만드는 문제

  function coinChange(amount, coins) {
    // 큰 금액의 동전부터 사용하기 위해 내림차순 정렬
    coins.sort((a, b) => b - a);
  
    let totalCoins = 0;
    let remainingAmount = amount;
    let result = {};
  
    for (let coin of coins) {
        const count = Math.floor(remainingAmount / coin);
        if (count > 0) {
            result[coin] = count;
            totalCoins += count;
            remainingAmount -= coin * count;
        }
    }
  
    return {
        totalCoins: totalCoins,
        coinsUsed: result,
        remainingAmount: remainingAmount
    };
  }
  

// 예시: 한국 화폐 단위로 4,760원을 거슬러주기 const koreanCoins = [5000, 1000, 500, 100, 50, 10]; console.log(coinChange(4760, koreanCoins));

```

참고 https://bedecked-operation-4d1.notion.site/99-9-TIL-1d1eb405261e80bfa59ec5cbd1da3343

문제: https://www.acmicpc.net/problem/9996 알고리즘 분류: 정규 표현식, 문자열

문제 정의

패턴은 알파벳 소문자와 별표(*) 하나로 구성됨 파일 이름은 알파벳 소문자로만 구성됨 별표는 임의의 문자열(빈 문자열 포함)로 대체 가능 각 파일 이름이 패턴과 일치하는지 확인해야 함

문제 파악

패턴은 별표를 기준으로 앞부분(prefix)과 뒷부분(suffix)으로 나눌 수 있음 파일 이름이 패턴과 일치하려면:

파일 이름이 패턴의 앞부분으로 시작해야 함 파일 이름이 패턴의 뒷부분으로 끝나야 함 파일 이름의 길이가 최소한 (prefix + suffix) 이상이어야 함

접근 방법

패턴을 별표(*)를 기준으로 앞부분과 뒷부분으로 분리 각 파일 이름에 대해:

파일 이름이 패턴의 앞부분으로 시작하는지 확인 파일 이름이 패턴의 뒷부분으로 끝나는지 확인 중간 부분이 겹치지 않는지 확인 (prefix와 suffix가 겹치는 경우 고려)

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

const lines = input.split('\n');
const n = parseInt(lines[0]);
const pattern = lines[1];

const parts = pattern.split('*');
const prefix = parts[0];
const suffix = parts[1];

const results = [];

for (let i = 0; i < n; i++) {
  const filename = lines[i + 2];

  // 파일 이름 길이가 prefix + suffix보다 짧으면 패턴과 일치 불가능
  if (filename.length < prefix.length + suffix.length) {
    results.push("NE");
    continue;
  }

  // 파일 이름이 패턴의 앞부분으로 시작하는지 확인
  if (!filename.startsWith(prefix)) {
    results.push("NE");
    continue;
  }

  // 파일 이름이 패턴의 뒷부분으로 끝나는지 확인
  if (!filename.endsWith(suffix)) {
    results.push("NE");
    continue;
  }

  // 모든 조건을 만족하면 패턴과 일치
  results.push("DA");
}

console.log(results.join('\n'));

참고 https://bedecked-operation-4d1.notion.site/99-8-TIL-1d0eb405261e80f68c5ed675c161efe7

문제: https://www.acmicpc.net/problem/10799 알고리즘 분류: 자료 구조, 스택

문제 파악

괄호로 표현된 쇠막대기와 레이저의 배치를 해석하는 문제

• ( 와 ) 가 인접한 경우는 레이저를 의미

• 나머지 (는 쇠막대기의 시작, )는 쇠막대기의 끝을 의미

• 레이저는 쇠막대기를 자르며, 쇠막대기는 자신을 지나는 레이저의 수 + 1만큼 조각으로 나뉨

• 최종적으로 잘려진 쇠막대기 조각의 총 개수를 구하자

접근 방법: 스택(Stack)

1. 문자열을 왼쪽에서 오른쪽으로 순회

2. (를 만나면: 스택에 넣는다 (잠재적인 쇠막대기 시작 또는 레이저 시작)

3. )를 만나면:

• 직전 문자가 (였다면: 이는 레이저를 의미 → 스택에서 (를 pop하고, 현재 스택에 남아있는 (의 개수만큼 조각이 생김
• 직전 문자가 (가 아니었다면: 이는 쇠막대기의 끝을 의미 → 스택에서 (를 pop하고, 조각 개수를 1 증가

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
let answer = 0;
let stack = [];
let prevChar = '';

for (let char of input) {
    if (char === '(') {
        stack.push(char);
    } else { // 닫는 괄호인 경우
        stack.pop();

        if (prevChar === '(') {
            // 레이저인 경우
            answer += stack.length;
        } else {
            // 막대기 끝인 경우
            answer += 1;
        }
    }
    prevChar = char;
}
console.log(answer);

참고 https://bedecked-operation-4d1.notion.site/99-7-TIL-10799-Stack-1cfeb405261e8067bebdc807a89a6112

문제: https://www.acmicpc.net/problem/4963 알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

문제 파악

• 그래프 이론에서 주로 다루는 "연결 요소(Connected Components)"를 찾는 문제

• 섬의 개수는 연결된 땅(1)의 그룹 수를 세는 것과 같다

• 지도는 0(바다)과 1(땅)로 구성된 2차원 배열

• 가로, 세로, 대각선으로 연결된 1(땅)은 하나의 섬으로 간주

접근 방법 - DFS(깊이우선탐색)

1. 지도의 모든 칸을 순회

2. 0 땅(1)을 발견하면 해당 위치에서 DFS함수를 시작해 연결된 모든 땅을 방문하고 표시

3. 한 번의 DFS함수가 완료되면 하나의 섬을 발견한 것이므로 섬 카운터 증가시킴

4. 모든 칸을 순회할 때까지 1-3번 반복

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let lineIndex = 0;
const results = [];

while (lineIndex < input.length) {

  const [w, h] = input[lineIndex++].split(' ').map(Number);

  if (w === 0 && h === 0) break;

  const map = [];
  for (let i = 0; i < h; i++) {
    map.push(input[lineIndex++].split(' ').map(Number));
  }

  const visited = Array(h).fill().map(() => Array(w).fill(false));

  let islandCount = 0;

  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (map[i][j] === 1 && !visited[i][j]) {
        dfs(map, visited, i, j, h, w);
        islandCount++;
      }
    }
  }

  results.push(islandCount);
}

function dfs(map, visited, i, j, h, w) {

  if (i < 0 || i >= h || j < 0 || j >= w) return;

  if (visited[i][j] || map[i][j] === 0) return;

  visited[i][j] = true;

  const directions = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1, -1],  [1, 0],  [1, 1]
  ];

  for (const [dx, dy] of directions) {
    dfs(map, visited, i + dx, j + dy, h, w);
  }
}

console.log(results.join('\n'));

성능

• 시간복잡도(실행속도): 172 ms

• 공간복잡도(메모리): 12464 KB

개선할 점

• 재귀 호출을 사용하는 DFS는, 지도 크기가 클 경우 스택 오버플로우 발생 가능성 ⬆️

• BFS를 사용하면 이런 문제를 피할 수 있고, 특히 자바스크립트에서는 더 효율적일 수 있음

참고 https://bedecked-operation-4d1.notion.site/99-6-TIL-1ceeb405261e809699ffcb380cbc3e32

문제: https://www.acmicpc.net/problem/2559 알고리즘 분류: 누적 합, 슬라이딩 윈도우, 두 포인터

문제 파악

N일 동안의 온도 데이터가 주어짐 연속된 K일 동안의 온도 합을 계산 가능한 모든 연속된 K일 기간 중에서 온도 합이 최대인 값을 찾아야 함

접근 방법

슬라이딩 윈도우(Sliding Window) 알고리즘

• 배열이나 문자열과 같은 데이터 구조에서 연속된 요소들의 집합을 처리할 때 사용하는 기법

슬라이딩 윈도우 접근법:

• 처음 K개 요소의 합을 계산

• 윈도우를 한 칸씩 오른쪽으로 이동하면서:

  • 왼쪽 끝 요소를 제거
  • 오른쪽에 새로운 요소 추가
  • 최대값 갱신

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

function findMaxTemperatureSum(N, K, temperatures) {
  // 처음 K일 동안의 온도 합 계산
  let currentSum = 0;
  for (let i = 0; i < K; i++) {
    currentSum += temperatures[i];
  }

  // 최대값을 현재 합으로 초기화
  let maxSum = currentSum;

  // 슬라이딩 윈도우 적용
  for (let i = K; i < N; i++) {
    // 윈도우 이동: 왼쪽 끝 요소 제거하고 오른쪽 새 요소 추가
    currentSum = currentSum - temperatures[i - K] + temperatures[i];

    // 최대값 갱신
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

// 입력 처리
function solution(input) {
  const lines = input.trim().split('\n');
  const [N, K] = lines[0].split(' ').map(Number);
  const temperatures = lines[1].split(' ').map(Number);

  return findMaxTemperatureSum(N, K, temperatures);
}

console.log(solution(input));

참고: https://bedecked-operation-4d1.notion.site/99-5-TIL-1cbeb405261e8038a22fcdea4309d5c4

문제: https://www.acmicpc.net/problem/2468 알고리즘 분류: 너비 우선 탐색, 브루트포스 알고리즘, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

컨디션 이슈

• 감기에 제대로 걸려서 오늘 하루 책상에 앉아있는 게 고역이었다
• 3시간 고민하고도 문제 해결이 어려워서 이론부터 공부하기로 했다
• 구글링과 ai의 힘을 빌려 힌트를 얻고, 답을 완성해나갔다
• 더 나은 개선방안이 있는 지 추후 고민하고 정리해보려고 한다

문제 요약

• N×N 크기의 2차원 배열에 각 지점의 높이가 주어진다
• 비가 내려 특정 높이 이하의 지점이 모두 물에 잠긴다
• 물에 잠기지 않는 안전한 영역이란 물에 잠기지 않는 지점들이 상하좌우로 인접해 있는 지역이다
• 다양한 강수량(비의 양)에 따라 안전한 영역의 개수가 달라질 때, 안전한 영역의 최대 개수를 구해야 한다

접근 방법

이 지역에서 가능한 모든 강수량에 대해 시뮬레이션을 해봐야 합니다. 각 시뮬레이션에서 안전한 영역의 개수를 계산하고, 그 중 최댓값을 찾습니다. 안전한 영역의 개수는 DFS나 BFS를 이용해 구할 수 있습니다.

DFS와 BFS 개념 설명

DFS(깊이 우선 탐색)

• 그래프나 트리에서 깊이를 우선적으로 탐색하는 알고리즘
• 한 경로를 끝까지 탐색한 후 다른 경로를 탐색
• 주로 재귀 함수나 스택을 이용하여 구현

BFS(너비 우선 탐색)

• 그래프나 트리에서 너비를 우선적으로 탐색하는 알고리즘
• 시작점에서 가까운 노드부터 차례대로 탐색

참고 https://bedecked-operation-4d1.notion.site/99-4-TIL-DFS-BFS-1caeb405261e80ca84a8ecaef620f1ab

문제: https://school.programmers.co.kr/learn/courses/30/lessons/161990 바탕화면에 있는 모든 파일('#')을 포함하는 가장 작은 직사각형을 찾는 문제

문제분석

• 바탕화면은 격자 형태이며, 각 칸은 '.'(빈 칸) 또는 '#'(파일)로 표시
• 모든 파일을 한 번에 선택하기 위한 최소 크기의 드래그 영역을 찾아야 한다
• 드래그 영역은 시작점 (lux, luy)와 끝점 (rdx, rdy)로 정의

문제 접근방법

• 모든 파일 위치를 확인하며 가장 작은 x, y 좌표와 가장 큰 x, y 좌표를 찾아야 함
• 가장 작은 좌표 → 드래그 시작점 S(lux, luy)
• 가장 큰 좌표+1 → 드래그 끝점 E(rdx, rdy)
• ⚠️ 끝점은 파일 위치보다 1 더 크게 설정해야 함 why? 파일을 완전히 포함하기 위해
  • 드래그는 격자점을 기준인데, 파일은 격자 칸에 있음
  • 파일이 있는 칸을 완전히 포함하려면 그 칸의 오른쪽 아래 격자점까지 드래그해야 함

내 코드

function solution(wallpaper) {
    // 초기값 설정 (최소값은 가능한 최대로, 최대값은 가능한 최소로 설정)
    let lux = wallpaper.length;
    let luy = wallpaper[0].length;
    let rdx = 0;
    let rdy = 0;

    // 모든 파일 위치 확인
    for (let i = 0; i < wallpaper.length; i++) {
        for (let j = 0; j < wallpaper[i].length; j++) {
            if (wallpaper[i][j] === '#') {
                // 파일을 발견하면 시작점과 끝점 좌표 업데이트
                lux = Math.min(lux, i);
                luy = Math.min(luy, j);
                rdx = Math.max(rdx, i);
                rdy = Math.max(rdy, j);
            }
        }
    }

    // 드래그 끝점은 파일 위치보다 1 더 크게 설정해야 함
    return [lux, luy, rdx + 1, rdy + 1];
}

내 코드 성능

메모리: 33.6 MB, 시간: 0.54 ms

개선된 코드

참고: deun블로그

function solution(wallpaper) {
    let lux = wallpaper.length;
    let luy = wallpaper[0].length;
    let rdx = 0;
    let rdy = 0;

    for (let i = 0; i < wallpaper.length; i++) {
        if (!wallpaper[i].includes('#')) continue; // ✅

        lux = Math.min(lux, i);
        rdx = Math.max(rdx, i + 1);
        luy = Math.min(luy, wallpaper[i].indexOf('#')); // ✅
        rdy = Math.max(rdy, wallpaper[i].lastIndexOf('#') + 1); // ✅
    }

    return [lux, luy, rdx, rdy];
}

• 중첩된 반복문 제거 후 내장 메서드(indexOf, lastIndexOf)를 활용
  • 하나의 반복문으로 모든 계산을 수행
  • 각 행마다 최소/최대 인덱스를 바로 찾아 처리
• 파일이 없는 행(if (!wallpaper[i].includes('#')) continue;)은 빠르게 건너 뜀
• 성능 개선
  • 메모리: 33.6 MB → 33.4 MB,
  • 시간: 0.54 ms → 0.23 ms

indexOf(), lastIndexOf() 리뷰하기

indexOf() 메서드

배열이나 문자열에서 특정 요소나 문자의 첫 번째 등장 위치(인덱스)를 찾아 반환 찾는 요소가 없으면 -1을 반환

array.indexOf(searchElement, [fromIndex])
string.indexOf(searchValue, [fromIndex])

searchElement/searchValue: 찾을 요소 또는 문자열 fromIndex (선택적): 검색을 시작할 인덱스 (안 써주면 기본값 0)

사용 예) 특정 문자 이후의 내용 추출 - URL에서 쿼리 파라미터 추출

const url = 'https://example.com/search?query=javascript&limit=10';
const queryStartIndex = url.indexOf('?');

if (queryStartIndex !== -1) {
  const queryString = url.substring(queryStartIndex + 1);
  console.log('쿼리 문자열:', queryString); // 'query=javascript&limit=10'
}

lastIndexOf() 메서드

배열이나 문자열에서 특정 요소나 문자의 마지막 등장 위치(인덱스)를 찾아 반환 찾는 요소가 없으면 -1을 반환

array.lastIndexOf(searchElement, [fromIndex])
string.lastIndexOf(searchValue, [fromIndex])

searchElement/searchValue: 찾을 요소 또는 문자열 fromIndex (선택적): 역방향 검색을 시작할 인덱스 (기본값: array.length-1 또는 string.length-1)

사용 예 1) 파일 경로에서 파일명 추출하기

const filePath = '/users/documents/projects/report.pdf';
const lastSlashIndex = filePath.lastIndexOf('/');
const fileName = filePath.substring(lastSlashIndex + 1);
console.log('파일명:', fileName); // 'report.pdf'

사용 예 2) 중복 요소 중 마지막 위치 찾기

// 배열에서 중복된 요소의 마지막 위치 찾기
const numbers = [2, 5, 9, 2, 7, 5, 3, 5];
const lastFiveIndex = numbers.lastIndexOf(5); // 7 반환

console.log('마지막 5의 위치:', lastFiveIndex);

// 특정 위치 이전의 마지막 등장 위치 찾기
const previousFiveIndex = numbers.lastIndexOf(5, 6); // 5 반환
console.log('인덱스 6 이전의 마지막 5 위치:', previousFiveIndex);

실제 사용 범위

1. 문자열 처리 작업 단순화:

• URL 파싱
• 파일 경로 처리
• 이메일 검증
• 텍스트 분석

2. 데이터 검증과 처리:

• 입력값 유효성 검사
• 데이터 추출 및 변환

참고 https://bedecked-operation-4d1.notion.site/99-3-TIL-1c9eb405261e80f2b3b8e14bf17779e9

문제: https://www.acmicpc.net/problem/14495 알고리즘 분류: 다이나믹 프로그래밍

초기 접근 방식

1. 점화식 이해: f(n) = f(n-1) + f(n-3)는 현재 값이 바로 전 값과 3단계 전 값의 합임
2. 초기값 설정: f(1) = f(2) = f(3) = 1로 명확하게 설정
3. 효율적인 메모리 사용: 수열을 계산할 때 이전 값들을 재사용하는 동적 프로그래밍 접근법이 필요

내 코드(1차 시도)

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

let n = Number(input);

// 피보나치 비스무리한 수열 계산
function fibonacciLike(n) {
    // 기본 케이스: f(1) = f(2) = f(3) = 1
    let fib = [1, 1, 1]; // 배열초기화

    // n이 3 이하면 바로 결과 반환
    if (n <= 3) {
        return fib[n-1];
    }

    // n이 4 이상이면 수열 계산
    for (let i = 3; i < n; i++) {
        // f(n) = f(n-1) + f(n-3) 공식 적용
        fib[i] = fib[i-1] + fib[i-3];
    }

    return fib[n-1];
}

console.log(fibonacciLike(n));

추가 설명

let fib = [1, 1, 1];

for (let i = 3; i < n; i++) {
  fib[i] = fib[i-1] + fib[i-3];
}

• fib[0]은 f(1), fib[1]은 f(2), fib[2]는 f(3)

그러므로,

• f(n)은 fib[n-1]
• f(n-1)은 fib[n-2]
• f(n-3)은 fib[n-4]

for루프에서 i는 배열의 인덱스이고,

• fib[i]는 f(i+1)
• fib[i-1]은 f(i)
• fib[i-3]은 f(i-2)

결과적으로, 이 코드는 f(i+1) = f(i) + f(i-2)를 계산하는데, 이는 수학적 표기법으로는 f(n) = f(n-1) + f(n-3)와 동일 ➡️ 인덱스와 수열의 위치 사이에 1의 차이가 있어서(fib[i]가 f(i+1)을 나타냄)

배열 인덱싱과 관련된 오류와 코드수정(2차 시도)

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

let n = Number(input);

// 피보나치 비스무리한 수열 계산
function fibonacciLike(n) {
    // 기본 케이스: f(1) = f(2) = f(3) = 1
    let dp = new Array(n+1);
    dp[1] = dp[2] = dp[3] = 1;

    // n이 3 이하면 바로 결과 반환
    if (n <= 3) {
        return dp[n];
    }

    // n이 4 이상이면 수열 계산
    for (let i = 4; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-3];
    }

    return dp[n];
}

console.log(fibonacciLike(n));

추가 설명

1. 배열 이름변경: fib → dp (동적 프로그래밍 접근임을 명시)
2. 배열을 0부터가 아닌 1부터 인덱싱하도록 변경 (new Array(n+1) 사용) ➡️ 코드의 가독성을 높이기 위해 배열의 인덱스를 수열의 위치와 일치
3. dp[1], dp[2], dp[3]을 직접 1로 초기화
4. 반복문은 i = 4부터 시작하여 i <= n까지 실행
5. dp[n]을 반환하여 n번째 값을 리턴

1-based indexing 방식

배열 자체는 여전히 0부터 시작하지만, 우리가 0번 인덱스를 의도적으로 무시하고 1번부터 사용하는 것

new Array(n+1)로 배열을 생성하면:

크기가 n+1인 배열이 만들어 짐 예를 들어 n=5라면 크기가 6인 배열이 생성되고, 이 배열은 0번 인덱스부터 n번 인덱스까지 가짐 [undefined, undefined, undefined, undefined, undefined, undefined]

이제 0번 인덱스는 사용하지 않고, 1번부터 n번 인덱스를 사용:

dp[1]은 수열의 첫 번째 항 dp[2]는 수열의 두 번째 항 dp[3]은 수열의 세 번째 항 ... dp[n]은 수열의 n번째 항

이렇게 하면 코드에서 dp[i]가 정확히 수열의 i번째 항을 가리키게 되어, 수학적 표기법과 코드의 표기법이 일치하게 됨 따라서, 점화식 f(n) = f(n-1) + f(n-3)을 그대로 dp[i] = dp[i-1] + dp[i-3]으로 구현할 수 있어 코드가 더 직관적이고 이해하기 쉬워짐

런타임에러와 구현범위와 BitInt(최종 코드)

• 구현범위가 n이 최대 116까지 갈 수 있다고 명시되어 있으므로, 피보나치 비스무리한 수열의 값이 JavaScript의 Number 타입으로 표현할 수 있는 범위를 초과할 수 있음

• JavaScript에서 안전하게 표현할 수 있는 정수의 최대값은 Number.MAX_SAFE_INTEGER로 약 9007조(9,007,199,254,740,991)

• n이 116일 때의 값은 이 범위를 넘어갈 가능성이 높음

• 따라서, BigInt를 사용하여 코드를 수정 → 큰 수에 대한 처리가 필요

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

let n = Number(input);

// 피보나치 비스무리한 수열 계산
function fibonacciLike(n) {
    // 기본 케이스: f(1) = f(2) = f(3) = 1
    let dp = new Array(n+1);
    dp[1] = dp[2] = dp[3] = 1n; // BigInt 리터럴 사용 ✅

    // n이 3 이하면 바로 결과 반환
    if (n <= 3) {
        return dp[n];
    }

    // n이 4 이상이면 수열 계산
    for (let i = 4; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-3];
    }

    return dp[n];
}

console.log(fibonacciLike(n).toString()); // BigInt를 문자열로 변환하여 출력

주요 변경 사항

• 초기값을 1n으로 설정하여 BigInt 타입을 사용
• 결과 반환 시 .toString()을 사용하여 BigInt 값을 문자열로 변환 (BigInt는 console.log에서 "n"이 붙어서 출력됨)
• 이 수정으로 큰 수에 대해서도 정확한 계산이 가능

피보나치 수열은 매우 빠르게 증가하기 때문에, n이 큰 경우에는 이런 BigInt 처리가 필수적

맺으며

• 처음엔 단순 구현을 위해 배열의 인덱스와 수열의 위치가 달랐고,(1차 시도)
• 동적 프로그래밍 접근임을 명시 후 인덱스와 수열의 위치를 일치시켰다. (2차 시도)
• 런타임 에러 후 구현범위를 고려하여 BigInt를 사용해 최종 코드를 만들었다.
• 피보나치 수열은 매우 빠르게 증가하기 때문에 BigInt처리가 필수적이라는 것도 알게 되었다.
• 동적 프로그래밍과 BigInt에 대해 조금 더 공부해 봐야 겠다.

참고 https://bedecked-operation-4d1.notion.site/99-2-TIL-DP-Dynamic-programming-1c8eb405261e805b9f60e5da9096caaa

문제: https://leetcode.com/problems/top-k-frequent-elements/description/ 알고리즘 분류: Array Hash Table Divide and Conquer Sorting Heap (Priority Queue) Bucket Sort Counting Quickselect

접근방법

• 빈도수 계산
  • Map을 사용 ➡️ 각 숫자가 배열에서 몇 번 등장하는지 계산
• 버킷 정렬
  • 문제의 요구사항에 따라 O(n log n)보다 빠른 시간 복잡도가 필요
  • 버킷 정렬 시간 복잡도 : O(n)
• 결과 추출
  • 가장 높은 빈도수를 가진 버킷부터 시작 ➡️ k개의 요소를 결과 배열에 추가

내 코드

function topKFrequent(nums, k) {
    // 각 숫자의 빈도수를 저장할 Map 생성
    const frequencyMap = new Map();

    // 모든 숫자의 빈도수 계산
    for (const num of nums) {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    }

    // 빈도수를 기준으로 내림차순 정렬된 배열 생성
    // 시간 복잡도는 O(n log n)이 아닌 O(n)을 달성하기 위해 버킷 정렬 사용
    const buckets = Array(nums.length + 1).fill().map(() => []);

    // 각 숫자를 빈도수에 해당하는 버킷에 넣기
    for (const [num, freq] of frequencyMap) {
        buckets[freq].push(num);
    }

    // 결과 배열
    const result = [];

    // 가장 높은 빈도수부터 시작하여 k개의 요소를 결과 배열에 추가
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        if (buckets[i].length > 0) {
            result.push(...buckets[i].slice(0, k - result.length));
        }
    }

    return result;
}