알고리즘 문제408 [Leetcode] 240. Search a 2D Matrix II 문제 : https://leetcode.com/problems/search-a-2d-matrix-ii/ m x n 정수형 배열에서 target 이 존재하는지 유무를 반환하라. 배열은 각 행, 열에서 오름차순 정렬되어 있다. 가장 쉽게 생각할 수 있는건 각 행, 혹은 열마다 차례대로 이분탐색을 돌려서 target 값이 있는지 확인한다. 시간복잡도는 O(N logM) or O(M logN). 각 행, 열에서 오름차순 정렬되어 있다는 특징을 독립적으로 보지 않고 탐색조건에 같이 사용할 수 있을지 생각해보았다. 예제 1번의 배열모습이다. x = 1, y = 1 일 때, matrix[x][y]는 5이다. 이때 matrix[x~][y~] 배열을 한 번 보자. 각 행, 열들은 오름차순 정렬되어있으므로 항상 최상단좌측.. 2021. 11. 20. [Leetcode] 461. Hamming Distance 문제 : https://leetcode.com/problems/hamming-distance/ Hamming distance 는 두 정수의 서로 다른 비트의 개수이다. 두 개의 정수 x, y가 주어지면 이들의 Hamming distance를 구하라. 서로 다른 비트들을 구하기 위해 x, y를 XOR 연산을 한다. XOR = 입력값이 같으면 0, 다르면 1. 연산 후 2로 나눠가면서 2의 나머지가 1인 경우(탐색중인 자리의 비트가 1인 경우) 정답 + 1을 한다. 시간복잡도는 O(logN) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/461.%20Hamming%20Distance.cpp 2021. 11. 19. [Leetcode] 448. Find All Numbers Disappeared in an Array 문제 : https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ nums 배열 크기와 같은 크기의 나온 적 있는 숫자들을 확인하는 bool 형 배열을 하나 만들고 nums 배열을 탐색하며 존재 여부를 세팅한다. bool 형 배열을 다시 한 번 탐색하며 나온적 없는 숫자인 경우 정답 배열에 추가한다. 시간/공간 복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/448.%20Find%20All%20Numbers%20Disappeared%20in%20an%20Array.cpp 2021. 11. 18. [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] 80. Remove Duplicates from Sorted Array II 문제 : https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ 앞에서부터 탐색하면서 연속으로 등장하는 정수의 수를 저장한다. 만일 이전과 같은 정수인데 3개 이상 등장하는 수라면 해당 요소를 삭제한다. 리턴값은 삭제하고 난 뒤의 nums 배열의 사이즈를 반환한다. 시간복잡도는 O(N). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/80.%20Remove%20Duplicates%20from%20Sorted%20Array%20II.cpp 2021. 11. 15. [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. 이전 1 ··· 12 13 14 15 16 17 18 ··· 68 다음
