CEO

문제 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 풀이 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하여야 한다. 이때 최소 몇 대의 카메라를 설치해야 하는지 반환하는 문제이다. 처음에 문제를 접하였을 때는 카메라를 만났는지 모든 구간을 확인하며 문제를 풀고자 하였다. 정답은 맞았지만 다른 사람들이 푼 코드를 보니 더 짧고, 빠르게 풀 수 있는 방법이 있었다.😂 설치된 카메라를 진입 지점으로 갱신해 가며, 진입 지점이 설치된 카메라의 위치보다 작다면 카메라를 추가하고 위치를 갱신하면 `O(N)`의 시간으로 문제를 해결할 수 있다. 코드 from mat..

문제 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 문제 풀이 하드 디스크의 요청된 작업을 작업이 종료되는 시간이 빠른 순으로 처리하도록 하여 평균 처리 시간을 반환하는 문제이다. 요청된 작업 순으로 정렬 후에 처리할 작업을 하나씩 `pop`하여 `heap`을 통해 처리 시간이 가장 큰 작업부터 루트가 되도록 유지한다. 이와 같은 과정을 통해, 문제에 요구하는 것과 같이 작업을 처리할 수 있다. 코드 import heapq from collections import deque RQEUST = 0 d..

문제 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 풀이 집에서 학교까지 가는 길은 MxN 일 때, 폭우로 인해 갈 수 없는 길이 있다. 이때, 등교를 할 수 있는 경우의 수를 반환하는 문제이다. 문제는 x, y에 따른 2차원 배열을 생성하여 방문하는 경로를 기록하는 방식으로 풀 수 있다. 기존의 그래프에서 위의 그림과 같이 0을 추가한 DP 배열을 초기화한다. 그리고 처음 출발점인 집을 1로 초기화한 후 점화식인 `dp[x][y] = dp[x - 1][y] + dp[x][y - 1]`을 각..

문제 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 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..