생각보다 오래 고민한 문제
가장 도움이 되었던 힌트는 dp[i]배열에 수열의 첫번째 부터 i번째 까지의 최장 부분수열의 길이를 저장하는 것이다.
n 까지 dp[i]를 저장하는데 이중 for문을 돌면서 i보다 1적은 수 까지 도는 j를 선언해 arr[i]보다 작은 j 들 중 가장 큰 dp[j]를 찾아 dp[i]에 이 값에 1을 더한 수를 저장한다.
dp 계산이 끝나면 최대 dp 값을 찾아 출력한다.


- 코드

---

DP 문제다. 접근방법이 아무리 생각해도 떠오르지 않아 해설을 참고했다.
스티커 판과 같은 크기의 DP 점수 계산 배열을 만들고 첫번째 줄 부터 반복문을 돌면서 해당 칸을 선택 했을 때의 최댓값을 저장해놓고 다음 열의 점수를 구할 때 이용하는 것이다. 스티커를 고를 수 있는 경우의 수는 2가지로, 바로 전 열의 대각선 칸에 위치한 스티커를 선택하거나, 그 전 열의 대각선 칸에 위치한 스티커를 선택할 수 있다. 두가지를 비교하여 더 큰 값을 저장하면 된다.


즉 점화식이 다음과 같이 나온다.


코드


참고 https://lesslate.github.io/onlinejudge/Baekjoon-9465%EB%B2%88/

DP 를 확실히 공부하고 나니 DP로 풀어야 겠다는 생각은 바로 들었다. 알듯 말 듯 답이 떠오르지 않아 수열을 계산해 봤는데 피보나치 수열이 나왔다. 일단 풀고 보자 싶어서 풀었다. 처음에는 10,007로 마지막에 모듈러 연산 하여 답을 출력했는데 틀렸다고 나왔다. 질문을 검색해보니 10,007 이라는 큰 소수로 나눔으로써 메모이제이션을 하면서 값이 제대로 저장되지 않음을 방지하는 것이라 연산하는 도중에 모듈러를 해줘야 했다. 그리고 손쉽게 문제를 해결했다.

코드

---

답이 피보나치수열인 이유

N 열의 타일링을 채우는 경우의 수를 f(n)이라고 할 때, f(n)은 제일 오른쪽을 가로 블록 2개로 채운 경우의 수 + 세로 블록 1개로 채운 경우의 수이기 때문에 점화식은 결국
f(n) = f(n-1) + f(n-2) 가 나온다.
예를 들어, 만약 2*5칸짜리 타일이 있고 오른쪽을 가로 타일 2*1 2개로 채웠으면 결국 2*3 칸을 채우는 경우의 수가 답이 되고, 오른쪽을 2*1 1개로 채우면 2*4의 경우의 수가 나오므로 피보나치 수열이 점화식이 되는 것이다.

동적 프로그래밍

'하나의 문제는 한 번만 풀도록 하는 알고리즘'

분할 정복 기법의 단점을 보완하는 알고리즘이다. 그 단점이라 하면, 동일한 문제를 다시 푼다는 것. 예를 들어 피보나치 수열 문제에서 답을 구하기 위해서는 매 항이 바로 앞의 두 항을 필요로 한다. 이를 분할 정복 기법으로 풀 경우 같은 값을 반복적으로 다시 계산해 구해야 하기 때문에 비효율 적이다. 따라서 이럴 때 동적 프로그래밍 기법이 사용되어야 한다.


그림에서 볼 수 있듯 분할 정복 기법을 이용패 피보나치 문제를 해결하려고 하면 12번째 수를 세번이나 계산하게 된다. 이 때의 시간 복잡도는 O(2^n)으로 구하려는 수가 커지면 비용이 기하급수적으로 증가한다. 이럴 때 바로 동적 프로그래밍 기법을 사용해야 하는 것이다.

다음과 같은 가정하에 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

이 과정에서 Memoization(메모이제이션)이 사용된다는 점이 분할 정복법과 다른 점이다.
계산한 값을 저장하는 과정이다. DP를 사용하게 되면 이미 계산되어있는 연산은 안해도 되기 때문에 트리의 깊이 만큼만 계산이 이루어져 시간 복잡도는 O(n)이 나온다. 분할 정복 기법에 비해 엄청나게 감소한 것이다.

방식은 top-down과 down-top 이 있다. 자신에게 잘 맞는 방식으로 문제를 풀면된다. 둘 중 하나의 방식으로만 풀리는 문제도 있다고는 하는데 난 아직 본 적 없다.

코딩테스트에서 매우 자주 등장하므로 꼭 풀 줄 알아야 한다!

예제 ) 백준 1463 - 1로 만들기 (https://www.acmicpc.net/problem/1463)

자바에는 다양한 라이브러리가 있다. 그 중 가장 많이 사용되는 라이브러리는 단연 jquery 이다. 라이브러리가 많고 다양한 기능이 있는 만큼 라이브러리의 사용 목적을 잘 알고 써야 한다.

JQuery

jQuery는 출시되고 10년 동안 인기를 독차지 하고 있었다. 2018년 부터 그 인기는 줄어들고 있고 더이상 배울 필요는 없다고 한다. 하지만 그동안 몇가지 프로젝트를 해오면서 자료를 검색하면 항상 제이쿼리 = 자바스크립트 인 듯 사용하는 사람들이 많아 나같이 자바 스크립트를 아직 완벽하게 사용하지 못하고 계속해서 검색을 해야 하는 입장에서는 어느정도 문법은 쓸 줄 알아야 하지 않을까 싶다.

jquery가 인기가 많았던 이유가 몇가지 있다.

• 다양하게 동작하는 웹브라우저의 API간 차이를 줄여주었다.
• 복잡하고 어려운 DOM API를 추상화해서 제공하여 쉽게 DOM조작이 가능하게 해준다.
• 사고의 흐름에 맞춰 프로그래밍 할 수 있다.

Framework

결론

this 키워드는 this를 참조하고 있는 객체를 가리킨다.  함수 내부에서 사용하면 보통 해당 함수를 가리킨다. 하지만 this가 다른 객체를 가리키게 할 수도 있다.

for문을 써도 대부분의 반복 작업은 어려움 없이 할 수 있다. 하지만 자바스크립트에는 다른 여럭 메서드들이 존재하고 이를 잘 활용하면 for문 없이도 간단히 코드를 짤 수 있다.

위 데이터를 놓고 실험해보자.

1. forEach
data 내부 값을 출력하는 코드다.  위 for문을 보면 반복을 수행하기 위해 'i'를 새로 선언 하고있다. 하지만 forEach를 사용하면 function 을 인자로 받아 다른 변수의 선언이 불필요하고 간결하게 만들 수 있다.

2. map / filter

map 메서드는 함수에서 정의한 방법대로 모든 원소를 가공해서 원본 데이터를 변화시키지 않고 새로운 배열을 반환한다. 위 코드는 data에서 가격을 10배 인상하는 코드이다. 결과 데이터를 보면 10이 곱해진 price만 들어있는 배열이 들어온다.
price뿐 아니라 모든 데이터를 가진 원본 데이터 형식의 새로운 데이터 배열을 만들고 싶다면 새로운 배열을 만들고 값을 넣어 반환하게 해야 한다.


filter 메서드는 함수에서 정의한 조건에 맞는 원소만 추려서 해당 원소만 가진 새로운 배열을 반환하는 '필터'같은 메서드다. map 메서드와 달리 if 문 처럼 동작하면서 필터를 거친 데이터는 전부 반환한다.

3. 복합
5. reduce
배열의 모든 요소에 대해 지정된 콜백 함수를 호출하며 콜백 함수의 반환 값을 누적하여 반환하는 함수이다. reduce 함수는 매개변수로 콜백 함수와 누적을 시작하기 위한 초기 값을 받으며 초기 값은 선택사항이다. (디폴드 값은 0)


위 코드를 실행해보면 모든 상품의 가격을 더해 출력하는 결과가 나온다.
 콜백 함수 (reducer)는 4개의 인자를 가진다.

1. 누산기(acc) : 콜백의 반환값을 누적한다. 콜백함수의 이전 반환값 또는 초기값을 설정한 경우 설정한 초기값이 들어간다.
2. 현재값(cur)
3. 현재 인데스(idx)
4. 원본 배열(src)