본문 바로가기

전체 글657

[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][63] Unique Paths II 문제 : https://leetcode.com/problems/unique-paths-ii/description/ 로봇이 M x N 그리드의 왼쪽 위 코너에 있다. 로봇은 아래나 오른쪽으로만 움직일 수 있다. 그리드에는 장애물들이 있다. 장애물이 있는 경우 해당 칸으로는 갈 수 없다. 로봇이 그리드의 오른쪽 아래 코너로 가려고 할때 경우의 수는 총 몇 가지인가. 2차원 배열을 만든다. d[i][j] = (i, j)에서 도착점까지 갈 수 있는 경우의 수. 위 배열을 채우면 되는데, 로봇이 이동할 수 있는 방향은 아래, 오른쪽이고 장애물은 이동할 수 없다는 것으로 점화식을 세울 수 있다. d[i][j] = d[i+1][j] + d[i][j+1] ((i, j)가 장애물이 아닌 경우) d[i][j] = 0 ((.. 2020. 6. 30.
[leetcode][96] Unique Binary Search Trees 문제 : https://leetcode.com/problems/unique-binary-search-trees/1..n 의 수로 만들어질 수 있는 BST의 수를 구하라.예시에서 보여주고 있는 n = 3일 때의 만들 수 있는 BST들을 노드 입력 순으로 나열해보자. 1. 1 2 3 2. 1 3 2 3. 2 1 3 (2 3 1) 4. 3 2 1 5. 3 1 2 3번을 보면 [2, 1, 3] 과 [2, 3, 1]의 BST 결과가 같다는 것을 알 수 있다.BST는 루트노드보다 작은 노드들은 루트노드의 왼쪽 서브트리로 가고, 루트노드보다 큰 노드들은 루트노드의 오른쪽 서브트리로 간다.그러므로 2 다음에 1이나올지 3이 나올지는 중요하지 않다는 것이다. 1은 반드시 2의 왼쪽 서브트리로 갈 것이고, 3은 반드시 2.. 2020. 6. 24.
[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.
문자열 해싱(String Hashing) 해싱 알고리즘은 다양한 문제들을 해결하는데 도움을 준다. 문자열을 효과적으로 비교해야 하는 문제들이 있다. 각 문자들을 비교해서 브루트 포스(brute force) 방법으로 문자열(s1, s2)을 비교하는 경우 시간복잡도는 O(min(|s1|, |s2|))가 된다. 더 효과적으로 비교하는 방법의 아이디어는 문자열을 정수형으로 바꾸는 것부터 시작한다. 문자열 대신 숫자를 비교하게 된다면 시간복잡도는 O(1)이 된다. 문자열의 해시(hash)라 불리는 정수를 얻기 위해 해시 함수(hash function)를 사용한다. 만약 두 문자열 "ss"와 "tt"가 같다면 그들의 해시 값도 같아야 한다. hash(문자열)을 문자열의 해시값이라고 한다면 hash("ss")와 hash("tt")가 같아야 한다. hash(.. 2020. 6. 20.
[leetcode][275] H-Index II 문제 : https://leetcode.com/problems/h-index-ii/오름차순으로 정렬된 양의 정수 배열이 주어진다고 하자. (let, 배열 크기 = N)이 배열은 논문들이고, 각 배열 값은 i번째 논문이 몇 개의 논문을 인용했는지를 나타낸다. 즉, arr[2] = 3이라면 2번째 논문은 3개의 논문을 인용하여 작성되었음을 의미한다.N개의 논문중 h개의 논문이 h개 이상의 논문을 인용하고 N-h개는 h개 이하를 인용하는 경우 h-인덱스라고 한다.배열의 가능한 h-인덱스 값 중 최대값을 구해라.이분 탐색으로 풀어보자. 어쨌든 h의 범위는 논문의 개수이다.l, r 은 배열의 시작인덱스, 종료인덱스로 잡자.m = (l+r)/2이다.h = N - m라고 하고 h가 정답이 가능한지 판단한다.문제 초반.. 2020. 6. 18.

티스토리툴바