https://www.acmicpc.net/problem/2609

풀이

1. 유클리드 호제법 이용

2. r = a%b

3. gcd(a , b) == gcd (b, r)

4. r==0 이면
   이때 b가 gcd

​

https://www.acmicpc.net/problem/1430

풀이

1. 그냥 풀면 됨

2. 이 문제는 풀이가 의미 있는 것이 아니라,
   문제 자체가 의미 있음.
   문제 자체가 알고리즘 풀 때 쓰임.

3. 다이나믹 문제 풀다가
   int , long long 범위를 넘기 때문에 정답을

1

%100007

이렇게 구하는 문제가 있음.
이것은,
전체 정답을 구하고 나머지 출력하는것이 아님.
중간에 정수 범위를 넘어가기 때문에
중간 중간 나머지 연산 처리 해야함.

https://www.acmicpc.net/problem/11722

풀이

1. 가장 긴 증가하는 부분 수열과 동일

2. 다른 점

   • 증가하는 수열이 아닌 감소하는 수열
     검색할 때의 조건이 자신보다 높은값만 찾으면 됨
   • a[j] > a[i]

https://www.acmicpc.net/problem/11055

틀린 풀이

1. d[i]

   • a[1] ~ a[i] 중
   • a[i]를 포함하며,
   • 수열의 합

2. i번째를 기준으로 i-1번째 ~ 1번째로 하나 하나 검색

3. i번째보다 작으면 d[i]에 더함

맞는 풀이

1. 앞 문제와 동일하다

2. 앞 문제의 조건

   • i < j => a[i] < a[j]
   • max(d[j]) + 1 => 여기서 1은 길이

3. 1을 점수로 바꿔주면 됨

4. 햇갈리니까 표를 그리자!!

https://www.acmicpc.net/problem/11053

틀린 풀이

1. d[n]

   • 첫번째 ~ n번째 값 중,
   • 가장 큰 수

2. 10 20 10 30 20 50

   • d[0] = 0
   • d[1] = 10
   • d[2] = 20
   • d[3] = 20
   • d[4] = 30
   • d[5] = 30
   • d[6] = 50

3. d 배열의 값이 바뀔 때를 count

4. count 값이 답.

맞는 풀이

LIS 문제. 유명한 문제.

• d[i]

  • a[1] … a[i] 가 있을 때,
  • a[i]를 마지막으로 하는
  • 가장 긴 증가하는 부분 수열의 길이.
  • d[i]는 a[i] 가 반드시 포함

• ~ a[j] … a[i]

  • ~ a[j]길이 : d[j] —-> d[j] + 1

• d[i]

  • max( d[j] ) + 1

• a[j] 와 a[i]의 관계

  • a[j] < a[i]

1
2
3
4
5
6
7
8
9

  i			1     2     3     4     5     6 
a[i]		10    20    10    30    20    50 
d[i]     	 1     2     1     3     2     4         

d[4]를 예를들어,
d[4]는 처음에 1. 왜냐하면 자기 자신하나만 있으면 길이기 1이기 때문에.
a[3]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[3] +1 = 2. 1보다 크기 때문에. d[4]=2
a[2]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[2] +1 = 3. 2보다 크기 때문에 d[4] =3 
a[1]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[1] +1 = 1. 3보다 작기 때문에 그대로