문제 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 특정 금액 K가 주어질 때, 동전으로 변환할 경우 최소한의 동전으로 나타내는 동전의 수를 반환하는 문제이다. 이를 해결하기 위해서는 동전 중 금액이 가장 큰 동전부터 순회하며, 현재 금액인 K보다 작다면 `divmod`를 활용하여 몫은 동전의 수, 나머지는 잔돈이 되므로 이를 갱신하며 반복하면 된다. 코드 from sys import stdin if __name__ == '__main..
문제 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 회의가 끝나는 시간이 짧은 순서대로 정렬한 후에, 회의가 시작하는 시간이 짧은 순서대로 정렬하여, 회의를 할 수 있는지 하나씩 확인하는 방식으로 문제를 풀 수 있다. 처음에 문제를 풀 때는, 단순히 끝나는 시간이 가장 짧은 것만 파악하여 처리하면 된다고 생각하고 제출하였는데.. 90% 이상쯤에서 틀렸습니다. 를 만나게 되었다. 가만히 생각해보니, 가장 짧은 시간과 함께 시작 시간도 고려야 해야 되는 것이 빠졌다는 것을 알고 정렬을 `x: (x[1], x[0])` 과 같이 하니 맞았습니다!! 를 볼 수 있었다. 코드 from sys import stdin if __..
문제 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr 문제 풀이 모든 음식의 스코빌 지수를 K 이상으로 만들 고자 하는데 최소 몇 번 음식을 섞어야 하는지 반환하는 문제이다. 이 문제를 풀기 위해서는 `heapq`를 사용하면 쉽게 해결할 수 있다. `heapq`는 루트 노드가 가장 작은 값을 가지게 되기 때문이다. 따라서 `heapq`를 이용해 가장 작은 값 2개를 가져온 후 문제의 조건에 맞게 음식을 섞은 후 다시 `heapq`에 삽입한다. 이 과정에서 `heapq`는 heap의 성질을 따르..
문제 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린�� programmers.co.kr 문제 풀이 중요도가 가장 높은 문서부터 인쇄될 수 있도록 하여, 내가 요청한 문서는 몇 번째에 인쇄가 되는지 반환하는 문제이다. 이를 찾기 위해 인자로 주어진 위치(location)를 변경하고 중요도가 낮을 경우 큐를 활용해 뒤로 보내는 방식을 사용하면 된다. 이를 통해 내가 출력하고자 하는 문서가 언제 출력되는지 판단할 수 있다. 예를 들어 예제 #1의 경우, [2, 1, 3, 2]이고 출력하고자 하는 문서 2는 가장 먼저 출력된다. 이는 출력 대기열의 ..
문제 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제 풀이 무인도에 갇힌 사람들을 구명보트를 이용하여 탈출시키고자 할 때, 최소한의 구명보트를 구하는 문제이다. 문제의 제한 조건으로는 보트에는 최대 2명만 탑승할 수 있으며, 탑승할 수 있는 무게 제한이 있다. 따라서 사람들의 무게를 오름차순으로 정렬 후에, 큐나 이분 탐색을 통해 문제를 풀면 쉽게 해결할 수 있다. 큐를 이용한 풀이 people을 정렬 후, `deque`로 변환한다. list를 사용하면 `list.pop(0)`..
문제 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 문제 풀이 초 단위로 기록된 주식 가격이 떨어지지 않는 기간을 반환하는 문제이다. 이를 위해 prices에서 첫 번째 값부터 시작하여, 다른 값과 비교하였을 때 어느 시점에서 가격이 하락하는지를 파악하면 된다. 문제 풀이를 위해 큐를 사용하여도 되고, 단순히 반복문을 통해 문제를 해결할 수도 있다. 입력되는 주식가격을 `deque`로 변환한다. 첫 번째 값을 가져와, 주식 가격들과 비교하며 언제까지 상승하는지 카운트..
문제 코딩테스트 연습 - 스킬트리 programmers.co.kr 문제 풀이 스킬을 배워야 하는 순서가 주어지고, 스킬을 배운 목록이 주어질 때 해당 스킬 트리가 스킬을 배우는 순서에 맞게 배웠는지 확인하는 문제이다. 문제를 풀기 위해, 스킬 트리에서 순서에 영향을 미치는 스킬들만 추려낸 후 배워야 하는 순서와 일치하는지 확인하면 문제를 쉽게 할 수 있다. 코드 def solution(skill, skill_trees): answer = 0 for skill_tree in skill_trees: cur_tree = [s for s in skill_tree if s in skill] for idx in range(len(cur_tree)): if cur_tree[idx] != skill[idx]: brea..
문제 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이�� programmers.co.kr 문제 풀이 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해준 순으로 건너려고 할 때, 다리에 올라갈 수 있는 무게 제한이 있다. 트럭은 1초에 다리 한 칸을 지나갈 때, 모든 트럭이 다리를 건너는데 걸리는 시간을 구하는 문제이다. 문제를 풀기 위해서는 다음과 같은 로직을 작성하면 된다. q에 초기 값을 0으로 다리 길이만큼 채운다. 다리에 올라갈 수 있는 트럭을 파악하기 위해, 현재 다리의 무게를 계산한다. 첫 트럭부터 다리 위에 ..
