03-04 학습! 🟥🟧🟨🟩🟦🟪🟫⬜⬛🫢🔔😎😊🤔😭⭐
분할정복 🟥
양팔저울 🟧
24개의 동전 중 1개의 가짜 동전이 있다 가짜 동전은 무게가 차이가 난다
양팔 저울을 최소로 비교하여 가짜 동전을 판별하는 방법은?
거듭제곱 🟨
가장 쉬운 방법 - 반복문 -> O(N) 만약 n = 1000000000 (10억) 이라면?
곱하기 성질을 이용한 분할정복!
Recursive_Power(x,n)
if n == 1 : RETURN x
if n is even
y <- Recursive_Power(x, n/2)
RETURN yy
else
y <- Recursive_Power(x, (n-1)/2)
RETURN yy*x
순수함수🟩
부수효과가 발생하지 않는 함수
-> memoization 가능!
같은 색 공간 만들기 🟦
한변의 길이 N과 전체 공간을 구성하는 각 단위 정사각형 공간에서 하얀색 공간과 초록색 공간의 정사각형의 갯수를 구하는 프로그램!
어떻게 빠르게 해야할까?
병뚜껑 속의 숫자 게임 🟪
숫자를 부르면 Up 또는 Down을 통해 병뚜껑 속 번호를 맞추는 프로그램
분할정복! 이진탐색! 이분탐색!
어떻게 분할정복(이진 탐색)을 할 수 있었을까?
⭐⭐⭐자료가 정렬된 상태⭐⭐⭐
이진탐색🟫
- 자료의 중앙에 있는 원소를 고른다.
- 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
- 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 끝낸다.
- 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
- 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.
java.util.Arrays.binarySearch⬜
int binarySearch(int] a, int key)
int binarySearch(int] a, int fromIndex, int toIndex,int key)
=> 찾으면 찾은 원소 index 못찾으면 -삽입위치-1
⭐⭐⭐전제조건: 배열 a는 정렬된 상태여야 한다! ⭐⭐⭐
toIndex는 포함 안하는 거 주의!
Lower Bound & Upper Bound⬛
정렬된 배열에서 특정 값을 찾거나, 삽입할 위치를 찾는 데 사용되는 이진 탐색 기반 알고리즘
Lower Bound (이상)
목표 값보다 같거나 큰 값이 처음 나오는 위치
Upper Bound (초과)
목표 값보다 큰 값이 처음 나오는 위치
나무 자르기 🤔
7730. 나무 깎는 홍준
나무 자르기
문제
여러개의 나무에서 특정 높이 설정 시 해당 높이 보다 큰 나무의 윗 부분을 다 잘라줌
절단 높이를 신중하게 조정하여 최소 M미터 이상의 목재를 얻으면서 가능한 한 높은 절단 높이를 구하는 방법
해결 방법
절단 가능한 높이를 잡아보자
파라메트릭 서치⭐
최적화 문제를 결정 문제로 변환하여 이진 탐색 기법을 활용하여 해결하는 방법
이진 탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건을 만족하는 최적해를 찾을 때 사용!
범위가 주어져있고 최적해를 찾아야할 때 logN으로 바꿔줄 수 있음!
숙제
자기소개서 작성, SQLD 공부
