알고리즘연구소👨💻 (26) 썸네일형 리스트형 [Leetcode 826번 문제] 826. Most Profit Assigning Work 문제 상황You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:difficulty[i] and profit[i] are the difficulty and the profit of the ith job, andworker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).Every worker can be assigned at most one job, but one job can be completed multiple times.For ex.. [Leetcode 633번 문제] 633. Sum of Square Numbers 문제 상황Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.c가 두개의 제곱수의 합으로 나타낼 수 있는지 확인하라는 문제입력정수 c출력제곱수의 합으로 나타낼 수 있는지에 대한 불값과정일단 c는 제곱수의 합이기 때문에 특정c - 특정 제곱수가 제곱수인지 확인하는 문제여도됨.그럼 모든 제곱수들을 저장해놓고 그냥 해시하면 되지 않을까?대충 2 ** 16번의 계산만 하면 돼서 문제 없다고 생각했다.알고리즘 개요도 알고리즘class Solution { typedef long long ll; unordered_map container;public: bool judgeSqua.. [Leetcode 330번 문제] 330. Patching Array 문제 상황Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.Return the minimum number of patches required.nums의 정렬 배열이 있고 n이라는 정수를 추가할 거임, 요소를 add/patch 한다, 1부터 n까지의 모든 수를 배열안의 수로 제작할 수 있게 되는 최소의 변형 수를 구하는 문제입력1 1 nums is sorted in ascending order.1 출력배열의 조합으로 [1.. [Leetcode 648번 문제] 648. Replace Words 문제 상황In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence wi.. [백준 19648번 문제] 미하일 2마리 문제 설명위의 그림처럼 된 방향 그래프가 있다. 여기서 미하일이란 캐릭터가 파란색 지점에 총 2마리 놓여있다.1초마다 각 미하일은 인접 노드로 움직인다. 하지만 두 미하일은 각각의 위치에서 반대 미하일까지의 거리가 3이하가 되는 경로쌍으로는 이동하지 않게 되어있다.이런 조건으로 N초가 흘렀을 때 미하일들이 사냥할 수 있는 경로의 총 방법 수를 구해라. 단 두 미하일이 a, b에 있는 경우와 b, a에 있는 경우는 다른 경우로 취급한다.입력10억 이하의 정수출력n초 동안 사냥할 수 있는 총 방법 수를 1,000,000,007로 나눈 나머지과정입력값의 시간초가 10억이다. 얼핏보면 시간제한이 7초이기 때문에 풀 수 있을 것처럼 느껴지기도 하지만 사실 10억 초에 순간마다 100번만 계산을 해도 총 계산은 1.. [백준 27652번 문제] AB 문제설명집합 두개가 있고 3가지 커맨드가 있음add,delete,find,add, delete는 더하고 지우기 가 끝find는 문자열을 둘로 나눠서 앞의 부분은 A 뒷부분은 B에서 찾을 수 있는 경우의 수의 총합을 찾아서 출력하는 함수다.입력첫째 줄에 쿼리의 개수 Qn줄동안add A aba delete A a find abab출력find 구문마다 나올 수 있는 경우의 수의 총합을 출력과정처음에는 이렇게 생각했다 일단 find쿼리에서 일어나는 일은 O(문자열길이) 안에 끝내야한다고 생각한다. 애초에 집합으로 저장해야한다고 하기도 했고 해시가 바로떠오른다. 저장되는 쿼리 양도 해봤자 1000이다.유일하게 걱정되는건 subStr이 O(글자수)라고 알고있는데 1000 글자라면어찌됐던 1000 * 1000 번 연.. [Leetcode 2370번 문제] 2370. Longest Ideal Subsequence 문제 설명Ideal Subsequence란 Subsequence의 인접한 두 칸의 요소들의 인덱스 차이가 k 이내일 때를 의미한다. 어떤 문자열이 주어졌을때 그 문자열의 longest ideal string을 찾아야한다. 입력행렬의 길이 최대 10만, 칸 차이 최대 25각 행렬의 요소는 a ~ z출력Integer , 가장 긴 Subsequence의 길이과정이상적인이란말을 보면 가장긴 증가하는 부분수열이 생각난다. 다만 거긴 방향인데 여긴 아니란거 그래서 이 점이 다르다증가하는 부분수열에선 각 인덱스들이 왼쪽은 자기보다 작고 오른쪽은 자기보다 크거나 같은 자리를 찾아서 공통으로 사용함으로써 n^2 을 피할 수 있었는데 여기서는 그게 안된다.그러면 그냥 n ^ 2을 해야하는데 그것도 잘 안된다. 일단 길이가.. [Leetcode 881번 문제] 881. Boats to Save People 문제 설명사람 배열이라는게 존재함. 모든 사람들을 보트에 태워야한다. 보트에는 최대 2명이 탈 수 있고 그 두명의 무게의 합은 최대 중량 limit을 초과할 수 없다. 보트가 무한할때 이 인원들을 태울 수 있는 보트의 최소 숫자를 구해라.입력1이상 5만 이하의 사람배열각 사람의 무게는 limit과 3만보다 작고 1보다 큰 정수이다출력정수, 보트의 최소 개수과정보트를 태운다.배열이 나에게 아주 호의적인 상황이라면 (모든 탑승자의 크기가 limit / 2) 답은 뭐 나누기 2의 몫과 같음. 이 문제는 그렇지않음 보트의 수는 무한하다는것도 특징이다.그럼 이상적인상황을 만드는 방법을 구해야했다. 각 보트에 탈 수 있는 인원은 2명이 최대니까정렬해놓고 투포인터로 최소 무게 인원과 최대 무게 인원을 더해보는 방식을.. 이전 1 2 3 4 다음
