오늘도 맑음

목차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. 문제 풀이4. 전체 코드1. 설명1️⃣ 문제 분석출발 지점부터 목적 지점(distance) 사이의 돌 들이 있다.그 돌중에서 n 개의 돌을 삭제하여 각 구간(남은 돌 사이 거리)의 최소 값을 구하고,이 최소값들 중 가장 큰 값(최대 최소 거리)을 구하는 문제이다. 2️⃣ 입출력돌의 개수(rocks.length)가 5일 때, 2개의 돌을 삭제하는 경우의 수는,C(5, 2) = 10총 10가지의 경우의 수가 존재한다. 해결과정1) 2개의 돌을 선택하여 제거(총 10가지 조합 가능)2) 남은 돌들 사이의 거리를 계산3) 각 경우마다 최소 거리값을 구함4) 이 최소값들 중 가장 큰 값을 구하면, 4이다. 3️⃣ 제한사항  완전 탐색의 경우, C(바위 개수, 삭제할 바위 ..

🧾 목차1. 문제 설명2. 문제 풀이3. 정답 코드4. 총평1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/340212 퍼즐 해결 시 소요 시간 계산 방법예제 조건- 퍼즐 난이도 : 1,5,3- 퍼즐당 기본 시간 : 2,4,7- 나의 레벨 : 1 계산 과정1. 첫 번째 퍼즐 (난이도 1, 시간 2)- 내 레벨(1)과 같으므로, 소요 시간 = 2 2. 두 번째 퍼즐 (난이도 5, 시간 4)- 난이도 (5) > 내 레벨(1)이므로 추가 시간 발생 - 추가 시간 공식  👉 (이전 퍼즐 소요 시간 + 현재 퍼즐 소요 시간 ) x (퍼즐 난이도 - 내 레벨) + 현재 퍼즐 소요 시간 - 적용  (2 + 4) x (5 - 1) + 4 = 6 ..