기능개발 (스택/큐)
- 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
- 제한사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
- 제한사항
제출한 코드 :
import math
def solution(progresses, speeds):
# 각 작업이 완료되는데 필요한 일수 계산
days = [math.ceil((100 - p) / s) for p, s in zip(progresses, speeds)]
# 배포 결과를 저장할 리스트
result = []
# 첫 번째 작업의 완료 일수
current_max_day = days[0]
count = 0
for day in days:
if day > current_max_day:
result.append(count)
current_max_day = day
count = 1
else:
count += 1
# 마지막 배포 그룹 추가
result.append(count)
return result프로세스 (스택/큐)
- 운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
- 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
- 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
- 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게
됩니다.
현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴
배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를
알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로
실행되는지 return 하도록 solution 함수를 작성해주세요.
- 제한사항
- priorities의 길이는 1 이상 100 이하입니다.
- priorities의 원소는 1 이상 9 이하의 정수입니다.
- priorities의 원소는 우선순위를 나타내며 숫자가 클 수록
우선순위가 높습니다. - location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
- priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이
표현합니다.
- priorities의 길이는 1 이상 100 이하입니다.
제출한 코드 :
from collections import deque
def solution(priorities, location):
# 프로세스와 초기 위치를 큐에 저장
queue = deque([(p, i) for i, p in enumerate(priorities)])
# 실행 순서 카운터
order = 0
while queue:
# 큐의 맨 앞에 있는 프로세스
current = queue.popleft()
# 큐에 남아있는 프로세스 중 우선순위가 더 높은 것이 있는지 확인
if any(current[0] < q[0] for q in queue):
# 현재 프로세스를 다시 큐의 끝에 넣음
queue.append(current)
else:
# 현재 프로세스를 실행
order += 1
# 현재 프로세스가 목표 프로세스인지 확인
if current[1] == location:
return order피로도 (완전탐색)
- XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
- 제한사항
- k는 1 이상 5,000 이하인 자연수입니다.
- dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하
입니다.
- dungeons의 가로(열) 길이는 2 입니다.
- dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모
피로도"] 입니다.
- "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나
같습니다.
- "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
- 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가
서로 같을 수 있습니다.
- 제한사항
제출한 코드 :
from itertools import permutations
def solution(k, dungeons):
max_dungeons = 0
n = len(dungeons)
for perm in permutations(dungeons):
current_fatigue = k
explored_dungeons = 0
for required, consume in perm:
if current_fatigue >= required:
current_fatigue -= consume
explored_dungeons += 1
else:
break
max_dungeons = max(max_dungeons, explored_dungeons)
return max_dungeons타겟 넘버 (깊이/너비 우선 탐색(DFS/BFS))
- n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
- 제한사항
- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
- 각 숫자는 1 이상 50 이하인 자연수입니다.
- 타겟 넘버는 1 이상 1000 이하인 자연수입니
- 제한사항
제출한 코드 :
def solution(numbers, target):
def dfs(index, current_sum):
# 기저 사례: 인덱스가 numbers의 길이와 같으면 현재 합이 타겟과 같은지 확인
if index == len(numbers):
return 1 if current_sum == target else 0
# 현재 숫자를 더하는 경우와 빼는 경우를 재귀 호출
add_case = dfs(index + 1, current_sum + numbers[index])
subtract_case = dfs(index + 1, current_sum - numbers[index])
# 두 경우의 수를 합산하여 반환
return add_case + subtract_case
# 재귀 호출 시작
return dfs(0, 0)k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT)
- 양의 정수
n이 주어집니다. 이 숫자를k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
0P0처럼 소수 양쪽에 0이 있는 경우P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우P처럼 소수 양쪽에 아무것도 없는 경우- 단,
P는 각 자릿수에 0을 포함하지 않는 소수입니다.
- 예를 들어, 101은P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서
찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이
있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌,
10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0
형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수
있습니다.
정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때,
변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return
하도록 solution 함수를 완성해 주세요.
- 제한사항
- 1 ≤ n ≤ 1,000,000
- 3 ≤ k ≤ 10
제출한 코드 :
def is_prime(num):
if num <= 1:
return False
if num == 2:
return True
if num % 2 == 0:
return False
sqrt_n = int(num ** 0.5) + 1
for divisor in range(3, sqrt_n, 2):
if num % divisor == 0:
return False
return True
def convert_to_base_k(n, k):
result = ''
while n > 0:
result = str(n % k) + result
n //= k
return result
def solution(n, k):
base_k_number = convert_to_base_k(n, k)
candidates = base_k_number.split('0')
count_primes = 0
for candidate in candidates:
if candidate and is_prime(int(candidate)):
count_primes += 1
return count_primes