알고리즘 공부16 [프로그래머스] 기능 개발 문제 풀이 (파이썬/ 큐) 문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100% 일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 .. 2022. 1. 25. [백준] 구간 합 구하기 4 풀이(파이썬/python/구간 합/prefix sum) 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 예제 입력 5 3 5 4 3 2 1 1 3 2 4 5 5 예제 출력 12 9 1 구간 합을 사용한 문제풀이 구간 합(prefix sum) : 주어진 수열에서 임의의 구간에 포함된 요소의 합을 빠르게 구하는 방법 앞에서부터 합을 누적하여 미리 계산해 저장해 놓고 활용하는 방법입니다 주어진 리스트 : numbers.. 2022. 1. 15. [ LeetCode] Letter Combinations of a Phone Number 문제 풀이(Backtracking/백트레킹/Python/파이썬) 2에서 9까지의 숫자를 포함하는 문자열이 주어지면 숫자가 나타낼 수 있는 모든 가능한 문자 조합을 반환합니다. 어떤 순서든 답을 반환하세요. 숫자 대 문자 매핑(전화 버튼과 마찬가지로)이 아래에 나와 있습니다. 1은 어떤 문자에도 매핑되지 않습니다 예시 문제 풀이 이 문제의 예시들을 보면 만약 입력 digits가 23이라면 2에 매핑되는 문자는 abc이고 3에 매핑되는 문자는 def이므로 이 문자들을 조합한 결과를 반환해야 하고입력이 없다면 만들 수 있는 문자 조합이 없기 때문에 빈 리스트를 반환해야 합니다 숫자 입력은 길이 4까지 받을 수 있고 digits는 2부터 9까지 입니다. 관련 주제는 다음과 같고 저는 B.. 2021. 12. 28. [LeetCode] Maximum Subarray 문제풀이(DP/동적 프로그래밍/파이썬/Python) 문제 : Maximum Subarray 문제 설명 정수 배열의 nums가 주어졌을 때, 합이 가장 큰 연속적인 하위 배열(하나 이상의 숫자를 포함)을 찾아 그 합을 반환합니다. 하위 배열은 배열의 연속적인 부분입니다. 문제 풀이 이 문제의 관련 주제입니다 Related Topic - Array/Divide and Conquer/Dynamic Programming 저는 Dynamic Programming 동적 프로그래밍을 사용하여 이 문제를 풀었습니다. 다이내믹 프로그래밍 알고리즘이란? 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘입니다. 이 문제에 동적 프로그래밍 알고리즘을 적용한다면 배열을 한 번만 확인하면서 현재 값과 현재 값+ 이전 값.. 2021. 12. 25. [프로그래머스] 구멍보트 문제풀이(파이썬/python/그리디/greedy) 문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요... 2021. 12. 23. [프로그래머스] 네트워크 (BFS/너비우선탐색/python/파이썬) 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers .. 2021. 12. 21. [프로그래머스] 단어 변환 ( DFS/깊이우선탐색/파이썬/Python) [프로그래머스] 단어 변환 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot", "dot", "dog", "lot", "log", "cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정.. 2021. 12. 20. [프로그래머스] 큰 수 만들기 (Python/그리디/Greedy) 문제 : 프로그래머스 큰 수 만들기 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24]를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. number k return "1924" 2 "94" .. 2021. 12. 16. [백준] DFS와 BFS ( Python/ 파이썬/그래프 탐색) 백준 1260번 DFS와 BFS 문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방.. 2021. 12. 15. [LeetCode] Largest Number (Python/파이썬/Bubble Sorting/버블 정렬) Given a list of non-negative integers nums, arrange them such that they form the largest number. Note: The result may be very large, so you need to return a string instead of an integer. 음이 아닌 정수 리스트 nums이 주어지면 가장 큰 수를 구성하도록 정렬하세요. 참고: 결과가 매우 클 수 있으므로 정수 대신 문자열을 반환해야 합니다. Example 1: Input: nums = [10,2] Output: "210" Example 2: Input: nums = [3,30,34,5,9] Output: "9534330" Example 3: Input: nums.. 2021. 12. 14. [프로그래머스] 베스트앨범(파이썬/python/해시) 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 제한사항 genres [i]는 고유번호가 i인 노래의 장르입니다. plays [i]는 고유번호가 i인 노래가 재생된 횟수.. 2021. 12. 13. [프로그래머스] 로또의 최고 순위와 최저 순위 (Python) def count_rank_matching(count): if count == 6: rank = 1 elif count == 5: rank = 2 elif count == 4: rank = 3 elif count == 3: rank = 4 elif count == 2: rank = 5 else: rank = 6 return rank def solution(lottos, win_nums): answer = [] zero = 0 for num in lottos: if num == 0: zero+=1 count = len(list(set(win_nums).intersection(lottos))) min_count = count max_count = count+ zero answer=[count_rank_mat.. 2021. 12. 12. 이전 1 2 다음 728x90 반응형
