99클럽 코테 스터디 2일차 TIL(이진탐색,등차수열,일반화)

제목: 99클럽 코테 스터디 0일차 TIL + 오늘의 학습 키워드

🚨오늘의 학습 키워드

문제 : https://www.acmicpc.net/problem/11561

⭐️이진탐색⭐️

1일차와 동일!
mid값과 결과값을 비교하며 범위를 반씩 변경하며 탐색하는 알고리즘

⭐️등차수열⭐️

$수열 : 1 + 2 + 3 + ... + k$

$Sn(수열의 합)= k(k+1)/2$

⭐️일반화⭐️

수식의 패턴을 쉽게 인식하기 위해 사용
생략할 부분은 0으로 치환하거나 없애 패턴 파악에 유용하다

오늘의 회고

1. 첫번째 시도
   첫번째 점프거리를 이진탐색으로 찾는것으로 초점을 맞춰서 문제를 접근했다

   첫점프 : x
   두번째 점프 : x+1
   세번째 점프 : (x+1)+1
   ...
   첫번째 점프+1이상이 두번째 점프이기 때문에
   첫번째 점프에서 전체 징검다리의 반을 뛰게 되면 N번째 징검다리를 밟을 수 없다고 판단해서
   Right:전체 징검다리의 반-1, Left: 1 로 시도 했다
   이렇게 시도했더니 범위가 쉽게 좁혀 지지 않았고
   첫번째 점프에 따라
   while 문을 통해 점프마다 이동한 위치를 확인해 N번째에 도달하는지 여부를 파악하고

   최대 징검다리 수 도달한 경우)
   result = mid;
   right=mid-1;

   최대 징검다리 수를 초과한 상태에서 도달을 못한 경우)
   right=mid-1;

   최대 징검다리 수 미만인 상태에서 도달 못한 경우)
   left=mid+1

2. 두번째 시도

• 수열 합 공식 일반화 적용

• 첫번째 점프가 적을 수록 건너는 징검다리의 개수가 늘어난다

• 구하려는 값이 징검다리를 건넌 횟수이므로 징검다리를 건넌 횟수(k)와 mid를 비교한다

• 첫 점프한 거리:a1, 점프한 횟수:k

  $N(전체징검다리 수) = a1+(a1+1)+(a1+2)+(a1+3)+...+(a1+(k-1))$
  $N = a1*k+k(k-1)/2$

  일반화 (a1=0, 첫번째 점프=0)

  $N = 1+2+3+4+...+k$
  $N(일반화) = k(k+1)/2$
  $k = \sqrt{2N}$

  left = 1;
  right = N;
  mid = (left+right)/2

  k = mid(mid+1)/2;

  k<=N 경우) == mid(k)를 늘려보자
  result = mid;
  left = mid+1;

  k>N 경우) == mid(k)를 줄여보자
  right = mid-1;