본문 바로가기

전체 글95

프로그래머스 - 소수 찾기(완전 탐색) 문제 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 풀이 문자열로 만들 수 있는 숫자를 완전탐색을 활용해서 다 구한 다음 그 숫자가 소수가 가능한지 판단해야 하는 문제라고 생각하고 접근을 했다. 즉, 문자열을 완전탐색해서 가능한 숫자를 다 구해주는 함수 + 소수인지 판단하는 로직, 이 두가지가 필요하다고 생각했다. 📌 소수를 판단하는 로직 def isPrime(n): if n==1 or n==0: return False for i in range(2,int(.. 2023. 1. 15.
프로그래머스 - 모음사전(완전탐색)(파이썬) 문제 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요. 제한사항 word의 길이는 1 이상 5 이하입니다. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다. 풀이 완전탐색으로 알파벳 하나하나를 다 탐색하면서 result라는 배열에 넣어서 모든 경우의 수를 다 탐색했고, 그 result 배열에서 주어진 해당 word의 인덱스 값을 구하려고 했다... 2023. 1. 14.
프로그래머스 - 피로도(완전탐색)(파이썬) 문제 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다. 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최.. 2023. 1. 12.
동적 계획법과 Knapsack 문제 🗯️ knapsack 문제 가능한 조합의 최적의 경우를 찾는 문제입니다. 배낭이 주어지고 담을 수 있는 것들의 무게와 최대가치가 주어졌을때 주어진 무게를 넘지 않으면서 최대의 가치를 담을 수 있도록 해결하는 문제를 말합니다. 🔎 DP로 풀어가면 쉽게 해결할 수 있는 문제로, DP문제의 대표적인 유형입니다. 아래의 간단한 대표 문제로 살펴보면 (문제) 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4,5,10,11,13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 .. 2022. 12. 29.
LIS(Longest Increasing Subsequence) 알고리즘 알고리즘 개념 정리 LIS(최장 증가 부분 수열) 🗯️ LIS(최장 증가 부분 수열)이란? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇개의 수를 제거한다고 해서 부분 수열을 만든다고 했을때, 오름차순으로 이루어진 부분 수열 중에서 가장 긴 부분 수열을 구하는 알고리즘을 말합니다. 3 5 7 9 2 1 4 8로 이루어진 수열이 있다고 하면, LIS는 3 5 7 9가 됩니다. 🔎 DP(동적계획법)으로 풀 수 있는 문제이고, DP와 관련된 알고리즘 문제로 자주 등장하는 유형입니다. import sys input=sys.stdin.readline N=int(input()) arr=list(map(int,input().split())) arr.insert(0,0) ls=[0]*(N+1) ls[1]=1 for .. 2022. 12. 28.