Algorithm/Binary Search (47) 썸네일형 리스트형 (Python3) - 백준(BOJ) 1939 : 중량 제한 https://www.acmicpc.net/problem/1939dijkstra를 max heap으로 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화노드 개수 n, 간선 개수 m, 양방향 그래프 graph, 시작점 start와 도착점 end를 선언 후 적절히 입력 및 초기화해줍니다.📔 풀이과정어떤 경로에 최소 제한이 곧 이동 가능한 물품의 최대 하중이 됩니다. 따라서 max heap을 사용해 가장 큰 제한을 가진 노드들만 선택해 방문하도록 dijkstra를 구현해줍니다.1. 노드를 탐색할 변수 max_heap , 각 노드별 최대 하중 max_weight 배열을 선언 후 적절히 초기화합니다. 2. python에는 따로 max heap이 없으므로 원소를 저장할때 음수형태로 저장후 꺼내서 비교할 때 .. (Python3) - LeetCode (Medium) : 2054. Two Best Non-Overlapping Events https://leetcode.com/problems/two-best-non-overlapping-events/descriptiondp와 binary search 를 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화1. end_time에 대해 events를 오름차순으로 정렬합니다. 2. i번째 까지 event를 선택하거나 선택하지 않은 경우의 최댓값을 저장할 max_values_until_current_event를 선언 후 events길이만큼 저장해줍니다. 3. end_times를 따로 events에서 추출해 배열로 저장해줍니다.📔 풀이과정1. 이벤트 정렬: endTime 기준으로 정렬. 이렇게 하면 과거의 이벤트들 중 겹치지 않는 마지막 이벤트를 빠르게 찾을 수 있습니다.2. max_value.. (Python3) - LeetCode (Medium) : 1760. Minimum Limit of Balls in a Bag https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/이분 탐색 문제였습니다.📕 풀이방법📔 입력 및 초기화left, right를 선언해 각각 1, nums의 원소의 최댓값을 저장합니다.📔 풀이과정1. while left while left 이진 탐색에서 범위를 계속 좁혀가며 특정 값에 수렴할 때 사용하는 형태입니다. 반면, while left 정확히 값을 찾거나 특정 조건이 충족되는 순간 탐색을 종료하는 데 주로 사용됩니다.이 문제에서는 최적의 값을 찾기 위해 left와 right가 수렴하는 최종 지점까지 좁혀가야 합니다.left :예를 들어, mid = (left + right) // 2로 계산하고 범위를 조정할 때 left와 right의 .. (Python3) - 백준(BOJ) 1561 : 놀이 공원 https://www.acmicpc.net/problem/1561이분 탐색 문제였습니다.📕 풀이방법📔 입력 및 초기화탑승자 아이들의 수 child, 놀이기구 수 attractions, 각 놀이기구별 탐승시간 ride_times선언 후 입력 받습니다.📔 풀이과정무엇에 대해 이분탐색을 해야하는지 찾기가 쉽지 않았습니다. 처음 탑승할 아이의 수가 많기 때문에 그 숫자에 힌트를 얻어 아이에 대해 이분탐색을 진행했으나 각 놀이기구마다 탐승 가능한 아이의 수가 제각각 다르기 때문에 반대로 특정 시간(last_time)이 지났을 때 누적된 탑승자 수가 입력 받은 child값과 일치하는지 확인하는 방식으로 접근해야합니다. 1. 이분 탐색을 진행해줍니다. 1-1. left와 right변수를 설정해 시간을 이.. (C++, Rust) - LeetCode (easy) 222. Count Complete Tree Nodes https://leetcode.com/problems/fair-candy-swap/description/ Fair Candy Swap - LeetCode Can you solve this real interview question? Fair Candy Swap - Alice and Bob have a different total number of candies. You are given two integer arrays aliceSizes and bobSizes where aliceSizes[i] is the number of candies of the ith box of candy that Alice h leetcode.com 이분탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. alice 가 .. (C++) - LeetCode (easy) 744. Find Smallest Letter Greater Than Target https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/ Find Smallest Letter Greater Than Target - LeetCode Can you solve this real interview question? Find Smallest Letter Greater Than Target - You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters. Retu leetc.. (C++) - LeetCode (easy) 704. Binary Search https://leetcode.com/problems/binary-search/description/ Binary Search - LeetCode Can you solve this real interview question? Binary Search - Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. leetcode.com 이분탐색 문제였습니다. 📕 풀이방법 📔 풀이과정 target이상의 iterator를.. (C++) - LeetCode (easy) 455. Assign Cookies https://leetcode.com/problems/assign-cookies/description/ Assign Cookies - LeetCode Can you solve this real interview question? Assign Cookies - Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i], which is the minimum size o leetcode.com greedy 또는 이분탐색으로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화.. 이전 1 2 3 4 ··· 6 다음