전체 글
-
[Algo Rhythm🕺💃]BOJ 13458 - 시험감독Algo Rhythm🕺💃/BOJ 2021. 3. 9. 16:53
문제 분석 시험장의 개수를 N(1 ≤ N ≤ 1,000,000), i번째 시험장에 있는 응시자의 수를 Ai(1 ≤ Ai ≤ 1,000,000) , 총감독관과 부감독관이 한 시험장에서 감시할 수 있는 응시자의 수를 각각 B, C(1 ≤ B, C ≤ 1,000,000)라고 하자. 그리고 i번째 시험장에 들어가야 하는 총감독관과 부감독관의 수를 각각 $n\_main_i$, $n\_sub_i$라고 하자. 총감독관은 각 시험장에 무조건 한 명 들어가야 하고 부감독관은 없거나 여러 명 있어도 된다. 따라서 i번째 시험장에서 필요한 감독관 수의 최솟값은 아래 부등식을 만족하는 가장 작은 $n\_sub_i$를 구하는 것과 같다. $B\ +\ C \times n\_sub_i\ \ge A_i$ 이를 통해 우리가 최종적으로..
-
[Algo Rhythm🕺💃] LeetCode 720. Longest Word in DictionaryAlgo Rhythm🕺💃/LeetCode 2020. 9. 4. 01:05
📚 Problem description Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string. Example 1: Input: words = ["w","wo","wor","worl", "world..
-
[Algo Rhythm🕺💃] LeetCode 208. Implement Trie (Prefix Tree)Algo Rhythm🕺💃/LeetCode 2020. 9. 3. 16:04
📚 Problem description Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true Note: You may assume that all inputs are consist of lowercase letters a-z. All inputs ar..
-
[Algo Rhythm🕺💃] BOJ 16288. Passport ControlAlgo Rhythm🕺💃/BOJ 2020. 9. 3. 10:32
📚 문제 설명 $N$명의 입국 승객이 여권 심사를 위하여 그림 G.1 과 같이 입국 대기 줄에서 $[1, 2, … , N − 1, N]$ 순서로 기다리고 있다. 입국 승객은 준비된 $k$개의 여권 심사 창구 중 하나를 통과한 뒤 공항을 빠져나갈 수 있다. 입국할 때의 줄 선 승객의 순서를 $[1, 2, … , N − 1, N]$이라고 할 때 $k$개의 여권 심사 창구를 통과하여 입국장을 빠져나가는 순서 $[π_{1}, π_{2}, … π_{N−1}, π_{N}]$는 처음과 달라질 수 있다. $k$개 여권 심사 창구가 준비되어 있을 때, 이 입국장을 빠져나가는 순서가 가능한 순서인가를 계산해야 한다. 예를 들어 설명해보자. 만일 $N = 3, k = 2$ 라고 할 때 입국장을 빠져나가는 순서 중 $[1, ..
-
🌲 Segment Tree 2 - 더 빠른 update를 위한 Lazy Propagation!ALicademy 👩🏫👨🏫/알고리즘 2020. 9. 1. 19:27
원본은 링크를 통해 확인하실 수 있습니다. Intro 🚀 이전 글 마지막에 말씀드렸듯이 segment tree에서 특정 구간을 update할 때 leaf node를 일일이 방문해서 update하면 중복해서 방문하는 노드가 생깁니다. 이 때문에 정말 많은 update 연산을 해야 하는 경우 시간이 오래 걸릴 수 있습니다. 그래서 오늘은 더 빠른 udpate를 위한 기법인 Lazy propagation😴 에 대해 배워 보겠습니다! Lazy Propagation 😴 지금부터 여러분이 노드를 직접 update하는 일꾼👷♀️👷이라고 생각해봅시다! 여러분은 아래 예제와 같은 segment tree를 돌아다니면서 노드를 udpate합니다. 만약 arr의 0번째부터 2번째 인덱스까지 update하라는 작업이 들어오면..
-
🌲 Segment Tree 1 - Segment Tree란?ALicademy 👩🏫👨🏫/알고리즘 2020. 8. 31. 16:33
원본은 링크를 통해 확인하실 수 있습니다 😃 Intro 🚀 스마트폰을 켜서 SNS를 들어가봅시다. 지난 한 달 동안 여러분이 받은 좋아요👍 의 합을 구하고 싶으면 어떻게 하면 될까요? 아마 여러분이 저와 비슷하다면 가장 먼저 '모든 게시물 중 지난 한 달 동안의 게시물에서 받은 좋아요 수를 일일이 더하면 되지 않을까요?' 라고 말씀하실지도 모릅니다. 이 방법을 사용했을 때 게시물의 수가 $n$개이고 특정 기간 동안 받은 좋아요 수의 합을 묻는 query를 $m$개 처리해야 한다면 시간 복잡도는 $O(mn)$입니다. 이 방법도 나쁘지 않지만 더 효율적인 방법은 없을까요? 그래서 오늘 우리가 배울 것은 바로 구간의 합/ 차/ 최대값/ 최소값 등을 효율적으로 구하기 위해 쓰이는 자료 구조인 🌴Segment T..
-
[Algo Rhythm🕺💃] BOJ 17528. Two MachinesAlgo Rhythm🕺💃/BOJ 2020. 8. 26. 21:06
📚 문제 설명 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti를 완료하기 위해 머신 A를 선택하면 ai시간이 걸리고 머신 B를 선택하면 bi 시간이 걸린다. 각 머신은 어느 순간에 최대 하나의 작업만 수행할 수 있으며, 한 작업이 시작되면 그 작업을 완료하기 전까지 다른 작업을 그 머신에서 수행할 수 없다. SOPT 는 모든 작업을 완료하기 위한 최소의 완료 시간을 구하고자 한다. 예를 들어, 세 개의 작업이 t1, t2, t3가 주어져 있고 a1 = 2, b1 = 3, a2 = 5, ..
-
[Algo Rhythm🕺💃] LeetCode 653. Two Sum IV - Input is a BSTAlgo Rhythm🕺💃/LeetCode 2020. 8. 24. 15:24
📚 Problem description Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target. Example 1: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True Example 2: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False 🎯 Solution /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNo..