[99클럽 코테 스터디 2일차 TIL] 백준 11561 이진탐색, 등차수열

문제

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

오늘의 학습 키워드

등차수열

이번 문제에서 등차수열이라는 점을 인식하는게 매우 중요했다.

잘 생각해보면, 두번째 규칙에 의해 두번째 점프부터는 이전 점프 길이보다 1이상 점프해야하고 우리는 밟을 수 있는 최대 징검다리 수를 생각해야하므로 이전 점프보다 1보다 크게 점프하면 된다. 즉 초항은 처음 점프 길이, 공차가 1인 등차수열로 점프한 길이의 수열을 생각해볼 수 있다. 처음 점프 길이가 1이면 두번째는 2, 세번째는 3 ... 으로 이어진다.

중요한 건 등차수열의 합이다. 왜 중요하냐면 총 점프한 길이가, 즉 등차수열의 합이 N을 초과하지 않는 조건에서 최대로 밟을 수 있는 징검다리의 수를 구해야하기 때문이다. 공차가 1이고 점프한 횟수를 n이라고 하면 등차수열의 합(총 점프한 길이)는 n(n+1) / 2 로 구할 수 있다. 예를 들어 세 번 점프했을 때는 3*4 / 2 == 6, 4번 점프했을 때는 4 * 5 / 2 == 10이므로 징검다리 수가 6 ~ 9일 때는 최대 3번까지 점프가 가능하다.

이진탐색

위에서 언급했듯 결국 총 점프길이의 합이 N보다 작거나 같은 경우에 대해 최대 점프 횟수를 구하면 된다.

점프 횟수는 최소값은 1이고 최대값은 아래 사진에서 보듯 루트 2 * N(징검다리 수)로 정의할 수 있다. 아래 사진에서 k는 점프 횟수이다. 즉 등차수열의 합이 N 이하여야 하므로 등차수열 합 공식에 의해 최대 점프 횟수는 루트 2 * N이어야 한다.

 

따라서 1 ~ 루트 2 * N의 범위(점프 횟수)에서 이진 탐색을 하며

1. 총 점프 길이가 N이하이면 
   1. 최대 징검다리 갯수를 중간 값으로 갱신
   2. 최소 범위를 중간 값 + 1로 조정(아직 점프를 더 할 수도 있으므로)
2. 총 점프 길이가 N 초과이면
   1. 최대 범위를 중간 값 - 1로 조정(중간값 이상의 점프 횟수는 무조건 총 점프 길이가 N을 초과하므로)
3. 이진 탐색이 끝나면 최대 징검다리 개수를 반환

위의 과정을 거치면 된다.

공부한 내용 본인의 언어로 정리하기

등차수열

등차수열은 학창시절에 다들 배우는 수학 개념으로 연속한 두 항의 차이가 일정한 수열을 말한다.

예를 들어 2, 4, 6, 8 ... 은 연속한 두 항의 차이(공차)가 2인 등차수열이다. 등차수열의 첫번째 항을 초항이라고 한다.

등차수열의 합은 초항이 k이고 공차가 n이면 k * (k + n) / 2 로 나타낼 수 있다.

이진탐색이란

1일차에 이어 2일차도 이진탐색 문제가 출제되었다. 1일차 때 풀이를 정리하지 못하여 이진탐색에 대해 간단히 정리해보고자 한다.

이진탐색 예시

이진탐색(Binary Search)이란 탐색의 범위를 반씩 줄여나가며 값을 찾아나가는 절차를 의미한다.

위 사진을 반복적으로 중간값(mid)을 확인하며 탐색 범위를 줄여나가는 과정을 볼 수 있다.

예를 들어 1~10의 배열에서 8을 찾는다고 했을 때

 

1. 중간 값을 지정한다. 1~10에서는 5가 중간 값이다.

2. 5는 찾고자 하는 값이 아니므로 다시 탐색을 시도한다.

3. 5는 찾고자 하는 값 8보다 작으므로 탐색 범위를 6 ~ 10으로 조정한다.

4. 중간 값을 지정한다. 6 ~ 10에서는 8이 중간 값이다.

5. 찾고자 하는 값과 중간 값 8이 일치하므로 탐색을 종료한다.

 

만약 3번에서 중간 값이 찾고자 하는 값(ex. 3)보다 크다고 가정하면 탐색 범위를 1 ~ 4로 조정하면 된다.

이처럼 탐색 범위를 조정하며 값을 찾아나가는 것이 이진 탐색이며 이진 탐색 구현 시 중요한 점은

 

1. 범위가 특정 되어야 한다.

2. 중간 값과 비교할 수 있는 특정 조건이 존재해야 한다.

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  • 테스트 케이스는 통과했지만, 제출했을 때 시간 초과가 발생하였다.
  • 이진 탐색의 범위를 어떻게 줄여나갈지 고민해봤지만, 결국 해결하지 못했다.
  • 이진 탐색의 탐색 대상을 정의하는 부분에서 잘못 접근한 것 같다.
  • 탐색 대상을 점프 길이로 생각했는데 점프하는 횟수로, 즉 밟을 수 있는 징검다리 수로 접근해야 풀리는 문제였다.
• 어떻게 해결했는지
  • GPT의 도움을 받았다. 문제의 핵심 코드를 보며 풀이 과정을 이해하는 것으로 진행했다.
• 무엇을 새롭게 알았는지
  • 등차수열을 코딩테스트 풀이에 어떻게 적용하는지에 대해 알게됐다.
• 내일 학습할 것은 무엇인지
  • 이진 탐색의 조건을 쉽게 파악하는 방법에 대해 학습해봐야겠다.