모각코 6회차

목표 : 이것이 코딩테스트다 with PYTHON 이진 탐색 공부를 하고 관련 문제를 풀어보자.

이진 탐색 : 반으로 쪼개면서 탐색하기, 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다.. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

재귀함수로 구현하기

반복문으로 구현하기

문제 풀이

크게 세가지 방안이 있다. 첫 째는 이번 챕터와 관련된 이진 탐색, 둘 째는 계수정렬, 셋째는 집합 자료구조를 이용하는 방법이 있다. 이 세가지 방법 모두 원리는 동일하다. 해당 원소가 있는지 없는지를 확인하며 비교해나가는 과정이다. 코드는 세가지 방법 모두 작성해보았다.

1. 이진탐색

2. 계수정렬

3. 집합

문제 풀이

적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정한다.
문제조건에 따라 최소값 1 최대값은 주어진 길이 리스트의 최댓값으로 두고 조건에 맞도록 코드를 구성한다.