오늘도 맑음

이 문제는 N이 크지 않아서 dfs 로 풀어도 가능하다.다음과 같이 각 노드에 대해 뻗어 나가는 경우는 2개이다.1. 인사를 한다2. 인사를 안한다트리로 나타내면 다음과 같고, 시간복잡도는 2의 N승이다.하지만, 제한조건 N의 수가 커진다면, 시간복잡도를 만족하지 않을 수 있다.그럼 어떻게 최적화를 할 수 있을까? 경우의 수를 구하는 문제에서는 배낭(Knapsack) 알고리즘으로 해결할 수 있었다.같은 색 노드를 봤을 때 사실 인덱스(i)만 다르지 얻을 수 있는 행복과 현재 체력은 같다. 따라서 i 번째 사람과 인사를 안할 경우 i-1번째 사람한테서 가져오면 된다. 하지만 i번째 일때도 경우의 수가 4개 정도 존재한다. 그 중 어떤 경우의 수에서 값을 가져와야할까?이것까지 고려해주기 위해 dp는 1차원 ..

각 도시들 사이에 길이 있을 수도 있고, 없을 수도 있다. 도시들의 연결되어 있는 정보를 보고 여행갈 수 있는 지를 판별하여 "YES"나 "NO"를 출력하면 된다.도시들이 연결되어있다는 말은 하나의 그래프라는 것이고 유니온 파인드 알고리즘을 사용하여 알 수 있다. 유니온 파인드각 연결정보가 주어질 때, 그 그래프를 모두 연결해보면 2개의 그래프로 나뉜다는 것을 알 수 있다.  그렇다면 유니온 파인드는 어떻게 구현할까? 유니온 파인드는 부모(Parent) 배열을 사용하여 각 원소가 속한 집합을 나타낸다.초기에는 각 원소가 자기 자신을 부모로 가지도록 설정한다.(1) Find 연산 (경로 압축: Path Compression)Find 연산은 특정 원소가 속한 집합의 대표(root) 원소를 찾는 과정일반적인 ..

국내 1위 공급망관리 소프트웨어 기업 '엠로' 라는 기업에 대해 분석해보았습니다.메인 배너- 국내 1위 공급망 관리 소프트웨어- AI기반 디지털 혁신 소프트웨어- 국내 1위 AI 기반 기업용 공급망관리 소프트웨어 기업 엠로, 코스닥 시장 상장- 기업 고객에게 가장 필요하고 실용적인 AI기반 디지털 혁신 소프트웨어 여기서 키워드를 뽑아낼 수 있음1) 공급망 관리 소프트웨어2) AI 기반 디지털 혁신 소프트웨어👉 아! '엠로'는 AI 활용해 공급망 관리 소프트웨어를 개발하는 B2B 회사이구나! 국내 1위로 대단하네! 제공하는 제품, 솔루션을 'Solution & Services' 라고 표현했는데, 구매 SCM솔루션, 클라우드, AI솔루션, 기술 지원 등 다양한 솔루션을 개발하는 것을 확인할 수 있었습니다...

목차1. 문제 풀이2. 전체 코드 (+시간 복잡도) 1. 문제 풀이트리의 부모를 찾기 위해, bfs를 순회하며 부모를 방문 표시 대신 적어주면 된다. 1) 인접한 노드들을 edges 배열에 저장 2) bfs 코드- shift 연산 대신 left 변수를 사용하여 시간 복잡도를 줄였다.- 루트 노드의 부모는 없기 때문에 -1을 저장한다.- 노드를 순회하면서 해당 노드(cur)와 연결된 "다음 노드(next) 중에서 부모 노드가 없다면"   👉다음 노드(next)는 현재 노드(cur)의 자식이 된다.  2. 정답 코드const fs = require("fs");const input = fs.readFileSync("./example.txt", "utf8").trim().split("\n");// 입력cons..

보호되어 있는 글입니다.

목차1. 문제 설명2. 문제 풀이3. 전체 코드4. 배운 점1. 문제 설명입력players : 매시각의 플레이어 수/ m : 서버를 증설하기 위한 사람 수 조건/ k : 서버 가동 시간매시각 플레이어들의 수를 통해 증설해야하는 서버 수를 계산해야한다. 이 때, m명이 늘어날 때마다 서버 1대가 추가로 필요하다.예를 들어, m = 3일 때, 3명일 때 서버를 1대 늘려야하고, 6명일 때 서버를 2대 늘려야한다.이 서버의 가동시간은 k이다. 따라서 가동시간 이후에는 서버를 종료시켜 계산해야한다.2. 문제 풀이 1️⃣ 변수 초기화k 시간 이후 서버를 종료시키기 위해, 각 서버의 종료시간을 저장할 큐가 필요하다 생각했다.2️⃣ 종료 시간을 넘긴 서버 제거하기몇개를 더 가동할지 계산하기 전, 종료시간이 지난 서버..

목차1. 문제 설명2. 문제 풀이3. 정답 코드1. 문제 설명'뿌요뿌요'는 같은 색상끼리 터트리는 게임이다. 🌱 뿌요뿌요 규칙1) 같은 색상이 4개 이상이 있을 때 (인접한 상하좌우 4개 이상), 터뜨린다.2) 만약 터뜨릴 수 있는 것들이 여러 집단일 때, 동시에 터뜨린다. 이과정을 몇번 반복하는 지 카운트하는 문제이다.2. 문제 풀이1) DFS를 순회하며, 4개 이상인지 확인하기 - dfs 함수를 사용하여 같은 색깔의 블록을 탐색한다. 탐색한 블록의 좌표를 record 배열에 저장한다. 2) 4개 이상일 경우, 다녀간 경로를 모두 터뜨리기 - 탐색이 끝난 후, record 배열의 길이가 4이상이면 해당 블록들을 터뜨린다. - 터뜨린다는 것을 '.' 로 만드는 것이다. 3) 모두 터뜨린 다음 그리드..

원인jest는 기본적으로 css 파일을 처리할 수 있는 기본 설정이 되어 있지 않기 때문에, 추가 설정을 해야 한다.cf) 바벨도 마찬가지로 설정을 해줘야 한다. 해결https://jestjs.io/docs/webpack#handling-static-assets > 스타일시트와 이미지와 같은 정적 파일을 처리하기 위해 jest를 구성해야 한다. 보통의 경우 이 파일들은 테스트를 위하여 필요가 없기 때문에 단순히 파일을 모킹해서 사용할 수 있다. 만약 CSS Module를 사용할 경우에는 클래스네임을 보여주기 위해 프록시를 모킹하는 것이 더 낫다. 1. jest 설정모킹할 대상(이미지, css)과 모킹 파일을 매핑해준다.* ModuleNameMapper는 jest의 설정 옵션 중 하나로, 특정 모듈 이름을..

목차1. 문제 풀이2. 정답 코드3. 시간 복잡도1. 문제 풀이외판원이 모든 도시를 한번씩 거쳐 마지막에 다시 출발 도시로 돌아오는 데 걸리는 최소 비용을 구하는 문제이다. 4개의 도시에 대하여, i -> j 로 이동할 때 걸리는 비용이 2차원 배열로 주어진다.이 때, 기본적인 dfs 코드와는 다르게 '비용'이 있으므로, 방문할 때마다 비용을 더해줘야 한다.또한 여러 케이스의 경로에 대하여 '총 비용'을 비교하여 최소 비용을 출력해야하므로, 모든 경로를 탐색하기 위해 백트래킹 개념을 사용하였다. 백트래킹은 쉽게 말하자면, 순열과 같다.'A' , 'B', 'C', 'D' 가 있을 때, ABCD, ABDC, ACBD, ACDB, .... 순으로 진행되는데, 이를 구현하기 위해 1. 한 가지 선택지를 택함2...

목차1. 문제 접근2. 문제 풀이3. 정답 코드1. 문제 접근삼각형의 맨 꼭대기에서 바닥까지 내려가면서, 거쳐한 수들의 합이 최댓값이 되는 수를 리턴한다.아래칸으로 이동할 때는 왼쪽 대각선, 오른쪽 대각선 아래로 이동한다. 화살표 방향으로 이동하면서 그 수들을 계속 더해주면 되기 때문에, 누적합 문제이다.누적합이란, a[i] = a[i-1] + ??이런식으로 구현하는 것을 말한다. 그렇다면 2차원 배열로 주어지는 triangle 배열에서는 어떤식으로 누적합을 해줘야 할까? i = 2일 경우를 살펴보자✔ j = 0 또는 j == i 일 때를 제외하고, 즉 맨 앞과 맨 뒤를 제외하고는 기본적으로 화살표가 양쪽에서 오는 것을 확인할 수 있다.그 화살표들 중 최댓값을 누적해서 더해주면 된다.triangle[i]..