알고리즘 문제/Leetcode283 [leetcode][430] Flatten a Multilevel Doubly Linked List 문제 : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/ doubly linked list 가 주어진다. 하나의 노드는 next, previous, child 포인터를 가지고 있다. 이를 prev, next만을 가진 linked list로 바꿔라. child와 next 포인터를 가지고 있다면 child 노드를 next 노드로 잇고 child 노드와 연결된 모든 노드들이 linked list로 만들어졌을 때 그 뒤에 next노드를 다시 이어나간다. dfs로 head 노드에서 child노드가 있다면 child 노드를 잇고 다음 next노드를 잇는 식으로 재귀함수를 만들어서 푼다. 이를 위해 최근 탐색했던 노드 포인터 before와.. 2020. 7. 10. [leetcode][15] 3Sum 문제 : https://leetcode.com/problems/3sum/ nums 배열이 주어졌을 때 3개의 수 a,b,c를 nums 배열에서 고를 때 a, b, c의 합이 0이 되는 조합의 수를 구해라. https://withhamit.tistory.com/408 [BOJ][2143] 두 배열의 합 문제 : https://www.acmicpc.net/problem/2143 투 포인터(Two-Pointer)를 이용하여 풀었습니다. 배열 당 모든 부배열을 만드는 시간 복잡도는 O(n2)인데 n의 크기가 (1 2020. 7. 8. [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. 이전 1 ··· 28 29 30 31 32 33 34 ··· 48 다음