잡동사니

Description 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. You must write an algorithm with O(log n) runtime complexity. 풀이 O(log n)에 맞춰 풀어야 하는 문제로, 배열이 정렬됐기 때문에 binary search를 이용하면 쉽게 풀리는 문제이다. 기본적인 binary search 구현을 하면 된다. - left = 0 (최소 index 값)..

카테고리 없음 2022. 5. 1. 03:17

솔직히 이거 문제 처음에 이해 못했다. 두 번째 입력되는 숫자 그대로 반환하면 값 그대로 나오기 때문이다. 알고보니 주어진 함수 자체에 bad 파라미터 값이 세팅되어 있지 않아 어쩔수 없이 코딩을 복잡하게 해야했다. Description You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also ..

카테고리 없음 2022. 5. 1. 03:17

Description Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. 풀이 O(log n)에 맞춰 풀어야 하는 문제로, 배열이 정렬됐기 때문에 binary search를 이용하면 쉽게 풀리는 문제이다. 타겟값이 없을 경우 들어가기 가장 적합한 곳의 인덱스를 반환해야 하는데, left와 right을 이리저리 옮겨다니면 최종적으로 멈추는..

카테고리 없음 2022. 5. 1. 03:17

Stable sort란 중복된 키를 순서대로 정렬하는 정렬 알고리즘을 지칭한다. 즉 같은 값 2개 이상이 리스트에 등장할 때, 기존 리스트에 있던 순서대로 중복된 키들이 정렬된다는 것을 의미한다. numbers = [9, 3, 12, 1, 6, 2, 2] ↓ numbers = [9, 3, 12, 1, 6, 2(첫번째), 2(두번째)] ↓ [1, 2(첫번째), 2(두번째), 3, 6, 9, 12] 위 예시를 살펴보면 이해가 쉽다. 이처럼 기존 리스트에서 중복된 값들에게 순서가 매겨졌는데, 그 순서대로 정렬이 됐을 때 이 알고리즘을 stable sort라고 부를 수 있다. ​ Stable sort의 중요성 Stable sort로 정렬하는 알고리즘들의 순서는 항상 똑같기에 같은 결과를 보장한다 숫자를 정렬할 ..

카테고리 없음 2022. 5. 1. 03:17

Description Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. 풀이 Acceptance 비율이 높은만큼 쉬운 문제이다. 리스트 안에 내용물을 하나씩 꺼내서 제곱값을 구한 후 반환시키면 되는 문제이다. 파이썬 특성 상 한 줄로도 끝낼 수 있는 간단한 문제다. 코드 class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: return sorted([num**2 for num in nums])

카테고리 없음 2022. 5. 1. 03:17

Description Given an array, rotate the array to the right by k steps, where k is non-negative. 풀이 먼저 in-place 알고리즘의 의미를 알아야 해당 문제를 풀 수 있다. (링크 추후 추가) k값을 기준으로 리스트 슬라이싱을 하면 쉽게 풀리는데, 이때 단순히 이것만 생각하고 코딩을 하면 문제가 발생한다. 리스트 길이 때문에 답이 [1]이 아닌 [1, 1]로 나오는 등의 경우를 볼 수 있는데, 이를 방지하기 위해 k만 사용하는 것이 아닌 len(nums)를 이용하면 정확한 길이까지 세팅할 수 있다. 마지막으로, 파이썬 고인물들의 스킬로 [:]를 사용하면 in-place로 알고리즘을 구현할 수 있다. ~나도 이제 고인물~ 대부분의 ..

카테고리 없음 2022. 5. 1. 03:17