Keep the Experience Natural, Easy, Light

#1 알고리즘#1-1 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘#1-1 정의동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com상향식 동적 프로그래밍 문제다. #1-2 구간 합 도출 방법캐싱을 위해 모든 range 예를 들어, 1..300, 40..70, 998..999, ...들을 전부 구하는 것은 사실상 불가능하다. 무수한 경우의 수가 있기에 저장 공간과 계산 시간 모두 안드로메다로 날아가 버린다. 대신, 1..1, 1..2, 1....

#1 알고리즘#1-1 직관화타일로 생각하면 머리가 아프다. 어떤 수 n을 1과 2만 사용한 덧셈식으로 표현했을 때, 나올 수 있는 가짓수로 생각하면 한결 명확해진다. 가령, 위 타일 조합을 1 + 1 + 2 + 1로 생각하는 것이다. #1-2 피보나치?var n = -1val cache = Array(1001) { -1 }fun main() {    n = readln().toInt()        cache[1] = 1 // (1)    cache[2] = 2 // (1 + 1), (2)    cache[3] = 3 // (1 + 1 + 1), (1 + 2), (2 + 1)    cache[4] = 5 // (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2 + 1), (2 + 1 + 1..

#1 알고리즘 Longest increasing subsequence - WikipediaFrom Wikipedia, the free encyclopedia Computer science problem In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in whichen.wikipedia.org위키백과에도 등재된 유명한 문제다. 위 링크에 문제 풀이 알고리즘을 표현한 GIF 이미지가 있다. 보자마자 문제 풀이 방향을 알게 된다. ..

#1 알고리즘#1-1 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘#1-1 정의동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com상향식 동적 프로그래밍을 이용해 풀었다. #1-2 색깔 조건약간 어렵게 쓰여있는 것 같지만, "모든 지붕은 그 직전 지붕과 색이 달라야 한다"라는 말로 압축된다. 현재 순회중인 지붕의 색과는 다른 색의 지붕을 재귀 호출하는 방식으로 색깔 조건을 구현할 수 있겠다. #1-3 캐싱 객체의 구조와 재귀 호출 가지치기말..

#1 알고리즘#1-1 하향식 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 #1-1 정의 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com하향식 동적 프로그래밍을 구현해 풀었다. Caching을 위한 객체로 HashMap를 사용했다. 예를 들어, 1 + 2 + 3 - 4 + 5 - 6 + 7라는 수식을 Caching하기 위해 makeListToKey()라는 함수를 만들었다 (#2 참조). 수식 makeListToKey()에 넣으면 "+1..

#1 알고리즘#1-1 상향식 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 #1-1 정의 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com상향식 동적 프로그래밍을 구현해 풀었다.  #1-2 수열의 규칙(점화식) 찾기1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ...문제에 제시된 위 수열은 p[n] + p[n+1] = p[n+3] 라는 간단한 점화식을 지니고 있다. #2 코드 - 코틀린/*수열 p가1, 1, 1, 2, 2, 3, ..

#1 알고리즘 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 #1-1 정의 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com하향식 동적 프로그래밍을 구현해 풀었다. 이 문제가 까다로운 이유는, 하향식 동적 프로그래밍에서 캐싱(Caching)을 할 때, 어떤 값을 캐싱해야할 지 난감하다는 것이다. 여러가지 경우들 중에서 최솟값을 골라서 캐싱해야 하는데 그 구현이 처음 문제를 봤을 땐 꽤 복잡해보였다. 나는 ArrayList에 재귀호출의 return값들을 ..

#1 알고리즘#1-1 문제의 핵심이 문제의 핵심은, x!가 가지고 있는 2*5 쌍의 갯수만큼 뒤에 0이 붙는다는 규칙의 파악이다. #1-2 상향식 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 #1-1 정의 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com상향식 동적 프로그래밍을 구현해 풀었다.  #2 코드 - 코틀린val twoCounts = Array(501) {0}val fiveCounts = Array(501) {0}// 2*5 ..

#1 알고리즘#1-1 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 이름을 붙었다. 확실히 static이 붙을 만한 작업은 아니지만, 그kenel.tistory.com상향식 동적 프로그래밍을 구현해 풀었다. 이 문제에서 가장 핵심적인 부분은 점화식을 구하는 것이다. 나는 먼저 점화식 calculateCombination(sum) = calculateCombination(sum - 1) + calculateCombination(sum - 2) + calculateCombination(sum - ..

#1 알고리즘#1-1 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 이름을 붙었다. 확실히 static이 붙을 만한 작업은 아니지만, 그kenel.tistory.com하향식 동적 프로그래밍을 구현해 풀었다. #1-2 #1-3 #2 코드#2-1 자바import java.util.*;public class Main { public static Map map = new HashMap(); public static void main(String[] args) { Inte..