Redddy's Devlog

11월 24일 KUPC Open contest가 있었다.오픈컨 치르고 남겨보는 후기...A구현 문제였는데 문제 잘못읽고 1틀 먹고 시작했다. 문제를 꼼꼼히 읽자...B굉장히 재미있는 애드혹 문제였다. 아이디어 떠올리는 과정이 흥미로웠다. 역시 애드혹 문제는 노트 필수.C누적합 문제였는데, 아이디어는 금방 떠올랐으나 러스트 문법이 어색하여 구현이 조금 늦어졌다.D처음에는 투포인터가 떠올랐으나 구현하다보니 브루트포스가 되었다.오픈컨 후기를 적은 이유는 각잡고 러스트를 사용해서 대회에 참여한게(중간에 탈주하긴 했지만) 이번이 처음이였기 때문이었다.파이썬과 비교 했을 때 코드 타이핑 속도가 확실히 차이난다는 것을 느꼈다. 머리속으로는 파바박 이만큼 나가있는데 러스트 코드 피지컬이 못따라와서 답답함을 느끼기도 하..

🔈 문제You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer $k$. Each minute, you may take either the leftmost character of s, or the rightmost character of s.Return the minimum number of minutes needed for you to take at least $k$ of each character, or return -1 if it is not possible to take $k$ of each character. 💫 예시Input: s = "aabaaaacaabc", k = 2..

🔈 문제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]$과 같은지 다른지는 알 수 있지..