1. 문제 각 층마다 w개의 방으로 구성되고 전체 층은 h개로 구성된 호텔이 있다 사람들은 오전 11시에 체크아웃을 하고 오후 2시에 체크인을 한다 각 예약마다 k개의 연속된 방을 사람들이 체크인 날짜와 체크아웃 날짜에 맞춰서 예약을 한다 이 때 방을 나눠주는 규칙은 반드시 k개의 연속된 방으로 최대한 낮은 층, 최대한 낮은 번호의 방을 줘야한다. 주어지는 예약 리스트에서 예약을 받으면 1, 예약을 거절하면 0으로 하는 리스트를 출력해라 2. 나의 풀이 w개의 방과 h개의 층으로 구성된 호텔을 리스트로 구성함 def solution(w,h,reserves): hotel = [[0 for range(w)] for range(h)] 예를 들어 5개의 방에 2층으로 구성된 호텔을 생각해보고 k / 체크인/ 체..
1. 문제 화폐가 1원, 5원, 10원, 50원, 100원, 500원으로 6종류가 있다. 목표하는 생산 금액 money가 주어지고 주어진 화폐 6종류의 생산 단가가 배열로 costs로 주어진다. money만큼 화폐를 생산하는데 최소비용을 return하는 알고리즘을 작성한다면? 2. 내가 생각한 풀이 목표로 하는 금액 money를 target이라는 새로운 변수에 복사하고 money_list를 500부터 1원까지 거꾸로해서 리스트로 만든다 money_dict로 금액을 key로 해당 금액의 생산단가를 value로 하는 사전을 만든다 prod_list는 각 화폐를 몇개 생산해야하는지 나타낸 변수 def solution(money, costs): from collections import deque answer ..
서로소 집합 알고리즘(disjoint set) 그래프 내에서 여러개의 node가 존재할 때 2개의 node를 선택해서 이 node가 서로 같은 node에 속하는지 판별하는 알고리즘 예를 들어 다음과 같이 8개의 node가 존재한다면 이런 경우는 부모 node가 자기 자신인 경우이다 이제 1과 2가 연결되었다고 생각해보자 이런 경우 2의 부모 node는 1이 된다 이렇게 합쳐나가는 과정을 union알고리즘이라고 부른다 이번엔 2와 3도 연결되었다고 가정해본다면 그러면 3의 부모 node는 2가 되는데 3과 1이 연결되었다는 것은 어떻게 아는가? 3의 부모 node는 2이고 2의 부모 node는 1이라서 부모 node만 보고서는 판단할 수가 없다 그렇지만 재귀함수를 사용하면 3의 부모 node가 2를 가리키..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수=가장 맵지 않은 음식의 스코빌 지수+(두 번째로 맵지 않은 음식의 스코빌..
최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리 트리는 root node에서 밑으로 가지를 뻗어나가는 형태의 자료구조로 binary tree인 이진 트리는 최대 2개까지만 자식 노드를 가진다 최소힙은 부모 node가 자식 node보다 항상 작은 binary tree 최대힙은 부모 node가 자식 node보다 항상 큰 binary tree heap은 배열로 구현되며 파이썬에서는 list로 만들어진다 import heapq를 통해 파이썬에서 heapq 관련 함수 사용가능 기존 리스트를 heapq로 만들려면 heapify()를 이용 heap2 = [50,10,20] heapq.heapify(heap2) print(heap2) [10,50,20] 혹은 빈 리스트를 생생한 후에 heappush..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return하도록 solution ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
