Algorithm (38) 썸네일형 리스트형 [JavaScript] 백준 11725 - 트리의 부모 찾기 목차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.. [Javascript] 프로그래머스 - 서버 증설 횟수 목차1. 문제 설명2. 문제 풀이3. 전체 코드4. 배운 점1. 문제 설명입력players : 매시각의 플레이어 수/ m : 서버를 증설하기 위한 사람 수 조건/ k : 서버 가동 시간매시각 플레이어들의 수를 통해 증설해야하는 서버 수를 계산해야한다. 이 때, m명이 늘어날 때마다 서버 1대가 추가로 필요하다.예를 들어, m = 3일 때, 3명일 때 서버를 1대 늘려야하고, 6명일 때 서버를 2대 늘려야한다.이 서버의 가동시간은 k이다. 따라서 가동시간 이후에는 서버를 종료시켜 계산해야한다.2. 문제 풀이 1️⃣ 변수 초기화k 시간 이후 서버를 종료시키기 위해, 각 서버의 종료시간을 저장할 큐가 필요하다 생각했다.2️⃣ 종료 시간을 넘긴 서버 제거하기몇개를 더 가동할지 계산하기 전, 종료시간이 지난 서버.. [Javascript] 백준 - Puyo Puyo 목차1. 문제 설명2. 문제 풀이3. 정답 코드1. 문제 설명'뿌요뿌요'는 같은 색상끼리 터트리는 게임이다. 🌱 뿌요뿌요 규칙1) 같은 색상이 4개 이상이 있을 때 (인접한 상하좌우 4개 이상), 터뜨린다.2) 만약 터뜨릴 수 있는 것들이 여러 집단일 때, 동시에 터뜨린다. 이과정을 몇번 반복하는 지 카운트하는 문제이다.2. 문제 풀이1) DFS를 순회하며, 4개 이상인지 확인하기 - dfs 함수를 사용하여 같은 색깔의 블록을 탐색한다. 탐색한 블록의 좌표를 record 배열에 저장한다. 2) 4개 이상일 경우, 다녀간 경로를 모두 터뜨리기 - 탐색이 끝난 후, record 배열의 길이가 4이상이면 해당 블록들을 터뜨린다. - 터뜨린다는 것을 '.' 로 만드는 것이다. 3) 모두 터뜨린 다음 그리드.. [Javascript] 백준 - 외판원 순회 2 목차1. 문제 풀이2. 정답 코드3. 시간 복잡도1. 문제 풀이외판원이 모든 도시를 한번씩 거쳐 마지막에 다시 출발 도시로 돌아오는 데 걸리는 최소 비용을 구하는 문제이다. 4개의 도시에 대하여, i -> j 로 이동할 때 걸리는 비용이 2차원 배열로 주어진다.이 때, 기본적인 dfs 코드와는 다르게 '비용'이 있으므로, 방문할 때마다 비용을 더해줘야 한다.또한 여러 케이스의 경로에 대하여 '총 비용'을 비교하여 최소 비용을 출력해야하므로, 모든 경로를 탐색하기 위해 백트래킹 개념을 사용하였다. 백트래킹은 쉽게 말하자면, 순열과 같다.'A' , 'B', 'C', 'D' 가 있을 때, ABCD, ABDC, ACBD, ACDB, .... 순으로 진행되는데, 이를 구현하기 위해 1. 한 가지 선택지를 택함2... [JavaScript] 프로그래머스 - 정수 삼각형 목차1. 문제 접근2. 문제 풀이3. 정답 코드1. 문제 접근삼각형의 맨 꼭대기에서 바닥까지 내려가면서, 거쳐한 수들의 합이 최댓값이 되는 수를 리턴한다.아래칸으로 이동할 때는 왼쪽 대각선, 오른쪽 대각선 아래로 이동한다. 화살표 방향으로 이동하면서 그 수들을 계속 더해주면 되기 때문에, 누적합 문제이다.누적합이란, a[i] = a[i-1] + ??이런식으로 구현하는 것을 말한다. 그렇다면 2차원 배열로 주어지는 triangle 배열에서는 어떤식으로 누적합을 해줘야 할까? i = 2일 경우를 살펴보자✔ j = 0 또는 j == i 일 때를 제외하고, 즉 맨 앞과 맨 뒤를 제외하고는 기본적으로 화살표가 양쪽에서 오는 것을 확인할 수 있다.그 화살표들 중 최댓값을 누적해서 더해주면 된다.triangle[i].. [Javascript] 가장 먼 노드 목차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.. [Javascript] 프로그래머스 - 게임 맵 최단거리 목차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 연산을 할 수 있는데, 그럼 간당간당하게 되거나 안되거나 하겠다. 라는 .. [Javascript] 프로그래머스 - 아이템 줍기 목차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 4 5 다음 목록 더보기
