집합이 Input으로 주어질 때, 모든 가능한 subset의 배열을 리턴하라.(이를 power set이라 부른다) 모든 케이스를 카운팅하므로 재귀가 필요하다 이 재귀는 조건에 따라 index를 1씩 증가시키며 필요한 만큼 Loop를 돈다 예컨데 [1,2,3] 배열이 input으로 들어오는 경우, 첫 Loop인 [ ] 에 대해서는 index 1,2,3의 케이스로 Loop를 돈다 각 index에 대해서는 해당 index보다 크고 3보다 작은 케이스만 Loop를 돌것이다.

배열이 주어지면 해당 원소들로 만들 수 있는 순열 케이스를 모두 구하는 문제 input이 아예 없거나 하나인 경우는 일단 걸러준다. 이후 Loop를 돌면서, 순회 차례가 된 원소를 제외하고 나머지를 recursion으로 넘겨준다. 이때 recursion의 결과인 res는 배열로 나올것이므로, 다시 순회하며 결과를 하나씩 만들어준다. 이렇게 하는 이유는, 나머지를 가지고 만든 순열의 경우의 수에 순회 차례가 된 원소만 concat으로 붙여주면 해당 배열로 만들 수 있는 모든 경우의 수가 되기 때문이다. 이러한 행위를 순회하면 모든 경우의 수를 구할 수 있다.

특정 string이 input으로 들어왔을 때, 최대한 하나의 part로 보이게끔 string을 나누면 몇개가 되느냐를 묻는 문제이다. 다시말해, 각 part에 포함된 각각의 string이 겹치지 않도록 part를 나누는 방법을 구하라는 뜻. 이때 리턴값은 각 part의 갯수로 구성된 배열이 된다. 이렇게 part에 대한 maximum을 찾는 문제는 greedy algorithm의 활용으로 귀결된다. greedy algorithm은 원소들을 순회하되, 각 순회 시점에서 global solution만을 고려하며 매 순회마다 비교하는 방식이다 따라서 한번의 순회로 도출된 global solution이 모든 경우에 대한 global solution인 경우에 적용될 수 있다. 위와 같은 문제도 이러한 유형에 해..

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. 배열과 target이라는 정수가 주어질 때, 배열의 원소 두개를 더해 target이 될 수 있다면, 몇번째 자리의 원소 두개를 더했는지 리턴하라는 문제. 아무래도 시간복잡도가 중요한 문제가 되겠다. 처음에는 target을 기준으로..

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. 배열이 주어졌을때 합이 최대가 되는 연속된 부분의 합이 얼마인지 리턴하라는 문제 이런 경우에는 보통 Kadane`s Algorithm을 사용한다 이 알고리즘의 핵심 로직은 원소들이 양수인지 여부를 가리는데 있다. 만약 배열의 모든 원소가 양수라면 더할수록 최댓값을 경신 할 것이고, 음수라면 최대한 더하지 않는 것이(즉, 음수 중 최댓값을 갖는 원소 한개만) 최댓값일 것이다 Kadane`s Algorithm의 기본원리는 이전까지의 부분합 중 최대를 알아내는 것이다 ..

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. 가격과 각 index가 날짜인 배열이 주어져 있을때 내가 어느 날짜에 사서 어느 날짜에 팔아야 최대 이익인..