두덕리온라인

C++ quick sort 퀵 정렬 void quickSort(vector& nums, int l, int r) { if (l >= r) return; int mid = partition(nums, l, r); quickSort(nums, l, mid); quickSort(nums, mid + 1, r); } int partition(vector& nums, int l, int r) { int pivot = nums[l]; while (l = pivot) r--; nums[l] = nums[r]; while (l < r && nums[l]

C++ merge sort 합병 정렬 알고리즘 void merge(vector& nums, int left, int middle, int right) { vector tmp (right - left +1);// 임시버퍼 int i = left;// 왼쪽에서 시작 int j = middle+1;// 가운데에서 시작 int k = 0; // 왼쪽과 가운데에서 시작하여 작거나 같으면 왼쪽으로 복사 while(i

C에서는 주로 atoi(), itoa()를 썼었는데 C++에서는 string을 사용해서 더욱 간단하게 변환할수 있다. // int를 string으로 변환, c에서는 itoa() int num = 100; string str = to_string(num); // "100" // string을 int로 변환, c에서는 atoi() string str = "1234"; int num = stoi(str); // 1234

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. Example 1: Input: nums = [7,2,5,10,8], m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the..

Java로 구현한 합병 정렬입니다. 배열을 반으로 나눠서 오른쪽이 왼쪽의 숫자보다 작으면 이동시키는 것을 반복합니다. class MergeSort { void mergesort(int[] array) { int[] helper = new int[array.length]; mergesort(array, helper, 0, array.length - 1); } void mergesort(int[] array, int[] helper, int low, int high) { if (low < high) { int middle = (low + high) / 2; mergesort(array, helper, low, middle); mergesort(array, helper, middle + 1, high); me..

최소값을 상수시간에 리턴하는 stack만들기. stack을 만들면서 간단히 해당 element의 상태일때 최소값을 기억해놨다가 리턴해주면 된다. Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the ..

쿠팡에서 설계 문제로 나온 LRU Cache. 핵심 포인트는 HashMap과 LinkedList를 동시에 유지하는 것. Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of..

쿠팡 문제로도 유명한 3SUM이다. Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Example 2: Input: nums = [] Output: [] Example 3: Input: nums = [0] Output: [] Const..