본문 바로가기

binarysearch9

[Leetcode] 668. Kth Smallest Number in Multiplication Table 문제 : https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ m x n 크기의 2차원 배열(1-indexed)이 있다. 배열 값은 각 요소들의 행, 열 인덱스의 곱이다. m, n, k가 주어졌을 때, m x n 2차원 배열에서 k 번째로 작은 요소 값을 구해라. k 번째로 작은 요소 값은 완탐을 하지 않는 이상 구하기 어렵기 때문에, 정수 x 보다 작은 요소 값들이 몇 개인지 구해보자. m = 3, n = 3, k = 4을 예로 들어보자. 1 2 3 2 4 6 3 6 9 1 2 2 3 3 4 6 6 9 구하고자 하는 문제를 좀 더 분해해서 각 행에서 정수 x 보다 작은 요소 값들이 몇 개(let, cnt)인지를 먼저 구해보.. 2021. 11. 16.
[Leetcode] 34. Find First and Last Position of Element in Sorted Array 문제 : https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ 내림차순 정렬된 정수 배열과 target 값이 주어지면 배열에서 target 값의 시작 위치와 끝 위치를 찾아라. 만일 target을 찾을 수 없다면 [-1, -1]을 반환해라. O(log N) 복잡성을 가지는 알고리즘을 작성해라. logN 복잡성이라는거 보니 이분탐색으로 해야겠다. 이분탐색을 진행하면서 target 값을 찾는 경우 정답배열의 최소값, 최대값을 갱신한다. 그리고 시작 위치와 끝 위치를 찾아야 하므로 여기서 끝내지 않고 (left, m-1), (m+1, right) 로 이분탐색 2개를 다시 실행시킨다. (m = (left + r.. 2021. 11. 14.
[Programmers] 입국심사 문제 : https://programmers.co.kr/learn/courses/30/lessons/43238 문제 풀기전에 문제 분류를 봐버렸다.. 이분탐색 문제를 풀고싶었다기 보다는 레벨3 문제를 풀고싶었던건데 문제분류가 너무 잘보여버림. 이분탐색이란걸 알았으니 어떻게 이분탐색으로 해야하는지 분석해보자. 입국심사를 기다리는 사람은 최대 10억명. 한 명의 심사관이 걸리는 시간은 최대 10억분. 심사관의 수는 최대 10만. 이분탐색은 내부 조건이 정답이 가능한지 안한지를 판단할 수 있어야한다. 그럼 주어진 조건을 어떻게 정답이 되는지 안되는지 알 수 있을까. m분안에 모든 심사원이 최소 n명을 처리할 수 있다면 m분이 정답이 될 수 있다. 모든 심사원이 처리할 수 있는 시간 = 각 심사원들이 m분안에 .. 2021. 6. 10.
[leetcode][154] Find Minimum in Rotated Sorted Array II 문제 : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ 오름차순 정렬된 배열이 있을 때, 어떤 pivot으로 배열이 회전했다고 하자. ex) [0,1,2,3,4,5,6,7] -> [4,5,6,7,0,1,2,3] 회전된 배열이 주어질 때 가장 작은 수를 구하라. 배열안에 수는 중복될 수 있다. 33번 Search in Rotated Sorted Array 와 비슷하게 풀었다. 위 문제와 다른 점은 33번 문제는 회전된 배열에서 특정 수 target을 찾고 배열은 중복된 수가 없다. 왼쪽 오른쪽 배열 오름차순 오름차순 오름차순 (제일 작은수가 왼쪽에 위치) 오름차순 내림차순 제일 작은수가 오른쪽에 위치 내림차순 오름차순 제일 작.. 2020. 7. 26.
[leetcode][441] Arranging Coins 문제 : https://leetcode.com/problems/arranging-coins/ n 개의 동전이 있으면 이를 계단 모양으로 배열하려고 한다. i번째 계단에는 i개의 동전이 있어야 한다. n개의 동전으로 조건을 충족시키는 계단의 최대 행 수를 구하라. 1부터 1씩 증가시키면서 i번째 행의 계단을 만들 때 필요한 동전 수를 구해서 정답을 구할수도 있다. 이렇게 풀면 O(N)으로 문제를 해결할 수 있을 것이다. 더 빠른 방법을 알아보자. 계단은 등차 수열이니까 i개의 행을 가진 계단을 만들고자 할 때 등차수열의 합 공식( i * (i + 1) / 2 )을 이용하면 필요한 동전 수를 O(1)만에 구할 수 있다. 이를 이용해서 parametric search 방식으로 문제를 다시 생각해보자. i 행의.. 2020. 7. 2.
[leetcode][1044] Longest Duplicate Substring 문제 : https://leetcode.com/problems/longest-duplicate-substring/ 문자열 S가 주어지면 두 번 이상 발생하는 S의 모든 중복 된 하위 문자열들 중 가장 긴 문자열을 찾아라. binary search 로 정답이 가능한 하위 문자열 길이 범위를 줄여나간다. length를 문자열 길이의 하위 문자열이 문자열 S에 두 번 이상 발생하는지 확인할 때는 Rabin-Karp 알고리즘을 사용한다. 라빈 카프 알고리즘은 해시 기법을 사용한다. 문자열이 같은지 비교할 때 1차로 해시가 같은지 비교하고, 해시가 같을 때만 실제로 문자열이 같은지 비교한다. 자바에서 hashCode(), equals() 함수를 생각하면 이해하기 쉽다. 객체를 비교할 때 1차로 hashCode().. 2020. 6. 20.

티스토리툴바