Redddy's Devlog

[LeetCode] 2563. Count the Number of Fair Pairs

🔈 문제Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.A pair (i, j) is fair if:0  💫 예시Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6 Output: 6 Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5). 🎱 제한1 nums.length == n$-10^9$ $-10^9$  📚 문제 풀이 문제를 요약하자면 nums에서 i, j 를 골라(i != j)  더했을 때 lower 보다 같거나 ..

🔈 문제You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [$h_i$, $k_i$] represents the $i^{th}$ person of height $h_i$ with exactly $k_i$ other people in front who have a height greater than or equal to $h_i$.Reconstruct and return the queue that is represented by the input array people. The returned queue shou..

🔈 문제당연한 이야기지만, 성공으로 가는 길이 항상 평탄하지만은 않다. 온갖 장애물이 가득하고, 장애물에 막혀서 주저앉을 수도 있다. 그래서 그 장애물을 폭파하려고 한다.성공으로 가는 길은 N×M격자 위에 놓여 있다. 성공으로 가려면 맨 왼쪽 위 칸에서 시작하여 장애물이 없는 상하좌우로 인접한 칸을 밟으면서 맨 오른쪽 아래 칸에 도착해야 한다. 한 번의 폭파 작업으로 D×D 격자 내에 있는 모든 장애물을 없앨 수 있다. 하지만 세상에 공짜는 없는 법. 폭파 작업에도 큰 힘이 들기 때문에, 성공으로 가려면 최소 몇 번의 폭파 작업이 필요한지 알고 싶다.📝입력첫 번째 줄에 격자의 행의 개수 N, 열의 개수 M, 폭파의 범위 D가 주어진다(D ≤ N, M ≤ 500, 1 ≤ D ≤ 100).그 다음 N개의..

레벨 인터뷰 하면서 받았던 피드백을 반영해보자 세웠던 액션 플랜을 준비하기 위한 글이다.    나는코더다에서 카드 게임(Easy)와 카드 게임(Hard)라는 문제가 나왔다.  Easy문제 요약Easy는 상대의 체력 $H$와 내가 가지고 있는 공격력 카드 $N$장과 그리고 각 공격력 카드의 공격력 $d_i$이 주어진다. 카드를 사용하면 상대의 체력은 $d_i$ 만큼 깎이고, $H$가 0이하가 되면 게임은 끝난다. 그리고 각 카드는 한번씩만 사용할 수 있다. 최대한 많은 카드를 사용고자할 때 최대 몇 개의 카드를 사용할 수 있는지를 구하는 문제이다. 모든 카드를 사용하여도 $H$를 만들지 못하면 -1을 반환한다. 문제 접근정리하면 최대한 많은 카드를 사용하여 $H$ 이상을 만들어야 한다. $H$ 이상을 만들..

한동안 알고리즘 공부를 멈췄다가 최근에 다시 흥미가 생겨 발을 들이기 시작했다. 이번에는 또 어떤 씹덕 알고리즘을 배워볼까 하다가 이분 매칭이 맛있어 보였다.    모든 간선 용량이 1이고, 정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 유량 그래프를 이분 그래프(bipartite graph)라고 한다.    이분 그래프에서 한쪽 그룹을 A, 다른 쪽 그룹을 B라고 할 때, 간선의 방향이 모두 A -> B일 때, 최대 유량을 구하는 문제를 이분 매칭(bipartite matching) 문제라고 부른다. 위 그림에서는 생략되었지만 소스에서 A로 가는 간선과 B에서 싱크로 가는 간선이 있다고 생각하면 된다.  이분 그래프에서 매칭은 두 그룹의 정점..

5주차에는 중간중간에 틈틈히 회고 적을 시간도 없이 후루룩 지나갔다. 시간복잡도가 $O(N)$에서 $O(logN)$로 변경된거 같다고 해야하나 뭔가 버그가 있는 듯 하다. 블랙잭 미션 월요일 블랙잭 미션의 리뷰어는 수달이었는데 재미있게 미션을 진행하였다. 좀 오랫동안 고민하고 리뷰 요청을 해서 많은 리뷰를 오고 갔던 것은 아니었지만 그 만큼 깊이 있었다. 화요일 고민이 많았던 블랙잭 미션,, 네이밍, 컨벤션, 구조 등등 열심히 토론하며 미션을 하였다. 이번에는 Participant를 상속받는 Player와 Dealer를 어떻게 배치해야 할지가 고민이었다. 저번주에도 했던 고민이었는데 그때는 그냥 '고민' Thinking 만 했었다면 이제는 고민한 것을 '구현'해보았다. Participant 가 사실 Ha..

🔈 문제 Bessie is studying her favorite subject, Macroeconomics, in cowllege. For her final project, she will be presenting research on exchange rates between countries around the world. In order to make her presentation more lively, she would like to show the relative prices of Big Macs around the world, despite their rather unsavory contents. To illustrate, suppose that Bessie would like to find ..

문자열 $N$ 와 $H$가 주어졌을 때 $N$에 $H$ 있는지 찾는 문자열 검색 알고리즘에 대해 알아보자. 나이브하게 접근해보면 $N$의 첫문자부터 마지막문자까지 $H$와 하나하나 비교해가면서 일치하는지 판별할 수 있고 해당 솔루션의 시간복잡도는 $O(|N|*|H|)$ 이다. 문자열의 길이가 짧다면 해당 접근방법도 구현도 쉽고 나쁘지만은 않다. 하지만 문자열의 길이가 커진다면 제한시간내에 동작하지 못하게 된다. $N[k...i-1]$과 $H[...i-1]$ 까지는 문자열이 일치하였지만 $H[i]$ 문자에서 일치하지 않는경우 다시 $N[k+1]$ 부터 비교하는 것이 아니라 이미 $H[...i-1]$까지 어떤 문자가 있는지 알고 있으니 보지 않아도 $H[k+1]$이 $H[0]$과 같은지 다른지는 알 수 있지..

📖 Solution 문제의 요구사항을 정리해보면 길이 n의 조합중에서 x배수의 숫자의 합에서 y배수의 숫자의 합의 차를 가장 크게 만들 수 있는 조합을 찾고 그 차를 출력하는 문제이다. A - B의 차를 크게 만들기 위해서는 A를 최대한 크게, B를 최대한 작게 만들면 된다. 그렇다면 x의 배수 위치에는 n부터 내림차순으로 배치하고, y의 배수 위치에는 1부터 오름차순으로 배치하면 된다. 둘이 겹치는 부분이 있을 수 있는데 이는 0이 되기 때문에 상관없다. 그렇다면 이제 구해야 하는 점은 n에서 x 배수의 갯수, y 배수의 갯수 그리고 겹치는 부분이다. 이 겹치는 부분은 lcm 을 사용하여 찾을 수 있다. 💻 Code HTML 삽입 미리보기할 수 없는 소스 🔗 Problem https://codeforc..

🔈 문제 은수는 맛집을 탐방하러 도시로 여행을 떠날 것이다. 은수가 갈 도시에는 총 $N$개의 맛집이 있다. 도시에는 맛집에서 맛집으로 이동할 수 있는 일방통행 길이 $M$개 있고, 각 길의 중간에는 기념품 상점이 있다. 어떤 길은 출발하는 맛집과 도착하는 맛집이 같을 수도 있으며, 여러 길이 같은 맛집을 연결할 수도 있다. 은수는 도시의 맛집에서 여행을 시작해서, 길을 이용해 맛집을 탐방하다 도시의 맛집에서 여행을 끝낼 것이다. 여행을 시작한 곳과 여행을 끝낸 곳이 같을 필요는 없다. 도시는 은수가 사는 마을에서 멀리 떨어져 있기 때문에, 은수는 한 번의 여행에서 최대한 많은 맛집과 상점을 들르려고 한다. 특히, 여행 중에 모든 맛집을 방문하거나 모든 기념품 상점을 방문한다면 다음 여행에서 할인 혜택을..