Algorithm/꼭 기억해둘 유명 Algorithm

0-1 Knapsack Problem | Dynamic Programming

Problem n개의 아이템의 무게와 가치가 주어지고, 이 아이템들을 W 만큼의 용량을 가진 가방에 넣을 수 있는 최대치로 넣고자 한다. 좀 더 프로그래밍적으로 얘기하자면, 두 정수 배열 val[0, .. , n-1]와 wt[0, .. , n-1]는 각각 아이템의 가치와 무게를 나타내고, 주어진 정수 W는 가방의 용량을 나타낸다. 여기에서 부분집합의 총 무게가 W 보다 작거나 같은, val[]의 최대 부분 집합을 구하라. 아이템을 부술 수 없으며, 또한 하나의 온전한 아이템을 취하거나 취하지 않아야만 한다. (0-1 property) Example Recursion OR Exhaustive Search Solution Approach 간단한 해결책은 아이템들의 모든 부분집합의 무게와 가치를 확인하는 것이..

Ugly Numbers

Problem Ugly Numbers는 2, 3, 5로만 나누어 떨어지는 수이다. 11개 정도만 나열해보자면 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15가 된다. 참고로 맨 처음의 1은 편의상 들어가 있는 숫자이다. Ugly Numbers 문제에서는 숫자 n이 주어지며, n번째 Ugly Number를 리턴해야 한다. Example Input : n = 7 Output : 8 Input : n = 10 Output : 12 Input : n = 15 Output : 24 Input : n = 150 Output : 5832 Dynamic Programming Solution Ugly Number에서 1을 제외한 모든 수는 2, 3, 5로 나누어지기 때문에 다음과 같이 그룹을 3개로 나눌 ..

Longest Increasing Subsequence(LIS) | Dynamic Programming

Problem Longest Increasing Subsequence(LIS) 문제는 주어진 배열의 subsequence들 중에서 오름차순으로 정렬되었으며, 그 중에서도 길이가 가장 긴 subsequence를 찾아내는 문제이다. What is subsequence? 배열 {1, 2, 3}의 subsequence는 {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이다. 이 배열의 LIS를 굳이 따지자면, {1, 2, 3}이 된다. Example 위와 같은 배열이 주어졌을 때, LIS는 {10, 22, 33, 50, 60, 80}이 되고, 그 길이는 6이 된다. Input: arr[] = {3, 10, 2, 1, 20} Output: Length of LIS = 3 T..

Coin Change | Dynamic Programming

Problem 주어진 N이라는 값이 있다. 우리의 목적은 N cents에 대한 잔돈을 만드는 것이며, 우리는 각각 S={S1, S2, .. , Sm} 만큼의 가치를 가지는 동전들을 무한대로 공급할 수 있다. 잔돈을 만들기 위한 경우의 수는 몇인가? 여기서 동전들의 순서는 따지지 않기로 한다. Example 1) N = 4 and S = {1, 2, 3} 이 경우 4가지 해결책이 있다. {1,1,1,1}, {1,1,2}, {2,2}, {1,3} 2) N = 10 and S = {2, 5, 3, 6} 이 경우 5가지 해결책이 있다. {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5}, {5,5} Recursive Solution function count(S, m, n) { if (n ..

Sudoku | Backtracking

Approach 스도쿠의 칸 들 중에서 비어있는 칸들에 값을 하나씩 할당해보면서 해결하는 방식이다. 숫자를 할당하기 전에, 스도쿠의 규칙을 깨뜨리지 않는지 확인하는 로직이 필요하다. 그러기 위해서 같은 행이나 같은 열, 같은 3X3 subgrid에 넣으려는 숫자와 동일한 숫자가 있는지 없는지 판별해야만 한다. 넣으려는 숫자가 스도쿠 규칙을 깨지 않는다는 것이 확인된 이후에, 숫자를 할당하고 재귀적으로 해당 숫자가 해결책에 도달할 수 있는지 없는지 확인해야 한다. 만약 할당된 숫자가 해결책에 도달하지 못한다면, 그 다음 숫자를 현재의 빈 칸에 대해 다시 시도해본다. 이 작업을 1부터 9까지 다 시도해봤음에도 해결책을 찾아내지 못한다면, false 값을 리턴하고 해결책이 없음을 알린다. Algorithm 할..