Hello Ocean! 🌼

Spanning Tree(신장 트리) ? 개념 그래프 내의 모든 노드을 포함하는 트리 모든 노드를 사이클 없이 연결하는 간선들을 모아놓은 트리 그래프의 최소 연결 부분 그래프 최소 연결 = 최소의 간선 n개의 노드를 n-1개의 간선으로 연결 특징 DFS, BFS를 이용해서 찾을 수 있다. 탐색 도중에 이용된 간선 모으기 하나의 그래프 -> 여러개의 spanning tree 사이클 X MST(Minimum Spanning Tree) ? 개념 Spanning Tree중에 간선의 가중치 합이 최소인 트리 단순히 가장 가중치가 작은 간선을 이용한다고 해서 최소 비용이 얻어지는 것은 아님 특징 간선의 가중치의 합이 최소 n개의 노드을 가지는 그래프, n-1개의 간선만 이용 사이클 X 구현 방법 1. Kruskal..

문제 설명 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 이하인 자연수입니다. ..

문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. cloth..

문제 설명n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.제한사항입국심사를 기다리는..

문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion return [leo, kiki, ..

최대 최소 찾기 토너먼트 트리 선택트리(Selection tree) 라고도 하며, 이를 이용하면 여러개의 정렬된 묶음들(run) 중에서 가장 작은 값을 찾거나, 가장 큰 값을 찾을 때 이를 이용하면 비교횟수를 줄일 수 있다. 예를들어, 서울 경기 강원 충청 등등에서 각 지역마다 가장 키 큰 사람 100명씩을 뽑은 뒤에 그 들 중에서 가장 키가 큰사람을 순서대로 뽑고 싶을 때 토너먼트 트리를 이용할 수 있다. 토너먼트 트리에는 루트에 더 큰값을 올리느냐, 작은 값을 올리느냐에 따라 승자트리와 패자트리 두 종류가 있다. 승자 트리 (Winner Tree) 부모노드가 두 개의 자식노드보다 더 작은 값을 나타내는 완전 이진트리이다. 따라서 루트노드는 트리에서 가장 작은 원소이다. 오름차순으로 정리된 k개의 ru..