2차원 배열이 주어졌을때, 왼쪽위에서 오른쪽아래까지 가는 최소경로에 해당하는 vaule들을 모두 합하여 리턴하는 문제 역시 전형적인 점화식문제다 각 element를 기준으로 최소합을 구한다. 이 방식이 근본적인 Dynamic Programming 기법이다. 이때 i가0, j가 0인 경우는 각각 i-1, j-1이 없으므로 바로 이전 값을 더한것이 최소값이 된다.

Palindrome은 거꾸로 읽어도 똑같은 string이라고 한다. 예시를 보면 원소 한개는 palindrome이라고 생각하고, 그 외에 palindrome한 조합의 갯수를 찾는것으로 보인다. 전형적인 DP문제이다. s가 n개라고 할때, 0부터 n까지의 모든 케이스에 대해 palindrome이 있는지 찾으면 된다. 이 과정에서 시작위치를 left, 끝위치를 right로 두었다. 다섯글자로 구성된 s가 input으로 들어온다고 가정해보자. for문에서 검사하는 조합은 ( i , i )와 ( i , i+1) 이다. 따라서 검정색 동그라미로 표기된 조합은 Palindrome여부에 대한 검사가 가능하다. 그림에서 x로 표기된 조합은 검사할 필요가 없다. 시작위치가 끝위치보다 크기 때문이다. 문제는 for문에서 ..

0부터 input으로 들어오는 숫자까지의 자연수에 대해 각각을 이진수로 변경 후, 해당 결과의 1의 갯수를 세서 배열로 리턴하는 문제. 그냥 Loop를 돌면서 모두 2진수로 변환시킨후, 정규표현식을 이용해 1의 갯수를 찾아내 리턴하였다. 정규표현식을 쓰는 정도만 번거로울뿐 복잡하진 않았던 문제들.

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 climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 1칸 또는 2칸씩만 계단을 오를 수 있는 경우에 대해, 총 계단수가 주어졌을때 올라갈 수 있는 가짓수는 몇개인가? 딱 봐도 점화식 문제다. 경우의수[n] = 경우의수[n-1] + 경우의수[n-2](n>2)가 된다. 1칸 또는 2칸만 오를 수 있댔으니, 점화식의 관점에서는 1칸전 경우의수 + 2칸전 경우의수가 현재 계단을 오를 수 있는 경우의 수가 된다는 뜻. 간단한 문제였다

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가 날짜인 배열이 주어져 있을때 내가 어느 날짜에 사서 어느 날짜에 팔아야 최대 이익인..