• 프로그래머스 데브코스 3기 합격🎉
• 페이퍼리 사무실 정리😐 (2021-11 ~ 2022-10)

창업

호기롭게 시작했던 창업이 1년정도 되어간다. 학교 졸업을 할 때쯤 한마당 앱을 같이 만들었던 진억형님이 창업 제안을 했고, 경용형이랑 같이 셋이서 양재동 지하 어딘가에 사무실을 얻어서 창업을 했다. 페이퍼리 논문컨설팅

아직 실패했다고는 할 수 없지만 현실적인 벽이 너무 크게 느껴졌기 때문에 사무실은 정리를 하게 되었다. 거창하게 말해서 창업이지 경용형이랑 둘이서 꽤 큰? 프로젝트를 하나 끝낸 느낌이다. 기술 스택은 다음과 같다.

• React
• SCSS
• Recoil
• Node.js (Express)
• MySQL 등등..

앞으로 블로그를 하면서 여러 기록들을 할 생각인데 첫 창업을 하면서 느꼈던 것들을 한번 기록해보고자 한다.

창업 아이템

창업 아이템을 간단히 소개하자면 논문컨설팅 매칭 플랫폼이다. 스스로 논문 투고를 하지 못하는 대학원생, 혹은 직장인들은 보통 논문 업체들을 껴서 컨설팅을 받고 논문을 쓴다. 이 업체들의 문제점을 보완하고 대학원생과 컨설턴트(보통 교수님)들이 플랫폼 상에서 서로 컨택하여 컨설팅을 진행하는 아이템이다. 처음 창업 제안을 형님께 받았을 때 긍정적으로 생각이 됐던 이유 중 하나는 이 사업 타겟이 불특정 다수가 아닌 대학원생 이라는 특정 다수였기 때문이다. 타 업체들의 문제점들을 확실히 잡고 그 부분을 어필하면 충분히 먹힐 수 있겠다고 생각했다. 왜냐하면 논문 컨설팅 쪽으로는 이런 플랫폼이 없었기 때문이다. ... 하지만 지금 생각해보면 지금까지 없던 이유는 다 있지 않겠나 싶다. 가장 큰 이유는 일단 시장이 작다 이다. 내 주위에서 찾아보면 논문을 써야되는 대학원생을 본적이 없다. ㅋㅋ 내 친구들 주위에도 없다. 특정 다수가 타겟이라 괜찮겠다 생각했던 초반의 생각이 지금은 완전히 바뀌어있다. 불특정 다수가 사용하되, 누구나 쉽게 접근하고, 누구나 사용하는 그런 아이템이어야 되지 않나 싶다. (너무 당연한 소리)

커뮤니케이션

20년차 개발자이신 대표님이자 진억형님은 최신 기술에 대해 잘 모르셨다. 일단 이 부분부터 커뮤니케이션이 힘들 준비가 되있던걸지도 모른다. 리액트의 작동 방식부터 시간이 될 때마다 조금씩 알려드렸다. 대표님은 사업 자금을 위해 다니시던 직장을 계속 다니시면서 스텔스 창업을 하신 케이스다. 우리가 일 할 시간에 대표님은 다른 일을 하는 생활이 지속되다보니, 자연스레 커뮤니케이션이 원활하지 못했고, 그만큼 개발 기간도 지연되었던 것 같다. 대표님이 어느정도 기본 기능들을 말씀해주시면 우리가 예측?을 해서 개발하는 상황이 많았었고, 기능을 만들어서 보여드리면 대표님 생각과는 다른 기능이 탄생된게 몇번 있었다. 이 부분에서 커뮤니케이션의 중요성을 느낄 수 있었다. 대표님을 보면서 들었던 생각은 "스텔스 창업은 젊을때만 가능한게 아닐까..." 하는 생각이 들었었다.🙃

준비가 안된 실력

대기업 출신 개발자들이 나와서 창업을 해도 될까 말까인데 고작 학교 2년 배우고 시작한 창업... 게다가 백엔드 지식만 가르치다보니 프론트는 거의 독학으로 했다. 그렇게 맨땅에 헤딩하듯 시작했고, 결과물은.... 살짝 부끄럽다. (사이트가 별게 없어서 성능은 나쁘지 않은듯..?)

정말 패기 하나로 도전했고, 되도 경험이고, 안되도 경험이다. 라는 생각으로 시작했다. 이 창업을 하면서 리액트를 익혔고, 시간이 지나 지금 돌이켜 보면 잘 안됐지만 그래도 값진 경험이라고 생각한다.

이렇게 1년간의 짧다면 짧고, 길다면 긴 여정이 끝나갈 무렵 고민에 빠지게 됐다.

"나 이대로면 다른 곳 취업 못하겠다."

내 실력을 객관적으로 평가해봤을때 자바스크립트, 리액트, CSS 등 수박 겉핥기만 했구나 라는 생각이 강하게 들었다. 지금껏 난 프로그래머가 아닌 페이지를 찍어내는 코더 역할을 더 많이 했다고 생각한다. 내가 되고 싶은건 프론트엔드 개발자였기 때문에 개발 역량을 더 키워야겠다고 생각했고, 레벨업하기 위해 프로그래머스 데브코스에 지원하게 되었다.

프로그래머스 데브코스 3기 합격🎉

사실 이 글을 쓰는 지금은 데브코스 시작한지 3주가 지난 시점이다.

아직도 혹시 몰래카메라 또는 전산오류가 아닐까 생각한다.

저 메일을 받고 기쁨 보다는 당황스러움이 더 컸다. ("내가..? 왜 내가..?")

1차 서류전형은 며칠을 고민하여 꽤 만족스러운 서류접수를 했고, 2차 코딩테스트에선 1번 1문제 풀고 2번째 문제는 반 정도 풀었다. (사실 그 1문제도 틀렸을지도..) 3차 면접은 4대1 면접을 봤는데 내가 개발자 꿈을 갖고 본 첫 면접이라 정말 너무 떨렸고, 횡설수설해서 식은땀이 엄청 났던 것만 기억한다.

면접이 끝나고 정말 "아 여기까지겠구나"라고 생각했다. (진심)

하지만 정말 너무 너무 감사하게도 합격메일을 받았고 지금은 하던 알바들도 다 때려치우고 데브코스에만 전념하고 있다.

데브코스 시작한지 한 달 정도 되고 느낀점은 실력을 키우기 정말 좋은 환경이라는 것이다.

• 팀 별 멘토님 배정 (일주일에 한번 커피챗)
• 수준 높은 동영상 강의
• 거의 주마다 한번 있는 특강 & 세션 (진유림님, 김태휘님, 이선협님, 마광휘님 등등)
• 현업처럼 진행되는 과제, 멘토님의 코드리뷰
• 의욕넘치는 동기들과 스터디 등등

아직 3주밖에 되지 않았지만 아무리 생각해도 정말 실력 키우기 너무 좋은 환경인 것 같다. (감사합니다😭)

블로그의 중요성도 데브코스를 진행하며 실감하게 되어서 이제라도 시작해보기 위해 이 글을 썼다. 첫 회고 글이라 짧게 작성하려 했는데 쓰다보니 은근 재미있어서 길어진 것 같다. 글을 많이 써보지 않아서 어색하고 부족하지만 이것도 꾸준히 하다보면 나중엔 괜찮은 글도 쓸 수 있을 거라 생각한다.

TMI

프로그래머스 브랜드 키트 보고가세요~

귀여운 머쓱이

• 해결한 작은 문제로 큰 문제를 해결하는 방식

• Dynamic Programming(DP)라고도 부른다.

• 메모리를 사용하는 대신 빠른 성능을 자랑한다.

• 두 가지 방법론

  • 메모이제이션
  • 타뷸레이션

메모이제이션

• 하향식 접근법
• 동적 계획법에서 작은 문제들의 결과는 항상 같다.
• 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다.

타뷸레이션

• 상향식 접근법
• 필요한 값들을 미리 계산 (메모이제이션은 필요할때 계산, 타뷸레이션은 미리 계산)

동적계획법 문제 접근방법

키워드만으로 동적 계획법 문제임을 알기가 어렵다. 문제 유형을 알 수 없다면 아래 두가지를 확인해보자.

• 가장 작은 문제를 정의할 수 있는가?
• 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙성이 있는가?

위 두가지가 가능하다면 동적계획법 문제일 확률이 크다.

동적계획법 문제

백준 계단오르기

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스

• 모든 경우의 수를 탐색하는 알고리즘
• DFS나 BFS이용
• 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기라고 한다.
• 자바스크립트는 재귀 효율이 안좋다. 때문에 DFS일 경우 Stack을 이용하는 것이 좋다.
• 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 좋다.

가지치기 🎄

백트래킹의 핵심이라고 할 수 있고 얼마나 잘 하느냐에 따라 효율성을 결정한다.

가지치기 방법

1. 모든 경우의 수를 찾을 수 있도록 코딩
2. 특정한 조건을 만족하는 것만 탐색하고, 나머지는 탐색하지 않도록 조건문 작성
3. 절대로 답이 될 수 없는 것은 탐색을 종료한다.

코드구현 (N-Queen)

문제링크

전략

가지치기를 할 수 있는 경우는 다음과 같다.

1. 퀸을 둔 행은 가지치기 한다.
2. 퀸을 둔 열은 가지치기 한다.
3. 퀸을 둔 대각선 왼쪽, 오른쪽은 가지치기 한다.

가지치기 조건을 찾은 것은 좋지만 가지치기를 위해 행과 열, 대각선을 루프를 통해 검사하게 되면 성능을 크게 낭비하게 된다. 그래서 최대한 적은 비용으로 가지치기를 하기 위해 1차원 배열을 사용한다.

• 배열의 index는 행의 위치, 해당 index의 value는 열의 위치 ex)queen[2] = 1은 체스판 위에서 두 번째 줄, 첫 번째 칸에 해당한다.

• 한 index에 여러 value를 둘 수 없기에 행은 자연스럽게 가지치기 된다.

• index가 같다면 둘 수 없다. 같다면 가지치기 한다.

• 행, 열에 대한 차가 같다면 대각선에 있다는 뜻이므로 가지치기 한다. ex)1부터 시작한다고 가정할 때 queen[3] = 2, queen[1] = 4일 때 행에 대한 차 3 - 1과 열에 대한 차 4 - 2는 같기 때문에 대각선에 있다는 뜻이다. (절대값으로 계산하면 왼쪽, 오른쪽 둘다 체크 가능하다)

이런 방식으로 검사 비용을 아낄 수 있다.

function check(queen, row) {
  // 이전까지 두었던 퀸의 위치를 확인한다.
  for (let i = 0; i < row; i += 1) {
      // 행의 위치와 대각선의 위치를 체크한다.
      if (queen[i] === queen[row] || Math.abs(queen[i] - queen[row]) === row - i) {
          return false; // 둘 수 없다면 false
      }
  }

  return true; // 모두 통과되면 true
}

function search(queen, row) {
  const n = queen.length;
  let count = 0;

  if (n === row) { // 체스판 끝에 도달했다면.. 재귀의 탈출 조건
      return 1;
  }

  for (let col = 0; col < n; col += 1) { // 0부터 n까지 열을 돌면 둘 수 있게 만든다.
      queen[row] = col; // 우선 퀸을 둔다
      if (check(queen, row)) { // 퀸을 둘 수 있다면..
          count += search(queen, row + 1); // 다음 행으로 이동!
      }
  }

  return count;
}

function solution(n) {
  // 미리 n개 만큼의 배열을 초기화한다. 0번 행부터 시작한다.
  return search(Array.from({ length: n }, () => 0), 0);
}

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스

그래프 탐색 알고리즘으로 같은 깊이에 해당하는 노드부터 탐색하는 알고리즘

BFS 특징

• Queue를 이용하여 구현
• 루트 노드부터 가까운 노드부터 탐색
• V가 정점의 수, E가 간선의 수 일때 BFS의 시간복잡도는 O(V+E)

DFS (깊이 우선 탐색)

그래프 탐색 알고리즘으로 최대한 깊은 노드부터 탐색하는 알고리즘

DFS 특징

• Stack을 이용하여 구현
• 루트 노드에서 깊은 노드부터 탐색
• V가 정점의 수, E가 간선의 수 일때 DFS의 시간복잡도는 O(V+E)

DFS 이진트리 순회

전위순회

작업순서 : 부모 노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드

중위순회

작업순서 : 왼쪽 자식노드 -> 부모 노드 -> 오른쪽 자식노드

후위순회

작업순서 : 오른쪽 자식노드 -> 부모 노드 -> 왼쪽 자식노

코드구현

function solution(n) {
  const preOrderArr = [];
  const inOrderArr = [];
  const postOrderArr = [];

  function preOrder(v) {
    if (v > 7) {
      return;
    } else {
      preOrderArr.push(v);
      preOrder(v * 2);
      preOrder(v * 2 + 1);
    }
  }

  function inOrder(v) {
    if (v > 7) {
      return;
    } else {
      inOrder(v * 2);
      inOrderArr.push(v);
      inOrder(v * 2 + 1);
    }
  }

  function postOrder(v) {
    if (v > 7) {
      return;
    } else {
      postOrder(v * 2);
      postOrder(v * 2 + 1);
      postOrderArr.push(v);
    }
  }

  preOrder(n);
  inOrder(n);
  postOrder(n);

  console.log(preOrderArr);    // 1 2 4 5 3 6 7
  console.log(inOrderArr);    // 4 2 5 1 6 3 7
  console.log(postOrderArr);// 4 5 2 6 7 3 1
}

console.log(solution(1));

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입력

k = 80 dungeons = [[80,20],[50,40],[30,10]]

출력

3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

📌 나의 풀이 (실패)

1. 최소 피로도 - 소모피로도 기준으로 내림차순 정렬
2. k가 최소피로도보다 크거나 같은지 확인
3. 크거나 같다면 k-=소모피로도, answer++

   function solution(k, dungeons) {
    var answer = 0;
    dungeons.sort((a,b) => {
        return (b[0]-b[1]) - (a[0]-a[1]);
    })
    dungeons.forEach((item, index) => {
        if(k - item[0] >= 0) {
            answer++;
            k -= item[1];
        }
    })
    return answer;
   }
   // 반례
   // k = 40
   // [[40, 20], [10, 10], [10, 10], [10, 10], [10, 10]]
   // answer = 4

📌 다른 사람 풀이 (DFS)

1. DFS를 활용하여 모든 경우의 조합을 answer에 추가
2. answer의 최대값을 반환

   function solution(k, dungeons) {
    let answer = [];
    let visited = Array(dungeons.length).fill(false);
    const dfs = (count, k) => {
        answer.push(count);
        for(let i = 0; i < dungeons.length; i++) {
            let curr = dungeons[i];
            if(k >= curr[0] && !visited[i]) {
                visited[i] = true;
                dfs(count + 1, k - curr[1]);
                visited[i] = false;
            }
        }
    }
    dfs(0, k);
    return Math.max(...answer)
   }

DFS, BFS 공부하러감.. 😇😇😇

정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘 O(log N)만큼 시간복잡도가 걸린다. ex) Up & Down 게임

이진 탐색 특징

• 반드시 정렬이 되어있어야 사용할 수 있다.
• 배열 혹은 이진 트리를 이용하여 구현가능하다.
• 시간복잡도가 O(log N)인 만큼 상당 빠르다.

배열 이진 탐색

• 배열 중간 값을 추가하거나 삭제할 때 선형시간이 걸리는 단점이 있다.
• 그래서 더 효율적인 이진 탐색 트리를 사용한다.

이진 탐색 트리

• 이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고, 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

이진 탐색 트리 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다. ex) 5,4,3,2,1 순으로 추가할 때

이진 탐색 구현 (배열)

const array = [null, 1, 2, 5, 125, 400, 777, 1004, 4563, 7777];

function arrayBinarySearch(array, findValue) {
    let left = 0;
    let right = array.length - 1;
    let mid = Math.floor((left + right) / 2);
    while (left < right) {
        if (array[mid] === findValue) {
            return mid;
        }

        if (array[mid] < findValue) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }

        mid = Math.floor((left + right) / 2);
    }

    return -1;
}

console.log(arrayBinarySearch(array, 1));

이진 탐색 구현 (트리)

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearch {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return;
        }

        let currentNode = this.root;
        while (currentNode !== null) {
            if (currentNode.value < value) {
                if (currentNode.right === null) {
                    currentNode.right = newNode;
                    break;
                }
                currentNode = currentNode.right;
            } else {
                if (currentNode.left === null) {
                    currentNode.left = newNode;
                    break;
                }
                currentNode = currentNode.left;
            }
        }
    }

    has(value) {
        let currentNode = this.root;
        while (currentNode !== null) {
            if (currentNode.value === value) {
                return true;
            }

            if (currentNode.value < value) {
                currentNode = currentNode.right;
            } else {
                currentNode = currentNode.left;
            }
        }

        return false;
    }
}

const tree = new BinarySearch();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);

console.log(tree.has(3)); // true
console.log(tree.has(2)); // false

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스

• 트리를 이용한 자료구조
• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 ex) 검색에서 사용하는 자동완성 기능을 만들 때 사용하는 알고리즘

트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 사용한다.
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
• 각 정점이 자식에 대한 링크를 전부 갖고 있기 때문에 저장 공간을 더 많이 사용한다.

트라이 구조

• 루트는 비어있다.
• 각 간선(링크)는 추가될 문자를 키로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
    }
}

class Trie {
    constructor() {
        this.root = new Node();
    }

    insert(string) {
        let currentNode = this.root;

        for (const char of string) {
            if (!currentNode.children.has(char)) {
                currentNode.children.set(char, new Node(currentNode.value + char));
            }
            currentNode = currentNode.children.get(char);
        }
    }

    has(string) {
        let currentNode = this.root;

        for (const char of string) {
            if (!currentNode.children.has(char)) {
                return false;
            }
            currentNode = currentNode.children.get(char);
        }

        return true;
    }
}

const trie = new Trie();
trie.insert("cat");
trie.insert("can");
console.log(trie.has("cat")); // true
console.log(trie.has("caq")); // false
console.log(trie.has("can")); // true
console.log(trie.has("cab")); // false

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스

우선순위 큐는 일반적인 FIFO인 큐와 달리 우선순위가 높은 요소가 먼저 나가는 개념이다. 힙은 우선순위 큐를 구현하기 위한 가장 적합한 방법이다.

우선순위 큐 !== 힙

힙의 특징

• 우선순위가 높은 요소가 먼저 나간다.
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)와 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.

힙 요소 추가 알고리즘

1. 추가된 요소를 트리의 가장 마지막 정점에 위치시킨다.
2. 요소의 부모 정점과 비교하여 우선순위가 높다면 부모 정점과 순서를 바꾼다.
3. 1,2번을 반복하면 가장 우선순위가 높은 정점이 루트가 된다.
4. 시간복잡도는 O(Log N)이다.

힙 요소 제거 알고리즘

1. 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다. (요소 제거는 루트만 가능)
2. 루트 정점의 두 자식 정점 중 우선순위가 높은 정점과 바꾼다.
3. 두 자식의 정점이 우선순위가 더 낮을 때까지 반복
4. 시간복잡도는 O(Log N)이다.

힙 구현 방법

요소 추가

class MaxHeap {
    constructor() {
        this.heap = [null];
    }

    insert(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor(currentIndex / 2);

        while (parentIndex !== 0 && this.heap[parentIndex] < value) {
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = value;
            this.heap[currentIndex] = temp;
            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }
}

const heap = new MaxHeap();
heap.insert(45);
heap.insert(36);
heap.insert(54);
heap.insert(27);
heap.insert(64);
console.log(heap.heap); // [null, 64, 54, 45, 27, 36]

요소 제거

class MaxHeap {
    constructor() {
        this.heap = [null];
    }

    remove() {
        const returnValue = this.heap[1];
        this.heap[1] = this.heap.pop();

        let currentIndex = 1;
        let leftIndex = 2;
        let rightIndex = 3;

        while (
            this.heap[currentIndex] < this.heap[leftIndex] ||
            this.heap[currentIndex] < this.heap[rightIndex]
        ) {
            if (this.heap[leftIndex] < this.heap[rightIndex]) {
                const temp = this.heap[currentIndex];
                this.heap[currentIndex] = this.heap[rightIndex];
                this.heap[rightIndex] = temp;
                currentIndex = rightIndex;
            } else {
                const temp = this.heap[currentIndex];
                this.heap[currentIndex] = this.heap[leftIndex];
                this.heap[leftIndex] = temp;
                currentIndex = leftIndex;
            }
            leftIndex = currentIndex * 2;
            rightIndex = currentIndex * 2 + 1;
        }

        return returnValue;
    }
}

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조 [사진출처] https://6mini.github.io/computer%20science/2022/02/03/tree/

트리의 특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
• 트리내에 또 다른 트리가 있는 재귀적 자료구조이다.

이진 트리 (Binary Tree)

이진 트리는 최대 2개의 자식노드를 가진다. (자식노드가 없거나 1개여도 가능)

이진 트리의 특징

• 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다. (N개의 노드를 가진 편향트리)
• 정점이 N개인 포화 또는 완전 이진트리의 높이는 log N이다.
  • 레벨이 증가됨에 따라 2개씩 정점이 생기기 때문
• 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등에 사용된다.

이진 트리의 종류

1. 편향 이진 트리

편향 이진 트리는 하나의 차수로만 이루어진 경우를 말한다. 배열(리스트)와 같은 선형 구조이므로 가장 아래쪽에 위치한 노드를 탐색 시 모든 데이터를 탐색해야한다는 단점이 있어서 효율적이지 못하다.

2. 완전 이진 트리

모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 의미한다.

3. 포화 이진 트리

포화 이진 트리는 Leaf Node를 제외한 모든 노드의 차수가 2개로 이루어져 있는 경우다. 해당 차수에 몇개의 노드가 존재하는지 바로 알 수 있으므로 노드의 개수를 파악할 때 용이하다.

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스 kdb님 velog

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입력

n = 6 vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

출력

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

데브코스에서 그래프 강의를 듣고 실습문제를 풀어보려고 한다. 평소에 알고리즘 문제에 약해서 DFS, BFS는 시도조차 못하고 있었다. 이 문제도 마찬가지였다. 입력값 vertex가 "이미 그래프가 만들어져 있는거 아닌가..?" 싶어서

const edgeMap = new Map();
vertex.forEach(([node, edge], index) => edgeMap.set(node, {
  node:edge
}))
...

이런식으로 풀어보려다가 아무리 생각해도 이건 아닌것 같아 문제풀이 강의를 들으면서 천천히 이해했다.

풀이

먼저 그래프를 만들어줘야한다. 이 문제에서 핵심 키워드는 간선은 양방향이다.

const graph = Array.from(Array(n + 1), () => [])

for(const [from,to] of edge) {
  graph[from].push(to);
  graph[to].push(from);
}

1번 노드에서 가장 멀리 있는 노드의 거리를 구해야한다. 각 정점의 거리를 기록할 수 있도록

const distance = Array(n+1).fill(0);
distance[1] = 1;    // 1번노드를 거리 1로

그리고 이제 BFS (너비 우선 탐색)를 구현해야한다. (BFS, DFS는 다른 포스트에 따로 개념 정리를 해야겠다)

BFS는 큐나 연결리스트로 구현 가능하다.

const queue = [1];    // 1번 노드를 기준으로
while(queue.length > 0) {
  const from = queue.shift();

  for(const node of graph[from]) {
    if(distance[node] === 0) {    // 한번도 가지 않은 노드라면
      queue.push(node);
      distance[node] = distance[from] + 1;
    }
  }
}
console.log(distance);
//    
// [
//  0, 1, 2, 2,
//  3, 3, 3
// ]

마지막으로 가장 멀리(3) 있는 노드들 갯수를 카운트해서 출력하면 된다.

const max = Math.max(...distance);
return distance.filter(item === max).length;

전체코드

function solution(n, edge) {
    const graph = Array.from(Array(n + 1), () => [])

    for(const [from, to] of edge) {
        graph[from].push(to);
        graph[to].push(from);
    }

    const distance = Array(n+1).fill(0);
    distance[1] = 1;

    // BFS
    const queue = [1];
    while(queue.length > 0) {
        const from = queue.shift();

        for(const node of graph[src]) {
            if(distance[node] === 0) {
                queue.push(node);
                distance[node] = distance[from] + 1
            }
        }
    }

    const max = Math.max(...distance);
    return distance.filter(item => item === max).length;
}

어렵지만 다른 문제도 풀어봐야겠다😇

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 정점 집합과 간선 집합으로 표현할 수 있다. [사진출처] https://velog.io/@gimtommang11/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EA%B7%B8%EB%9E%98%ED%94%84

용어

• 정점(Node/Vertice) : 그래프를 형성하는 노드
• 간선(Edge/arcs) : 정점 간에 선 (노드 간의 연결)
• 정점 차수 : 해당 정점에 연결된 간선의 개수
• 가중치 : 간선에 대한 값. 문맥에 따라 다양한 것을 나타낼 수 있음

그래프의 특징

• 정점은 여러개의 간선을 가질 수 있다.
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다.

그래프의 종류

무방향 그래프

간선으로 이어진 정점끼리는 양방향으로 이동이 가능 (1,2)와 (2,1)은 같은 간선으로 취급 ex) 양방향 통행 도로

방향 그래프

간선에 방향성이 존재 만약 양방향으로 갈 수 있다고 해도 (1,2)와 (2,1)은 다른 간선으로 취급 ex) 일방통행 도로

그래프의 종류(2)

비연결 그래프

노드들 중, 간선에 의해 연결되어있지 않은 노드가 있는 그래프

연결 그래프

모든 정점이 서로 이동 가능한 상태인 그래프 (무방향 그래프와 그림이 같음)

완전 그래프

모든 정점끼리 연결된 상태인 그래프 한 정점의 간선 수 = (모든 정점 수 - 1) 모든 간선의 수 = (모든 정점 수 - 1) * 정점 수

사이클

그래프의 정점과 간선의 부분집합에서 순환이 되는 부분

그래프의 구현 방법

인접 행렬

2차원 배열로 표현

const graph = Array.from(
  Array(5), () => Array(5).fill(false)
);
graph[0].push(1);    // 0 -> 1
graph[0].push(3);    // 0 -> 3
graph[1].push(2);    // 1 -> 2
graph[2].push(0);    // 2 -> 0
graph[3].push(2);    // 3 -> 2
graph[4].push(0);    // 4 -> 0

인접 리스트

연결 리스트로 표현

const graph = Array.from(
  Array(5), () => []
);
graph[0].push(1);    // 0 -> 1
graph[0].push(3);    // 0 -> 3
graph[1].push(2);    // 1 -> 2
graph[2].push(0);    // 2 -> 0
graph[3].push(2);    // 3 -> 2
graph[4].push(0);    // 4 -> 0

그래프 관련 문제 가장 먼 노드

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스 sue님 velog

First In First Out (먼저 삽입된 item이 먼저 삭제된다) 라는 개념을 가진 선형 구조이다.

[사진출처] https://galid1.tistory.com/483

큐에는 선형 큐와 원형 큐가 있다.

선형 큐 (Linear Queue)

1. 배열로 표현하기

• Enqueue로 데이터를 추가하다가 Dequeue를 할 때 앞에 빈공간이 생긴다.
• Front나 Rear의 값이 무한정 커질 수 있다.
• 공간을 더 쓰기 위해 배열을 앞당기는 작업이 필요하다.

2. 연결리스트로 표현하기

• 배열에서의 문제를 어느정도 해결한다.
• 연결리스트의 head는 Front가 되고 tail은 Rear가 된다.

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

  size() {
    return this.rear - this.front;
  }

😨 Shift 함수는 쓰지 말 것 shift함수는 선형시간이 걸리기 때문에 큐에서 기대하는 로직이 수행되지 않는다! (shift 자주썼는데...)

const queue = [1,2,3];
queue.push(4);
const value = queue.shift(); // O(n)
console.log(value); // 1

원형 큐 or 환형 큐 (Circular Queue)

한정된 공간을 효율적으로 이용할 때 사용한다.

class Queue {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.queue = [];
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  enqueue(value) {
    if(this.isFull()) {
      console.log("Queue is full.");
      return;
    }
    this.queue[this.rear] = value;
    this.rear = (this.rear + 1) % this.maxSize;
    this.size += 1;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front = (this.front + 1) % this.maxSize;
    this.size -= 1;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

  isFull() {
    return this.size === this.maxSize;
  }

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스

• 입력 크기
• 하드웨어, 운영체제 성능
• 컴파일러 최적화

이러한 고려해야 할 점이 많기 때문이다. 그래서 대략적인 성능을 비교하기 위한 상대적인 표기법을 사용한다.

빅오표기법 (Big-O notation)

실행 속도 O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(n!)

각각 어떻게 다른지 알아보자.

O(1)

일정한 복잡도라고 하며, 입력값(N)이 증가해도 실행시간은 동일하다. ex) stack의 push, pop

function O_1_algorithm(arr, index) {
  return arr[index];
}
let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

O(log N)

연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (log의 지수는 항상 2) ex) binary search 알고리즘, tree 형태 자료구조 탐색

for(let i = 1; i <= n; i *= 2) {
  ...
}

O(N)

입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘 ex) 1중 for문

for(let i = 0; i < n; i += 1) {
  ...
}

O(N log N)

O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 상태 ex) 퀵, 병합, 힙 정렬

for(let i = 0; i < n; i += 1) {
  for(let j = 1; j <= n; j *= 2) {
    ...
  }
}

O(N^2)

O(N)의 알고리즘이 두 번 중첩된 상태 ex) 2중 for문, 삽입/버블/선택 정렬

for(let i = 0; i < n; i += 1) {
  for(let j = 0; j < n; j += 1) {
    ...
  }
}

O(2^N)

빅오 표기법 중 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘이 이에 해당 ex) 피보나치 수열

function fibonacci(n) {
  if (n <= 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스 nana-moon님 velog hanamon님 블로그

자바스크립트 특징

• 자바스크립트는 싱글 스레드 기반의 언어이고 한번에 하나의 처리만 할 수 있다. (CallStack이 한개)
• 자바스크립트가 비동기로 동작할 수 있는 이유는 브라우저(혹은 node.js)의 이벤트 루프 때문이다.

이벤트 루프 기본 구조

자바스크립트 엔진

Heap 객체가 저장되는 메모리 공간

Call Stack 함수를 호출하면 함수 실행 컨텍스트가 순차적으로 Call Stack에 푸쉬되어 순차적으로 실행된다. 실행 중인 컨텍스트가 종료되어 Call Stack에서 제거되기 전까지 다른 태스크는 실행하지 않는다.

브라우저 환경

Tesk Queue setTimeout이나 setInterval같은 비동기 함수의 콜백 함수, 이벤트 핸들러가 일시적으로 저장되는 공간

Web APIs 브라우저에서 제공하는 api 클릭같은 DOM Event, AJAX 네트워크 호출, Timer 등 은 실행시킬 경우 콜백 함수를 넘기게 되는데, 이 콜백 함수는 비동기 작업이 끝나면 Tesk Queue에 넣어지고 순차적으로 Call Stack에 푸쉬된다.

Event Loop 이벤트 루프는 Call Stack에 현재 실행 중인 실행 컨텍스트가 있는지, 태스크 큐에 대기 중인 함수가 있는지 반복해서 확인한다. Call Stack의 실행이 끝나고 비워져 있을 때만 태스크 큐의 함수를 순차적으로 푸쉬해주는 역할

예시

console.log('Hi');
setTimeout(function cb(){
  console.log('Dami');
},0);
console.log('Daisy');

// Hi
// Daisy
// Dami

위와 같은 코드가 있을 때 setTimeout의 콜백함수가 태스크 큐에 저장되고 "Hi"와 "Daisy"를 출력한다. 그 후 비워져 있는 Call Stack에 setTimeout의 콜백함수를 푸쉬를 해주면서 마지막으로 "Dami"를 출력한다.

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스 seokkitdo님 velog MDN EventLoop

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.
그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.

1, 1, 2, 3, 5, 8, ...

지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다. 타일의 개수 N(1 ≤ N ≤ 80)이 주어졌을 때, N개의 타일로 구성된 직사각형의 둘레를 구하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 입력은 한 줄로 구성되며 이 줄에는 타일의 개수를 나타내는 정수 N(1 ≤ N ≤ 80)이 주어진다.

출력

표준 출력으로 N 개의 타일이 구성하는 타일 장식물 직사각형의 둘레를 출력한다.

64비트 정수형인 “long long” 자료형을 써야할 수 있음

예제 입력1

5

예제 출력1

26

예제 입력2

6

예제 출력2

42

코드

*✔ 피보나치수열을 이용해서 둘레를 구해주면 된다. 둘레를 구할 때 표를 그려서 이해하면 쉽다.
// 타일 개수 1 2 3 4 5 6 7 // 둘레 4 6 10 16 26 42 68 따라서, f(n) = f(n-1) + f(n-2)의 규칙으로 증가함을 알 수 있다. 1과 2일때는 f(n-2)가 성립되지 않기때문에 배열에 [0,4,6]을 넣어준 뒤 구해지는 값들을 push해준다. 60~70번째까지 가면 숫자 초과 현상이 일어나는데 BigInt를 쓰면 뒤에 n이 붙어서 자꾸 틀렸다고 나온다... 일단 알고리즘은 맞는것 같으니 올리도록 하겠다... (이거 아시는 분 헬프미ㅠ) *

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const range = (start, end) => {
  let array = [];
  for (let i = start; i < end; ++i) {
    array.push(i);
  }
  return array;
};

let answer = [0, 4, 6];
const resultTile = (input) => {
  if (input === 1) return 4;
  if (input === 2) return 6;
  else {
    for (let i of range(3, 81)) {
      answer.push(answer[i - 1] + answer[i - 2]);
    }
    return answer[input];
  }
};

let input = 0;
rl.on("line", (userInput) => {
  input = userInput;
}).on("close", () => {
  console.log(resultTile(input));
  process.exit();
});

캥거루 세 마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다. 한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다. 캥거루는 최대 몇 번 움직일 수 있을까?

입력

여러개의 테스트 케이스로 이루어져 있으며, 세 캥거루의 초기 위치 A, B, C가 주어진다. (0 < A < B < C < 100)

출력

각 테스트에 대해 캥거루가 최대 몇 번 움직일 수 있는지 출력한다.

예제 입력1

2 3 5 3 5 9

예제 출력1

1 3

코드

** ✔ 캥거루는 3마리로 고정되어 있고 0<A<B<C 이다. 양쪽에 있는 A와 C의 자리에 있는 캥거루 중에 더 많이 움직이는 횟수 구해야하기 때문에 B-A와 C-B를 한 값중 더 큰값을 구해주면 된다.**

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const Result = (one, two, three) => {
  let twoOne = two - one - 1;
  let threeTwo = three - two - 1;

  twoOne > threeTwo ? console.log(twoOne) : console.log(threeTwo);
};

let array = [];
rl.on("line", (userInput) => {
  array = userInput.split(" ");
  const one = parseInt(array[0]);
  const two = parseInt(array[1]);
  const three = parseInt(array[2]);

  Result(one, two, three);
}).on("close", () => {
  process.exit();
});

JavaScript로 코딩테스트 준비를 하는사람은 C++이나 Python보다 비교적으로 적기 때문에 인터넷 서핑을 많이 해야한다.

fs 모듈

fs 모듈 사용은 알고 리즘 마다 경로가 달라져서 보편적으로 사용할 수 없다.
출처 https://gimgongta.tistory.com/20
fs 모듈 사용 예시

//한줄짜리 입력일 경우 (예 "사과")

// 문자로 입력받은것 정수나 숫자로 입력받기 preseInt(),Number()

var fs = require("fs");

var input = fs.readFileSync("/dev/stdin").toString();

var result = input; // 이 변수에 "사과" 가 들어간다.

// 한줄에 스페이스로 여러 파라미터가 들어가는 경우( 예를들어 "사과 토마토 수박" );

var fs = require("fs");

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

var result1 = input[0]; //입력받은값이 정수이면 parseIn, 소수이면parseFloat(input[0]);

var result2 = input[1];

var result3 = input[2];

// 여러줄로(개행되어) 여러 파라미터가 들어가는경우
// 예를들어
// 사과
// 토마토
// 수박

var fs = require("fs");

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

var result1 = input[0];

var result2 = input[1];

var result3 = input[2];

readline 모듈

위의 fs모듈을 사용하면 자꾸 경로 에러가 나서 가장 많이 사용하는 방법인 readline 모듈이다.
출처 https://velog.io/@exploit017
readline 모듈 사용 예시

//하나 입력
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", function (line) {
  console.log(line);

  //기본적으로 매개변수 line에 할당된다.

  rl.close();
}).on("close", function () {
  process.exit();
});

//한 줄에 스페이스로 구분하기
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input = line.split(" ").map((el) => parseInt(el));
}).on("close", function () {
  //매개변수 input에 할당된다.
  console.log(input[0] + input[1]);

  process.exit();
});

//여러줄 입력//
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  //내용이고 줄바꿈하면 인덱스바뀜 ex) input[0] enter -> input[1]
  process.exit();
});

프로젝트나 다른 이것저것 하다가 다시 문제를 풀려고 하면 자꾸 모듈 사용하는게 기억이 잘 안나서 아예 정리를 해버렸다.
프로그래머스로 넘어가야되나...🤔

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력1

4 2 1 1 1 1

예제 출력1

3

예제 입력2

10 5 1 2 3 4 2 5 3 1 1 2

예제 출력2

3

코드

** ✔ 구간의 부분합을 이용하는 문제 투 포인터는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘이다. 조건은 배열의 원소가 자연수여야 한다는 것이다. start, end라는 두 개의 포인터를 사용해서 구해야하는 값보다 배열의 부분합이 작으면 mid를 한간 이동하여 배열의 크기를 늘리고 반대로 부분합이 크면 mid를 한간 뒤로 이동하여 배열의 크기를 줄인다.**

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
const numberSum = (limitArr, numArr) => {
  const sumArr = [10001];
  let sum = 0;
  let count = 0;
  let mid = 0;

  const numberArr = Number(limitArr[0]);
  const cutlineNum = Number(limitArr[1]);

  for (let i = 0; i < numberArr; i++) {
    sum += Number(numArr[i]);
    sumArr[i] = sum;
  }
  // unshift를 통해 [0,1,2,3,4...] 배열로 만든다
  sumArr.unshift(0);

  for (let i = 0; i <= numberArr; i++) {
    // start에 포인터 한개, end에 포인터 한개 만든다.
    start = i;
    end = numberArr;

    // 중간지점 mid보다 cutlineNum이 작다면 start를 한칸 앞으로,
    // cutlineNum이 크다면 end를 한칸 뒤로
    while (start <= end) {
      mid = parseInt((start + end) / 2);
      if (cutlineNum > sumArr[mid] - sumArr[i]) {
        start = mid + 1;
      } else if (cutlineNum < sumArr[mid] - sumArr[i]) {
        end = mid - 1;
      } else {
        count++;
        break;
      }
    }
  }
  console.log(count);
};

const inputArr = [];
rl.on("line", (userInput) => {
  inputArr.push(userInput);
}).on("close", () => {
  const limitArr = inputArr[0].split(" ");
  const numArr = inputArr[1].split(" ");
  numberSum(limitArr, numArr);
});

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

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

입력

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

출력

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

예제 입력1

2

예제 출력1

1

예제 입력2

10

예제 출력2

3

코드

** ✔ 이전에 구했던 값들을 배열에 계속 저장함으로써 구했던 값들에 +1을 하는 방식으로 구한다.**

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", function (line) {
  const num = Number(line); // 배열 크기를 만들기 위해 입력 받은 값 숫자로 형변환
  const arr = new Array(num + 1).fill(0); // 입력받은 크기만큼 배열 공간 만들고 0으로 초기화

  for (let i = 2; i <= num; i++) {
    arr[i] = arr[i - 1] + 1; // arr[2]에 1대입

    if (i % 2 === 0) {
      // i가 2로 나누어 떨어지면
      arr[i] = Math.min(arr[i], arr[i / 2] + 1); // 위에서 대입한  1(arr[i])과 0(arr[2/2]+1)을 비교해서 작은 값을 arr[2]에 대입
    }

    if (i % 3 === 0) {
      // i가 3으로 나누어 떨어지면
      arr[i] = Math.min(arr[i], arr[i / 3] + 1); // 위의 코드와 마찬가지 (3으로 나누어졌던 과거 숫자들을 찾아야되므로 i/3)
    }
  }
  console.log(arr[num]);
}).on("close", function () {
  process.exit();
});

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다.

• 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
• 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
• 마지막 도착 계단은 반드시 밟아야 한다.
  따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
  각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력1

6 10 20 15 25 10 20

예제 출력1

75

코드

** ✔ 계단을 오르면서 밟아 올라왔던 계단들의 수들을 합하며 올라오는 것이 핵심이다. dp[0]은 첫번째 계단이므로 올라온 계단이 없기 때문에 arr[0]은 dp[0]이다. dp[1]은 두번째 계단이고 첫번째 계단과 두번째 계단을 합친 수와 두번째 계단을 비교해서 큰 수를 대입한다. dp[2]은 세번째 계단이고 첫번째, 세번째 이렇게 밟는 방법과 두번째, 세번째 밟는 방법 두 가지를 비교해서 큰 수를 대입한다. 이렇게 전에 올라왔던 계단들을 비교하고 더하면서 마지막 계단인 dp[stairs-1]를 구할 수 있다.**

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let arr = []; // 입력받는 공간

rl.on("line", (line) => arr.push(line)).on("close", () => {
  const stairs = parseInt(arr.shift()); // arr에 입력한 첫번째 인덱스값 stairs 에 저장 (stairs = 계단의 총 길이)
  arr = arr.map(Number); // arr에 있는 요소들 숫자로 형변환

  dp = Array(301);
  dp[0] = arr[0]; // 첫번째 계단은 고정
  dp[1] = Math.max(arr[0] + arr[1], arr[1]); // (첫번째 + 두번째)계단과 두번째 계단을 비교해서 큰 값을 dp배열에 삽입
  dp[2] = Math.max(arr[1] + arr[2], arr[0] + arr[2]); // (두번째 + 세번째)계단과 (첫번째 + 세번째)계단을 비교해서 큰 값을 dp배열에 삽입

  for (let i = 3; i < stairs; i++) {
    dp[i] = Math.max(arr[i] + dp[i - 2], arr[i] + arr[i - 1] + dp[i - 3]); // 네번째 계단부터는 위에 했던 방식대로 loop 돌림
  }
  console.log(stairs);
  console.log(dp[stairs - 1]);
});