본문 바로가기

코딩테스트

 (55)
[Python] 백준 1753번. 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제설명: 정점의 개수 V와 간선의 개수 E가 주어지고 시작 정점의 번호 K가 주어졌을 때 i번째 줄에서 i번 정점으로의 최단 경로의 경로값을 출력한다. 이 문제는 시작점이 K가 주어졌기 때문에 다익스트라 알고리즘으로 풀어본다. graph을 생성하자 여기에는 3개의 숫자 a,b,c 가 받아질때 graph[a].append((점, 간선))으로 받으려고 한다. I..
[Python][LeetCode] Intersection of Two Arrays(두 배열의 교집합) https://leetcode.com/problems/intersection-of-two-arrays/description/ Intersection of Two Arrays - LeetCode Can you solve this real interview question? Intersection of Two Arrays - Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order. Example 1: In leetcode.com 문제 설명: 두 배열이 주어졌을때 교집합을..
[Python][LeetCode] Search in Rotated Sorted Array(회전 정렬된 배열 검색) https://leetcode.com/problems/search-in-rotated-sorted-array/description/ Search in Rotated Sorted Array - LeetCode Can you solve this real interview question? Search in Rotated Sorted Array - There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 nums[right]: left = mid+1 el..
[Python][LeetCode] 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에 해당하는 인덱스를 구..
[Python][LeetCode] Two Sum II (두 수의 합) https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/ Two Sum II - Input Array Is Sorted - LeetCode Can you solve this real interview question? Two Sum II - Input Array Is Sorted - Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two n leetcode.com 문제 설명:..
[Python][LeetCode] Search a 2D Matrix II(2D 매트릭스 검색) https://leetcode.com/problems/search-a-2d-matrix-ii/description/ Search a 2D Matrix II - LeetCode Can you solve this real interview question? Search a 2D Matrix II - Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties: * Integers in each row are sorted in ascending fr leetcode.com 문제 설명: 행렬이 주어졌을때 target의 값을 구하..
[Python] 백준 2512. 예산 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 설명: 국가예산이 주어졌을때 지방예산요청의 합이 국가예산보다 큰 경우 상한액을 설정 그 합이 가능한 국가예산을 벗어나지 않고 최대가 되도록 구하는 문제 만약 국가예산이 485이고 지방예산요청이 120 110 140 150 일 때 합이 485를 넘어가게 된다. 그럼 상한액을 설정해서 상한액이 127이 될때 120 110 127 127이 되어 합이 484로 예산의 최대액이 된다. start..
[Python] 백준 2805. 나무자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 설명: 상근이가 얻으려는 나무의 길이 M , 나무의 수 N M을 얻기 위해 절단기로 자를 수 있느 나무의 최대 높이값을 구하는 문제 만약 4개의 나무 [20, 15, 10, 17]이 주어질때 7미터 얻으려고 할때 15미터로 설정하고 자르면 [0,0,5,2] 7미터를 얻을 수 있다. 이진탐색으로 풀 수 있지만 조금 방법을 바꿔보고 싶었다. 나무의 리스트를..

티스토리툴바