본문 바로가기

2. 알고리즘 공부

 (10)
[Leetcode] 221. Maximal Square https://leetcode.com/problems/maximal-square/ Maximal Square - 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 1. Problem Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. 2. Algorithm class Solution { public int maxi..
[LeetCode] 923. 3Sum With Multiplicity https://leetcode.com/problems/3sum-with-multiplicity/ 3Sum With Multiplicity - 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 1. Problem Given an integer array A, and an integer target, return the number of tuples i, j, k such that i < j < k and A[i] + A[j] + A[k] == target. As th..
4. Kruskal Algorithm (크루스칼 알고리즘) : MST 찾기 public class Kruskal { static class Edge { int u, v; double weight; Edge(int u, int v, double weight) { this.u = u; this.v = v; this.weight = weight; } } static void findMST(int n, List edges, List MSTEdges) { //Step 1. 간선들을 가중치에 따라 오름차 순으로 정렬 Collections.sort(edges, (a, b) -> a.weight < b.weight ? -1 : 1); //Step 2. disjoint set 선언 + rank배열은 0으로, 부모 배열을 자기 자신으로 초기화 //rank 배열은 랭크값이 작은 트리를 랭크값이 큰..
3. Radix Sort (기수 정렬) public class RadixSort { static void radixSort(int nums[]) { int maxLen = getMaxLen(nums); List cnt[]; for(int radix = 0; radix
2. Quick Sort(퀵정렬) public class QuickSort { static void quickSort(int [] nums, int s, int e) { int index = partition(nums, s, e); if (s index) quickSort(nums, index, e); } static int partition(int [] nums, int s, int e) { int pivot = nums[(s+e)/2]; while(s pivot) e--; if (s
1. Merge Sort(병합정렬) public class MergeSort { public static void mergeSort(int nums[], int helper[], int s, int e) { if (s < e) { int m = (s+e)/2; mergeSort(nums, helper, s, m); mergeSort(nums, helper, m+1, e); merge(nums, helper, s, m, e); } } public static void merge(int nums[], int helper[], int s, int m, int e) { for (int i = s; i
[Leetcode] 82. Remove Duplicates from Sorted List II https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ Loading... 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 1. Problem Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Input: 1->2->3->3->4->4-..
[Leetcode] 300. Longest Increasing Subsequence https://leetcode.com/problems/longest-increasing-subsequence/ 불러오는 중입니다... 1. Problem Given an unsorted array of integers, find the length of longest increasing subsequence. 2. Algorithm I used dp solution with time complexity O(n^2). Step 1. Iterate index i 0 to length of array. -> O(n) Step 2. With index j find the longest length before d[i] iteratively, where nums[i] > nums[j]. -> O(n) Step 3..

티스토리툴바