• Public Cloud 서비스 공급자가 클라우드를 구성하는 자원과 환경들을 모두 가지고 구축을 한 다음에 사용자에게 제공

• Private Cloud 클라우드 서비스를 하기 위해 필요한 환경이나 데이터센터, 네트워크 장비, 서버등을 구축해서 서비스를 하는것

• Hybrid Cloud Public Cloud와 Private Cloud를 혼용해서 사용하는 클라우드

유연성

사용자는 자신의 니즈에 맞게 서비스를 확장, 애플리케이션을 커스터마지으하고, 인터넷 연결을 통해 어디서나 클라우드 서비스를 이용할 수 있다.

효율성

사용자는 기본 인프라 비용 또는 유지보수에 대한 걱정 없이 컴퓨팅 자원을 사용하며 애플리케이션을 빠르게 구축할 수 있다 비용, 시간, 공간 등의 제한없이 사용자의 주문형 서비스 사용이 가능한 클라우드 컴퓨팅

전략적 가치

클라우드 컴퓨팅 사용은 가장 최신의 컴퓨팅 기술을 제공함으로써 기업이 경쟁 우위를 확보 할 수 있도록 한다 클라우드 서비스 제공업체에서 사전에 구축, 유지보수, 관리서비스 등이 제공되는 글로벌 인프라 서비스, 인스턴스, 네트워크, 스토리지, 보안서비스등 요구에 따라 선택적으로 사용하여 시간, 비용 절약

이미지 출처 : https://getlogovector.com/tailwind-css-logo-vector-svg/

Tailwind CSS 란?

많은 유틸리티(utility) 클래스로 이루어진 CSS 프레임워크입니다. Tailwind가 제공하는 유틸리티 클래스들을 다양하게 조합하면 추가적인 CSS 코드 작성없이 단순히 HTML 요소의 class속성에 설정해주는 것만으로도 스타일링이 가능하게 됩니다.

CSS의 속성들을 클래스에 직관적으로 표현함으로써 효율적으로 사용할 수 있게 됩니다. 스타일링에 필요한 대부분의 속성들이 클래스 형태로 사전에 정의되어 있고 사용자는 클래스들을 조합해서 사용하면 됩니다.

여기서 유틸리티 클래스란 딱 한 가지 일만 하는 매우 적은 양의 CSS 코드를 담고 있는 클래스를 뜻하는데요. 보통 유틸리티 클래스를 단독으로 쓰기 보다는 여러 개의 유틸리티 클래스를 함께 사용해야지 의미있는 스타일링을 할 수 있습니다.

반복적으로 사용되는 스타일들을 컴포넌트로 추상화하여 재사용할 수 있습니다. 기본적으로 제공되는 유틸리티 클래스 외에도, 프로젝트 요구사항에 맞게 테마를 확장하거나 새로운 유틸리티 클래스를 추가하여 커스터마이징할 수 있습니다.

장점

• 클래스의 이름을 고민하지 않아도 됩니다.
• 쉽게 반응형 페이지를 구현할 수 있도록 지원합니다.
• 기본적으로 제공하는 BreakPoint가 존재하기 때문에 복잡한 반응형 디자인도 쉽게 구현할 수 있습니다.
• 따로 커스터마이징이 가능합니다.
• 기본 정의된 테마를 확장할 수도 있고 새로운 속성을 추가할 수 있습니다.
• 반복되는 스타일은 컴포넌트 추상화, 클래스 추상화를 통해서 재사용 가능합니다.
• 공식문서가 매우 친절하고 학습 난이도가 낮습니다.
• 다크 모드 지원 dark: 프리픽스 방식으로 지원 ( 스타일을 직접 추가 하는 방식 ) 조금 불편한 방법일 수도 있지만 모듈화가 잘 이루어지면 나중에 dark 클래스 추가만으로도 손쉽게 다크모드를 적용할 수 있습니다.
• Tailwind CSS 공식 커뮤니티가 존재하며 컴포넌트 또는 완성된 페이지들도 제공합니다.

단점

• 코드의 직관성은 좋으나 가시성은 떨어집니다. -> https://marketplace.visualstudio.com/items?itemName=heybourn.headwind 해당 플러그인으로 어느정도 해소가 가능합니다.

• 초기 학습 곡선: Tailwind의 유틸리티 클래스가 많아 익숙해지기까지 시간이 걸릴 수 있습니다.

• 클래스 중복: HTML 코드에 많은 클래스가 중첩될 수 있어 가독성이 떨어질 수 있습니다.

• 의존성 문제: 프로젝트의 스타일링이 Tailwind에 종속되므로, 다른 CSS 프레임워크로 전환하기 어려울 수 있습니다.

• JSX의 가독성 저하: React 같은 프레임워크에서 JSX 코드가 복잡해질 수 있습니다.

• 커스터마이징 제약: 매우 구체적인 디자인 커스터마이징이 필요한 경우 Tailwind의 기본 제공 클래스만으로는 한계가 있을 수 있습니다.

언제 사용해야 하는가?

디자이너와 협업하며 빠르게 UI를 반복해야 할 때 작은 팀이나 개인 프로젝트에서 CSS 관리 복잡도를 낮추고 싶을 때 디자인 시스템을 코드로 일관되게 유지해야 할 때

결론

Tailwind CSS는 유틸리티 중심의 접근으로 '어떻게 스타일을 적용할 것인가'에 집중하게 해 주며, 대규모 프로젝트에서도 일관된 디자인을 유지하게 도와줍니다. 클래스가 많아지면 HTML이 복잡해질 수 있으므로, 필요할 땐 @apply 지시자를 써서 별도의 컴포넌트 클래스에 묶어 관리하는 방식도 병행해 보는거를 추천합니다.

AI로 바이브 코딩하는 것은 개발자로 성장하기에는 큰 도움이 안되는 것을 어느정도 인지하고있기에 AI로는 기본적인 틀만 참고하고 문제점은 스스로 해결하려고 하지만 시간에 쫒겨 결국 AI를 이용하면서 바이브 코딩화가 되가는 내 자신을 보게 되어 자책감도 생기고 자신감도 너무 떨어지게 되면서 그동안 해왔던 모든 준비가 부정당하는 기분이 들기 시작한다.

도대체 어떻게하면 남들보다 잘하지는 못하더라도 비슷하게라도 할수 있는지 큰 고민이 들기 시작했다. 백준에서 문제를 풀어볼때도 브론즈 5~3정도는 자신감있게 풀었지만 실버 이상의 문제를 풀기시작해면서 푸는데도 시간이 너무 걸리고 알고리즘 적으로도 너무 부족해보이는 내가 보이기 시작했다.

일주일간 기초부터 다시 다지기 위해 CS를 다시 되짚어보면서 고민하는 시간을 가져야할거 같다.

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제

해결

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

const arr = input.shift();

input.sort((a,b) => a - b);

console.log(input.join("\n"))

const arr = input.shift();

첫번째 값은 개수 출력 후에는 사용하지 않으므로 shift처리로 배열에서 없애줍니다.

input.sort((a, b) => a - b);

sort의 비교 함수를 통해 숫자를 오름차순으로 정렬합니다. (a, b) => a - b는 a가 b보다 작으면 음수, 크면 양수를 반환해서 원하는 순서를 만듭니다.

자연수 N이 주어졌을 때, 1부터 N까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 100,000보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄부터 N번째 줄 까지 차례대로 출력한다.

예제

해결

const fs = require("fs")
const input = fs.readFileSync("/dev/stdin").toString().split(" ");

const a = Number(input);

let str = ''
for(let i = 1; i <= a; i++) {
    str = str+i+'\n'
    }

console.log(str);

N * M크기의 두 행렬 A와 B가 주어졌을 때, 두 행렬을 더하는 프로그램을 작성하시오.

입력

첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.

출력

첫째 줄부터 N개의 줄에 행렬 A와 B를 더한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.

예제

해결

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

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

for (let i = 1; i <= N; i++) {
  A.push(input[i].split(" ").map(Number));
}

for (let i = N + 1; i <= N * 2; i++) {
  B.push(input[i].split(" ").map(Number));
}

const result = [];

for (let i = 0; i < N; i++) {
  const row = [];
  for (let j = 0; j < M; j++) {
    row.push(A[i][j] + B[i][j]);
  }
  result.push(row.join(" "));
}

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

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

첫 번째 줄 input[0]을 공백 기준으로 나눈 뒤 map(Number)로 숫자 배열로 변환하여, N(행 수)과 M(열 수)에 각각 할당합니다.

const A = [];
for (let i = 1; i <= N; i++) {
  A.push(input[i].split(" ").map(Number));
}

두 번째 줄(input[1])부터 input[N]까지 총 N줄을 순회하며, 각 줄을 공백으로 나눠 숫자 배열로 만든 뒤(.split(" ").map(Number)) A 배열에 한 행씩 push 합니다.

const B = [];
for (let i = N + 1; i <= N * 2; i++) {
  B.push(input[i].split(" ").map(Number));
}

이어서 input[N+1]부터 input[2N]까지 읽어, 같은 방식으로 2차원 배열 B를 만듭니다.

const result = [];
for (let i = 0; i < N; i++) {
  const row = [];
  for (let j = 0; j < M; j++) {
    row.push(A[i][j] + B[i][j]);
  }
  result.push(row.join(" "));
}

빈 배열 result를 만들고, 이중 for문으로 각 행(i)과 각 열(j)을 순회하면서 A[i][j] + B[i][j]로 같은 위치 원소를 더해 row 배열에 추가합니다. 한 행의 덧셈이 끝나면 row.join(" ")로 공백 구분 문자열로 바꿔 result에 담습니다.

문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다.

QR Code "alphanumeric" 문자는 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ$%*+-./: 이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 반복 횟수 R(1 ≤ R ≤ 8), 문자열 S가 공백으로 구분되어 주어진다. S의 길이는 적어도 1이며, 20글자를 넘지 않는다.

출력

각 테스트 케이스에 대해 P를 출력한다.

예제

해결

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

const repeat = parseInt(input[0]);

for(let i = 1; i <= repeat; i++) {
    const [r, s] = input[i].split(' ');
    let result = '';
  for (const char of s) {
    for (let j = 0; j < parseInt(r); j++) {
      result += char;
    }
  }
  console.log(result);
}

for (let i = 1; i <= repeat; i++) {
  const [r, s] = input[i].split(' ');
  let result = '';
}

i = 1부터 repeat까지 순회하며, 각 줄(input[i])을 공백 기준으로 나눠 [r, s]로 비구조화 할당합니다. r: 반복 횟수 (문자 하나를 몇 번 반복할지) s: 대상 문자열 result라는 빈 문자열을 만들어 반복 결과를 누적합니다.

for (const char of s) {
  for (let j = 0; j < parseInt(r); j++) {
    result += char;
  }
}

문자열 s의 각 문자(char)에 대해 0부터 r-1까지 반복하면서(j < parseInt(r)) result += char로 저장합니다

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. 넓이 우선 탐색 (BFS)이 깊이 우선 탐색 (DFS)보다 좀 더 복잡하다.

넓이 우선 탐색(BFS)의 특징

• 직관적이지 않은 면이 있다. BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.

• BFS는 재귀적으로 동작하지 않는다.

• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 즉, 선입선출(FIFO) 원칙으로 탐색 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

• 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 가중치가 없는 그래프에서는 시작점에서 끝점까지의 최단경로를 알아낼 수 있다.

• ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

넓이 우선 탐색(BFS)의 과정정

깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

1. a 노드(시작 노드)를 방문한다. (방문한 노드 체크)

• 큐에 방문된 노드를 삽입(enqueue)한다.
• 초기 상태의 큐에는 시작 노드만이 저장
• 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.

2. 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.

• 큐에서 꺼낸 노드를 방문한다.
• 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
• 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
• 큐에 방문된 노드를 삽입(enqueue)한다.

3. 큐가 소진될 때까지 계속한다.

넓이 우선 탐색의 시간복잡도

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)
• 깊이 우선 탐색(DFS)과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

예제

해결

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

const N = input[0];
const paper = [];
for (let i = 0; i < N; i++) {
  paper.push(input.slice(1 + i * N, 1 + (i + 1) * N));
}

let white = 0;
let blue = 0;

function countColor(x, y, size) {
  const first = paper[y][x];
  let allSame = true;

  for (let i = y; i < y + size; i++) {
    for (let j = x; j < x + size; j++) {
      if (paper[i][j] !== first) {
        allSame = false;
        break;
      }
    }
    if (!allSame) break;
  }

  if (allSame) {
    if (first === 0) white++;
    else blue++;
  } else {
    const half = size / 2;
    countColor(x, y, half); // 왼쪽 위
    countColor(x + half, y, half); // 오른쪽 위
    countColor(x, y + half, half); // 왼쪽 아래
    countColor(x + half, y + half, half); // 오른쪽 아래
  }
}

countColor(0, 0, N);

console.log(white);
console.log(blue)

const paper = [];
for (let i = 0; i < N; i++) {
  paper.push(input.slice(1 + i * n, 1 + (i + 1) * n));
}

뒤이어 들어오는 n×n개의 숫자를 한 줄씩 잘라 paper[y][x] 형태의 2차원 배열로 만듭니다. 0은 흰색, 1은 파란색 칸을 의미합니다.

function countColor(x, y, size) {
  const first = paper[y][x];
  let allSame = true;
   // 현재 크기(size×size) 범위 안에 칸들이 모두 first(0 또는 1)와 같은지 검사
  for (let i = y; i < y + size; i++) {
    for (let j = x; j < x + size; j++) {
      if (paper[i][j] !== first) {
        allSame = false;
        break;
      }
    }
    if (!allSame) break;
  }
  if (allSame) {
    // 모두 같은 색이면 해당 색 카운트 증가
    if (first === 0) white++;
    else blue++;
  } else {
    // 아니면 크기를 반으로 나누어 네 개의 분할 영역에 대해 재귀 호출
    const half = size / 2;
    countColor(x, y, half); // 왼쪽 위
    countColor(x + half, y, half); // 오른쪽 위
    countColor(x, y + half, half); // 왼쪽 아래
    countColor(x + half, y + half, half); // 오른쪽 아래
  }
}

해당 영역이 모두 같은 색(allSame===true)이면 더 이상 분할하지 않고 바로 white 또는 blue를 1 증가시킵니다. 섞여 있는 영역이라면 size/2 크기로 4분면(쿼드트리 방식)으로 나누어 각각 검사합니다.

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제

해결

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

const meetings = input.slice(1).map(line => {
  const [start, end] = line.split(' ').map(Number);
  return { start, end };
});

meetings.sort((a, b) => a.end - b.end || a.start - b.start);

let count = 0;
let lastEnd = 0;
for (const { start, end } of meetings) {
  if (start >= lastEnd) {
    count++;
    lastEnd = end;
  }
}

console.log(count);

const meetings = input.slice(1).map(line => {
  const [start, end] = line.split(' ').map(Number);
  return { start, end };
});

두 번째 줄부터 마지막 줄까지 각 줄을 시작 시간 & 끝 시간 형태로 읽어 { start: Number, end: Number } 객체 배열로 변환합니다.

meetings.sort((a, b) => a.end - b.end || a.start - b.start);

끝나는 시간(end) 기준 오름차순 정렬합니다. 만약 끝나는 시간이 같다면, 시작 시간(start) 기준으로 오름차순 정렬해 같은 종료 시간 회의끼리는 일찍 시작하는 회의를 먼저 고려하도록 합니다.

let count = 0;
let lastEnd = 0;
for (const { start, end } of meetings) {
  if (start >= lastEnd) {
    count++;
    lastEnd = end;
  }
}

lastEnd 변수에는 이전에 선택한 회의의 종료 시각을 저장합니다. 정렬된 회의들을 순서대로 보면서 현재 회의의 시작 시간이 lastEnd값 이상이면 count를 하나 올리고 lastEnd를 현재 회의의 끝나는 시간으로 갱신합니다. 그렇지 않으면 건너뛰어 다음 회의 후보를 검사합니다.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

깊이 수선 탐색의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

장점

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.

• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.

• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

깊이 우선 탐색의 시간 복잡도

DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2) 즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제

해결

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

const a = Array(input + 1).fill(0);

for (let i = 2; i <= input; i++) {
    a[i] = a[i - 1] + 1;

    if (i % 2 === 0) {
        a[i] = Math.min(a[i], a[i / 2] + 1);
    }

    if (i % 3 === 0) {
        a[i] = Math.min(a[i], a[i / 3] + 1);
    }
}

console.log(a[input]);

a[i - 1] + 1 은 i에서 1을 빼는 연산을 한 번 한 뒤, 남은 값 ( i − 1 )를 1로 만드는 연산 횟수(a[i-1])에 더합니다.

i % 2 === 0 i가 2의 배수일 때 i/2에서 2를 곱해 i가 된다고보고 (a[i - 1] + 1) 중 작은 쪽을 선택합니다.

i % 3 === 0 이면 i/3에서 3을 곱해 i가 된다고 보고, a[i] = min(a[i],a(i/3)+1)으로 갱신

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제

해결

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map((item) => Number(item));

let a = input[0];
let b = input[1];

while(a % b !== 0){
    let r = a % b;

       if(r !== 0){
        a = b;
        b = r;
    }
}
console.log(b);
console.log((input[0] * input[1]) / b);

유클리드 호제법으로 구하는 문제입니다. 유클리드 호제법에 대한 내용은 해당링크에 정리되어 있습니다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

while (a % b !== 0) {
    let r = a % b;
    if (r !== 0) {
        a = b;
        b = r;
    }
}

a % b가 0이 아닐 동안(while (a % b !== 0)) 반복해서: r = a % b 로 나머지를 구하고 그 나머지(r)가 0이 아니면 a <- b, b <- r 로 값을 갱신합니다.

console.log(b);
console.log((input[0] * input[1]) / b);

반복이 끝난 시점의 b를 출력합니다. 이 값이 바로 최대공약수입니다.

두 수의 곱을 최대공약수로 나오면 최소공배수가 나오므로 console.log((input[0] * input[1]) / b); 를 출력해줍니다.

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다. 최소공배수, 최대공약수를 구하기 위해서는 다음과 같은 표를 쓴다.

(출처 : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95)

알고리즘

입력으로 두 수 m,n(m>n)이 들어온다. n이 0이라면, m을 출력하고 알고리즘을 종료한다. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다. 위 과정은 “n, m에 대해서 나머지 연산을 실시할 수 있다”라는 조건에만 의존하므로, 정수환뿐 아니라, 임의의 유클리드 정역에 대해도 똑같은 과정을 거치면 공약인자가 구해진다.

예시

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21 42는 21로 나누어 떨어진다. 따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 ＋ 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 ＋ 0

따라서, 최대공약수는 36이다.

<그림 1>과 같이 9×9 격자판에 쓰여진 81개의 자연수 또는 0이 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.

예를 들어, 다음과 같이 81개의 수가 주어지면

이들 중 최댓값은 90이고, 이 값은 5행 7열에 위치한다.

입력

첫째 줄부터 아홉 번째 줄까지 한 줄에 아홉 개씩 수가 주어진다. 주어지는 수는 100보다 작은 자연수 또는 0이다.

출력

첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다.

예제

해결

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

const matrix = input.map(line => line.split(" ").map(Number));
const flat = matrix.flat();
const max = Math.max.apply(null, flat);

let row = 0;
let col = 0;

for (let i = 0; i < 9; i++) {
  for (let j = 0; j < 9; j++) {
    if (matrix[i][j] === max) {
      row = i + 1;
      col = j + 1;
    }
  }
}

console.log(max);
console.log(${row} ${col});

const matrix = input.map(line => line.split(" ").map(Number));

각 줄(line)을 공백으로 나눠 숫자 문자열 배열로 만들고, map(Number)로 다시 숫자로 변환해 2차원 배열 matrix를 구성합니다.

const flat = matrix.flat();
const max = Math.max.apply(null, flat);

matrix.flat()로 9×9 배열을 1차원(길이 81) 배열로 펴고, 펴진 배열을 Math.max에 인자로 풀어(apply(null, flat)) 최댓값 max를 구합니다.

let row = 0;
let col = 0;
for (let i = 0; i < 9; i++) {
  for (let j = 0; j < 9; j++) {
    if (matrix[i][j] === max) {
      row = i + 1;
      col = j + 1;
    }
  }
}

2중 for문으로 원본 matrix를 순회하며 각 요소가 max와 같을 때의 인덱스를 찾습니다. i는 행, j는 열을 나타내므로, 출력은 1부터 시작하는 행과 열의 번호를 요구하므로 i+1, j+1을 저장합니다.

9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오. 예를 들어, 서로 다른 9개의 자연수 3, 29, 38, 12, 57, 74, 40, 85, 61 이 주어지면, 이들 중 최댓값은 85이고, 이 값은 8번째 수이다.

입력

첫째 줄부터 아홉 번째 줄까지 한 줄에 하나의 자연수가 주어진다. 주어지는 자연수는 100 보다 작다.

출력

첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 몇 번째 수인지를 출력한다.

예제

해결

const fs = require("fs")
const input = fs.readFileSync("/dev/stdin").toString().split("\n").map(Number);
const max = Math.max(...input);

console.log(max);
console.log(input.indexOf(max)+1);

Math.max(...input)으로 정렬된 배열의 값들 중 최대값을 뽑아냅니다. input.indexOf(max)은 배열에서 첫 번째로 max가 등장하는 인덱스(0부터 시작)를 반환하고, 문제에서 줄은 1부터(input[1]) 세기 때문에 +1을 해 줍니다.

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

예제

해결

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

const n = parseInt(input);
let m = 0;

for(let i = 0; i < n;i++){
    let sum = 0;
    const candidate = i;
    const string = candidate.toString();
    for(let j = 0; j < string.length;j++){
        sum += parseInt(string[j]);
    }
    sum += candidate;
    if(sum == n){
        m = candidate;
        break;
    }
}

console.log(m);

i를 0부터 n-1까지 하나씩 늘려가며 후보 생성자로 삼습니다. 후보 생성자를 문자열로 바꾼 뒤, 각 자리 문자를 parseInt로 다시 숫자로 변환해 sum에 더합니다. 예를 들어 후보 생성자 = 256이라면 '2', '5', '6'을 순서대로 숫자로 바꿔 더해서 2+5+6 = 13이 되고, 마지막에 sum += 후보 생성자;로 “자기 자신”까지 더하면

분해합 = (각 자리의 합) + (자기 자신)

이 됩니다. 만약 이 값이 n과 같다면, i가 n의 분해합(생성자)이므로 m = candidateV;에 저장하고 더 작은 값을 찾지 않아도 되므로 break;로 반복을 종료합니다.

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

예제

해결

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin");

let range = 1;
let block = 1;

while (block < input) {
    block += 6 * range;
    range ++;
}

console.log(range);

let range = 1;
let block = 1;

range는 현재 탐색 중인 “층”(거리)을 나타냅니다. 중앙(1번 방)에 해당하는 첫 번째 층을 1로 두고 시작. block은 그 층까지 포함했을 때 커버되는 방 번호의 최대값입니다. 초기에는 중앙 한 칸만 커버하므로 1.

while (block < input) {
    block += 6 * range;
    range ++;
}

반복 조건: 아직 우리가 커버한 최댓값 block이 입력값(방 번호)보다 작으면, 더 바깥층으로 확장해야 합니다. 각 반복에서 6 * range만큼 방이 추가로 생깁니다. 1층(중앙)에서 2층으로 갈 때 6칸, 2층에서 3층으로 갈 때 12칸(=6×2), 3층에서 4층으로 18칸(=6×3)... 이만큼을 block에 더해 주면 “현재까지 커버하는 최대 방 번호”가 갱신되고, range를 하나 늘려서 “다음 층”을 가리키게 합니다.

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

• 산술평균 : N개의 수들의 합을 N으로 나눈 값
• 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
• 최빈값 : N개의 수들 중 가장 많이 나타나는 값
• 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

예제

해결

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

const N = input[0];
const numbers = input.slice(1).sort((a, b) => a - b);

const sum = numbers.reduce((acc, cur) => acc + cur, 0);
const average = Math.round(sum / N) === -0 ? 0 : Math.round(sum / N);

const median = numbers[Math.floor(N / 2)];

const freqMap = new Map();
let maxFreq = 0;

numbers.forEach(num => {
  const freq = (freqMap.get(num) || 0) + 1;
  freqMap.set(num, freq);
  if (freq > maxFreq) maxFreq = freq;
});

const freqList = [];
freqMap.forEach((value, key) => {
  if (value === maxFreq) freqList.push(key);
});
freqList.sort((a, b) => a - b);

const mode = freqList.length >= 2 ? freqList[1] : freqList[0];

const range = numbers[numbers.length - 1] - numbers[0];

console.log(average);
console.log(median);
console.log(mode);
console.log(range);

const numbers = input.slice(1).sort((a, b) => a - b);

input.slice(1)으로 실제 값들만 떼어내 정렬한 뒤 numbers에 오름차순으로 저장합니다.

//평균
const sum = numbers.reduce((acc, cur) => acc + cur, 0);
const average = Math.round(sum / N) === -0 ? 0 : Math.round(sum / N);

reduce로 모든 수의 합 sum을 구하고, sum / N을 Math.round로 반올림한 값을 average에 -0이 나올 경우(자바스크립트에서 Math.round(-0.4) 같은 결과로) 이를 0으로 바꿉니다.

//중앙값 (median)
const median = numbers[Math.floor(N / 2)];

오름차순 정렬된 numbers에서 인덱스 [N/2] 위치의 값을 중앙값으로 취합니다.

//최소값
const freqMap = new Map();
let maxFreq = 0;

numbers.forEach(num => {
  const freq = (freqMap.get(num) || 0) + 1;
  freqMap.set(num, freq);
  if (freq > maxFreq) maxFreq = freq;
});

const freqList = [];
freqMap.forEach((value, key) => {
  if (value === maxFreq) freqList.push(key);
});
freqList.sort((a, b) => a - b);

const mode = freqList.length >= 2 ? freqList[1] : freqList[0];

Map을 써서 각 숫자의 등장 횟수를 세고(freqMap), 등장 횟수 중 최댓값 maxFreq를 기록 freqMap을 순회하며, 등장 횟수가 maxFreq인 모든 키(숫자)를 freqList에 수집 이 리스트를 오름차순 정렬 여러 개의 최빈값(길이 ≥ 2)이 있으면 두 번째로 작은 값(freqList[1]), 한개면 그 값(freqList[0])을 mode에 저장

//범위
const range = numbers[numbers.length - 1] - numbers[0];

정렬된 배열의 최댓값(마지막 요소)과 최솟값(첫 요소) 차이.

최적의 값을 구해야하는 상황에서 사용되는 근시안적인 방법론 "각 단계에서 최적이라고 생각되는 것을 선택"후 나가는 방식으로 진행하며 "각 단계에서 최선의 선택을 한 것이 전체적으로 최선이길 바라는 알고리즘" 입니다.

다이나믹 프로그래밍(DP)과는 최적 부분 구조 문제를 푼다는 점에서 약간 다른데, DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면 그리디는 각 단계마다 지역 최적해를 찾는 문제로, 문제를 더 작게 줄여나가는 형태다.

1. 그리디 알고리즘의 절차

• 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
• 적절성 검사 (Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
• 해답 검사 (Solution Check) : 원래의 문제가 해결되었는지 검사 후, 해결되지 않았다면 선택 절차로 돌아가서 반복

2. 사용 조건

• 탐욕적 선택 속성 (Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조 (Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결방법으로 구성

예시

• AI에 있어서 결정 트리 학습법(Decision Tree Learning)
• 최소 신장 트리(Minimum spanning tree)
• 다익스트라 알고리즘
• 허프만 코드
• UNION&FIND 알고리즘
• 프림/크루스칼 알고리즘

문제 유형

• 활동 선택 문제(Activity selection problem)
• 거스름돈 문제
• 제약조건이 많은 대부분의 문제
• 회의실 배정
• 배낭 문제 (일부 경우)

주의 할 점

그리디 알고리즘은 항상 정답을 보장하지 않기 때문에, 문제마다 다음을 확인해야 합니다. "그리디로 풀면 항상 최적인가?" >> 증명하거나 반례가 없음을 확인해야 함 대부분은 탐색/DP보다 빠르지만 검증이 필요합니다.