ALiNew ALiNew

프로그래머스

• [Algo Rhythm🕺💃] 프로그래머스 - 기지국 설치

  Algo Rhythm🕺💃/Programmers 2022. 9. 24. 16:51

  💫문제 분석 아파트의 개수를 $n\ (1 \le n \le 2 \times 10^8)$, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열을 $S\ (1 \lt \left\vert S \right\vert \lt 10^4,\ S는\ 오름차순\ 정렬)$, $S$에 속하는 각 기지국을 $s_i\ (1 \le s_i \le n,\ 1 \le i \le \left\vert S \right\vert )$, 전파의 도달 거리를 $w(1 \le w \le 10^4)$, 한 기지국이 전파를 전달할 수 있는 기지국들의 최개 개수를 $d\ (=2 \times w + 1)$라고 하자. 현재 설치된 기지국 $s_i$의 전파 전달 범위를 $rcvd_i$라고 할 때, $rcvd_i$는 다음과 같다. $\begin{matri..

  Read More

• [Algo Rhythm🕺💃] 프로그래머스 - 숫자 게임

  Algo Rhythm🕺💃/Programmers 2022. 9. 24. 00:59

  💫문제 분석 A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열을 $A$, i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열을 $B$라고 하자. 이때 두 배열의 원소 $a_i, b_i$, 배열의 크기 $L$은 아래와 같이 정의할 수 있다. $1 \le L = \left\vert A \right\vert = \left\vert B \right\vert \le 10^5$ $1 \le a_i, b_i \le 10^9 (a_i \in A, b_i \in B, i \in \left[ 1, L \right])$ A팀은 출전 순서가 이미 고정되어 있다. 따라서 B팀이 최대 승점을 얻기 위해서는 각 $a_i$를 패배할 수 있는 즉, $a_i < b_i$ 조건을 만족하는 가장 작은 $b_i$와 매칭하..

  Read More

• [Algo Rhythm🕺💃] 프로그래머스 고득점 kit 도둑질

  Algo Rhythm🕺💃/Programmers 2020. 8. 8. 22:49

  📚 문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 🎯 어떻게 풀었나 Backtracking을 이용한 첫번째 시도 (0/ 100) => 정확성은 모두 시간 초과, 효율성은 모두 통과 🙅‍♂️🙅‍♀️🙅 class Solution { private..

  Read More

• [Algo Rhythm🕺💃] 프로그래머스 고득점 kit 등굣길

  Algo Rhythm🕺💃/Programmers 2020. 8. 6. 15:21

  📚 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다. m과..

  Read More

• [Algo Rhythm🕺💃] 프로그래머스 고득점 kit 정수 삼각형

  Algo Rhythm🕺💃/Programmers 2020. 8. 4. 15:40

  📚 문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 🎯 어떻게 풀었나 1. DFS (50/ 100) - 효율성 통과 🙅‍♀️🙅‍♂️🙅 class Solution { public int solution(int[]..

  Read More

• [Algo Rhythm🕺💃] 프로그래머스 고득점 kit 예산

  Algo Rhythm🕺💃/Programmers 2020. 7. 30. 15:38

  📚 문제 설명 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다. 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다. 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각..

  Read More

• [Algo Rhythm🕺💃] 프로그래머스 고득점 kit 순위

  Algo Rhythm🕺💃/Programmers 2020. 7. 29. 14:47

  📚 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 선수의 수는 1명 이상 100명 이하입니다. 경기 결과는 1개 이상 4,500개 이하입니다. results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는..

  Read More

• [Algo Rhythm🕺💃] 프로그래머스 고득점 kit 가장 먼 노드

  Algo Rhythm🕺💃/Programmers 2020. 7. 28. 12:35

  📚 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 🎯 어떻게 풀었나 i..

  Read More