본문 바로가기

Star43

[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] 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] 587. Erect the Fence 문제 : https://leetcode.com/problems/erect-the-fence/ Erect the Fence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 볼록껍질 (Convex hull) 구하는 문제이다. 볼록껍질..! 5년 전쯤에 한 번 풀어보고 이후로 처음인거 같다. 나무들 중 반드시 정답에 포함될 수 있는 나무는 좌하단(가장 왼쪽에 있는 점들 중 가장 아래) 아니면 우상단(가장 오른쪽에 있는 점들 중 가장 위)에 있는 나무이다. 따라서 이.. 2021. 9. 4.
[leetcode] 1632. Rank Transform of a Matrix 문제 : https://leetcode.com/problems/rank-transform-of-a-matrix/ m x n 크기의 배열이 있을 때, 이들의 랭크를 매긴 배열을 반환하라. 순위는 1부터 시작하며 두 개의 요소 p, q가 같은 행 혹은 같은 열에 있으면 아래와 같은 규칙에 따라 순위를 매긴다. 1. p q : rank(p) > rank(q) 랭크는 가능한한 작게 매겨져야 한다. 예시 4를 보자. 7 3 6 1 4 5 9 8 2 만약 배열의 모든 수가 유니크한 수를 가진다면 정답을 구하기는 생각보다 간단하다. 요소 값을 기준으로 오름차순 정렬한다. 요소값(x, y) 1 (1,0) -> 2.. 2021. 8. 12.
[leetcode] 126. Word Ladder II 문제 : https://leetcode.com/problems/word-ladder-ii/ 문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환횟수 문자열 변경 리스트들을 구하라. beginWord는 wordList에 없어도 되지만 endWord는 wordList에 있어야만 변경 가능한다. ex) // input beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] // output [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog.. 2021. 7. 25.
[Programmers] 하노이의 탑 문제 : https://programmers.co.kr/learn/courses/30/lessons/12946 오랜만에 풀어보는 하노이의 탑. 재귀로 풀었다. A -> C로 N개의 원판을 옮긴다고 해보자. 가장 아래에 있는 원판을 제외한 N-1개의 원판은 커다란 덩어리로 보자. 먼저 N-1개의 원판을 하노이의탑 규칙에 어긋나지 않게 A -> B 위치로 옮긴다. 그 뒤, N 번째 원판을 A -> C로 옮긴다. 다시 N-1개의 원판을 N-2번째 원판과 그 외의 원판들로 보자. N-2 개의 원판들을 규칙에 어긋나지 않게 B -> A로 옮긴 후, N-1번째 원판을 B -> C로 옮긴다. 이를 반복하며 다시 N-2개의 원판들을 C로 옮긴다. // n개의 원판을 from -> to로 이동 fun hanoi(int .. 2021. 7. 6.

티스토리툴바