알고리즘
-
Merge / Quick / Heap Sort (Medium)알고리즘/Sort 2021. 1. 5. 16:22
출처(위키피디아/GeeksforGeeks) 1. Merge Sort(병합 정렬) - 분할 정복 알고리즘. - 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (원소가 하나인 리스트는 정렬된 것과 같으므로) - 부분 리스트가 하나만 남을때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. - 마지막 남은 부분리스트가 정렬된 리스트이다. - Stable / Not in place 최악 시간복잡도 Θ( n log n ) 최선 시간복잡도 Θ( n log n ) 평균 시간복잡도 Θ( n log n ) 공간 복잡도 Θ( n ) void merge(int arr[], int l, int m, int r){ int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n..
-
Selection / Bubble / Insertion Sort (Easy)알고리즘/Sort 2021. 1. 4. 23:19
출처(위키피디아/GeeksforGeeks) 1. Selection Sort(선택 정렬) - 주어진 리스중에 최소값을 찾는다. - 그 값은 맨 앞에 위치한 값과 교체한다. - 맨 처음을 제외한 나머지 리스트를 같은 방법으로 교체한다. - Unstable / In-place 최악 시간복잡도 Θ( n ^2 ) 최선 시간복잡도 Θ( n ^2 ) 평균 시간복잡도 Θ( n ^2 ) 공간 복잡도 Θ( 1 ) void selectionSort(int arr[], int n){ int i, j, indexMin, temp; for(i=0; i
-
LeetCode_931. Minimum Falling Path Sum알고리즘/Leetcode 2020. 12. 22. 00:22
leetcode.com/problems/minimum-falling-path-sum/ Minimum Falling Path Sum - 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 Solution1. 최종 목적지에서부터 역으로 최소가 되는 값을 찾아 table(r,c)에 기록하는 방법으로 접근 (지금 생각 하니 최초 출발지에서 시작 하든 동일하네...;;) row = 2 : (2,0)에서의 최소값은 7, (2,2)에서의 최소값은 8, (2,2)에서의 최소값은 9..
-
LeetCode_96. Unique Binary Search Trees알고리즘/Leetcode 2020. 12. 21. 23:54
leetcode.com/problems/unique-binary-search-trees/ Unique Binary Search Trees - 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 Solution1. Input N에 대해서 1~N에 대해서 루트일 경우는, root node가 1일 경우 : [왼쪽 자식] null F(0), [오른쪽 자식] N-1 case --> F(N-1) root node가 2일 경우 : [왼쪽 자식] F(1), [오른쪽 자식] N-2 ..
-
LeetCode_64. Minimum Path Sum알고리즘/Leetcode 2020. 12. 21. 22:23
leetcode.com/problems/minimum-path-sum/ Minimum Path Sum - 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 Solution1. M x N 사이즈의 table을 이용( all zero), (r,c) 칸으로 이동할수 있는 경우는 바로 위에칸(r-1,c)에서 아래로 이동하거나 왼쪽 칸(r,c-1)에서 오른쪽으로이동하는 경우만 존재 함, 따라서 (r,c)까지 이동 가능한 경우에서 최소값을 선택 table[r][c] = min..
-
LeetCode_63. Unique Paths II알고리즘/Leetcode 2020. 12. 21. 22:11
leetcode.com/problems/unique-paths-ii/ Unique Paths II - 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 Solution1. 2020/12/21 - [알고리즘/Leetcode] - LeetCode_62. Unique Paths 에서 장애물이 추가된 문제 이전과 동일하게 M x N 사이즈의 table을 이용하고 (r,c) 칸으로 이동할수 있는 경우는 아래와 같이 표현 가능하다. table[r][c] = table[r-1]..
-
LeetCode_62. Unique Paths알고리즘/Leetcode 2020. 12. 21. 22:03
leetcode.com/problems/unique-paths/ Unique Paths - 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 Solution1. M x N 사이즈의 table을 이용, (r,c) 칸으로 이동할수 있는 경우는 바로 위에칸(r-1,c)에서 아래로 이동하거나 왼쪽 칸(r,c-1)에서 오른쪽으로이동하는 경우만 존재 함, 따라서 (r,c)까지 이동 할수 있는 경우의 수는 아래와 같이 표현 가능하다. table[r][c] = table[r-1]..
-
LeetCode_486. Predict the Winner알고리즘/Leetcode 2020. 12. 18. 13:45
leetcode.com/problems/predict-the-winner/ Predict the Winner - 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 Solution1. 2차원 배열을 이용하여 [start, end] 구간에서의 점수 차를 저장 즉, DP[start][end] >= 0 : win 을 의미하고 DP[start][end] < 0 : Lose 를 의미 if start == end : dp[start][end] = nums[start] else ..