2023-06-11 PS 일지

오늘 목표 달성도 ( 4 / 8 )

SUAPC 대비 할 일 ( 6시간 )
 ✔️ DP 실력 올리기 ( 매일 골드 DP 4문제 )
 ❌ 최적화 기법 공부하기 ( 하루에 2시간 )
 ❌ 자료구조의 god 되기
     - 매일 새로운 자료구조 :
     - 센트로이드 배우기

Codeforce Blue 찍기 위해 할 일 ( 3시간 )
  ❌ 그리디 실력 올리기 ( 매일 골드 그리디 3문제)
  ✔️ DP 실력 올리기 ( 매일 실버 DP 7문제 )

개인적인 실력 올리기 위해 할 일 ( 4시간 )
  ✔️ DP 실력 올리기 ( 매일 플레 DP 1문제 )
  ❌ 세그 정복하기 ( 매일 세그 문제 2문제 이상 )
  ✔️ 1000솔 채우기 ( 매일 브론즈 10문제 )

[ SUAPC 대비 할 일 ]

• DP 실력 올리기
  ✔️ Gold V 14728 벼락치기
  ✔️ Gold II 2662 기업투자
  ✔️ Gold V 17845 수강 과목
  ✔️ Gold IV 4781 사탕 가게

  	Review : 0/1 냅색 응용 문제를 해결했다. DP 실력의 부족함이 아직도 많이 보인다.
  	#2662를 해결하면서 무엇을 DP 배열로 두어야 할지 구체화를 제대로 하지 못했고,
  	시간을 많이 지체했다. #4781이 요구하는 기본 CS 지식은 내 실수 혐오를 증폭시켰다.
  	냅색은 비슷한 유형이 많아서 실버~골드 티어인 사람에게 티어복사기가 될 수 있을 듯 하다.

[ Codeforce Blue 찍기 위해 할 일 ]

• DP 실력 올리기
  ✔️ Silver I 11052 카드 구매하기
  ㄴ 바로 점화식이 그려지는 DP 문제였다. 왜 실버 I이지?
  ✔️ Silver I 11057 오르막 수
  ㄴ dp[시작 자릿수][수의 길이] 를 떠올리는데 약간 시간이 걸렸다.
  그러나 떠올리고 나서는 일사천리.
  ✔️ Silver II 11055 가장 큰 증가하는 부분 수열
  ㄴ LIS를 구하는 문제에서 살짝 변형된 DP 문제다. O(N^2)으로 해결 가능.
  ✔️ Silver II 1699 제곱수의 합
  ㄴ 의식의 흐름대로 풀렸던 문제.
  이거 O(N^2)인데? -> N=100,000인데? 뭐지? -> 아. 제곱수. O(N^(3/2))이구나.
  ✔️ Silver II 9184 신나는 함수 실행
  ㄴ 문제에 적힌 그대로 구현해서 메모이제이션만 첨가해주면 해결.
  그러나 if(dp[a][b][c]) 체크해주는거 까먹어서 맞왜틀 오래함.
  ✔️ Silver V 9655 돌 게임
  ㄴ O(N)으로 돌면서 dp[i-1]이나 dp[i-3]이 0이면 dp[i] = 1로 전이.
  = 홀수면 1이고, 짝수면 0임. O(1)에도 해결 가능.
  ✔️ Silver II 11048 이동하기
  ㄴ LCS를 구하는 DP랑 비슷하다. 왼쪽, 위, 대각선 중 하나를 골라서 전이하면 된다.

  	Review : 골드 DP 연습은 문제를 정확하게 파악하고, DP 배열 전이 순서에 신경쓰는 연습이 되었다.
  	반면 실버 DP 연습은 빠르게 문제를 파악하고 코드를 작성하는 CP 대비 연습으로 적절했다.
  	3월의 나는 랜실디도 자신이 없었는데 어느새 실버 DP는 아무거나 던져줘도 크게 어렵지 않은 수준까지 왔다.
  	6월 안에 민트따리를 벗어나서 블루로 향하는 걸 목표로 하자!

[ 개인적인 실력 올리기 위해 할 일 ]

• DP 실력 올리기
  ✔️ Platinum IV 평범한 배낭 2
  ㄴ 생각보다 어려운 냅색 문제였다. K개만 중복 가능하기 때문에 [N*K][M] 으로 만들어버리면
  K <= 10000이라서 [1,000,000][10,000] 배열을 선언해야 한다.
  K=1인 아이템들로 나누는 게 아니라 K=1,2,4,8,16, ... ,2^(n-1), K-2^n+1 로 나눠버리면 [NlogK][M]으로 선언할 수 있다.

  	Review : X

• 세그 정복하기
  ✔️ Platinum V 연세워터파크
  ㄴ DP 연습을 그렇게 하고도 DP 식 세울 생각을 못해서 한참 헤맸다.
  dp[i] = max(dp[i - D], dp[i - (D-1)], ... , dp[i-1]) + node[i] 인데, O(N^2)이면 TLE가 난다.
  따라서 [i-D, i] 구간의 max 값을 O(log N)에 구할 수 있도록 세그먼트 트리를 만들어주면 된다.
  세그 자체는 간단한데 DP가 합쳐져서 생각보다 오래 걸렸다.
  세그 DP는 DP를 먼저 생각해야겠다. 세그는 어디까지나 최적화 수단일 뿐이라는 걸 잊지 말자.
  

• Bronze 10문제
  ✔️ Bronze IV 6778 Which Alien?
  ✔️ Bronze IV 6810 ISBN
  ✔️ Bronze IV 6825 Body Mass Index
  ✔️ Bronze IV 6841 I Speak TXTMSG
  ✔️ Bronze IV 6887 Squares
  ✔️ Bronze IV 6888 Terms of Office
  ✔️ Bronze IV 7595 Triangles
  ✔️ Bronze IV 8558 Silnia
  ✔️ Bronze IV 8674 Tabliczka
  ✔️ Bronze IV 8710 Koszykarz