오늘도 맑음

목차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) 모두 터뜨린 다음 그리드..

목차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]..

목차1. 문제 풀이2. 정답 코드 (shift 연산 x)3. 시간 복잡도 1. 문제 풀이1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 방법- bfs 코드를 순회한다.- visited 배열에 깊이(현재 노드까지의 간선의 개수)를 저장한다.2. 정답 코드 (shift 연산 x)shift() 연산을 O(1)로 만들기 위해 front 변수를 사용한다. - 큐에서 노드 하나를 제거하기 위해(1) q[front] 에서 노드를 꺼냄(2) front++이 두개의 연산(1 + 2)을 합쳐서👉 var cur = q[front++] - 언제까지 반복하는지👉 while(front function solution(n, edge) { var answer = 0; var edges = Array.from({l..

목차1. 문제 풀이2. 내가 푼 정답 (shift 연산 사용)3. 개선한 풀이 (큐 직접 구현)1. 문제 풀이2차원 평면에서 출발지점과 목적지점이 주어질 때, 장애물(0)을 이동하는 데 걸리는 최단 거리를 구하는 문제이므로, bfs로 해결할 수 있었다.다만, 시간 복잡도를 줄이는 데에서 애를 먹었다. 시간 복잡도제한 조건에서 알다시피 maps의 row, col은 최대 100이다. 따라서 row, col을 둘 다 N 이라고 하겠다.이 때, 시간 복잡도는 다음과 같다.시간 복잡도- 모든 칸을 순회 : O(N^2)- shift 연산 : O(N^2)👉 O(N^4) 최악의 경우 N 👉 O(10^8) 여기서 문제였던 부분이 1초당 10^8 연산을 할 수 있는데, 그럼 간당간당하게 되거나 안되거나 하겠다. 라는 ..

목차1. 문제 풀이  1) 테두리 구하기  2) 테두리 이동할 때, 풀이법 (❌ 주의: 칸 이동과 다름)2. 전체 코드3. 느낀 점1. 문제 풀이그림과 같이 여러 다각형이 배열 형태로 주어질 때, 테두리 정보를 배열에 저장해두어야 한다.출발지 (x, y) 에서 목적지 (x, y) 에 도달할 때까지 걸리는 가장 짧은 거리를 계산하기 위해서는 bfs 코드를 수행한다. 직사각형 입력 형식직사각형 배열은 [fromX, fromY, toX, toY] 로 주어지며, 각각 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점 정보이다.예를 들어, 가장 아래의 직사각형은 [1,1,7,4] 로 주어진다. 처음 생각한 방식처음에 생각한 방식은 직사각형이 주어질 때, 모든 선분을 1로 만드는 것이였다.그리고 1과 0(초기화) 경계에 있는 ..

🧾 목차1. 문제 설명2. 문제 풀이3. 전체 코드 (dfs)4. 다른 풀이 (bfs)1. 문제 설명n개의 송전탑이 트리 형태로 연결되어 있음.주어진 전선들 중 하나를 끊어서 트리를 두 개의 전력망으로 분할해야 함.두 전력망의 송전탑 개수 차이(절대값)를 최소화하는 경우를 찾아야 함.이 최소 차이를 return 하는 함수를 구현해야 함.2. 문제 풀이트리에서 한 곳의 연결을 끊으면 2개로 나눠진다.만약 [a, b] 를 끊었다면 a, b 노드는 각각 다른 트리에 속한다.따라서 a에서 시작하는 dfs 순회를 돌려서 트리에 속한 노드 개수를 구하고, 2n 에서 개수를 빼서 절댓값을 구하면 된다. 1️⃣ 연결 초기화 2️⃣ dfs 함수[a, b] 연결을 끊어서 a 부터 dfs를 돌린다면 exceptV는 b로 ..

목차1. 문제 설명2. 문제 풀이3. 전체 코드1. 문제 설명n 개의 컴퓨터가 있을 때, 네트워크 개수를 계산한다.☁ 네트워크란 컴퓨터가 연결된 형태를 의미한다.if) A - B 와 B - C 가 연결되어 있다면 A - B - C는 하나의 네트워크 안에 있다고 할 수 있다. 입출력 => n 개의 컴퓨터, 그리고 컴퓨터의 연결 정보가 주어질 때, 네트워크의 개수를 리턴한다. 첫번째 예시 두번째 예시2. 문제 풀이각 노드의 연결과 관련된 문제이므로, dfs 로 해결하였다.1) dfs 를 한번 호출했을 때, 연결된 컴퓨터를 모두 방문할 수 있다.2) 연결되지 않은 컴퓨터는 다시 dfs 를 호출해야 한다. 초기화 dfs 함수 dfs 함수를 호출하는 부분 시간복잡도1) 전체 네트워크 탐색 과정 → O(N)2) 한..