일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- 그래프이론
- 최단경로
- 알고리즘
- 파인튜닝
- 머신러닝
- LLM
- DP
- speaking
- bfs/dfs
- Lora
- Python
- Generative AI
- 데이터분석
- Coursera
- 스터디
- Scaling Laws
- 플로이드와샬
- English
- Fine-Tuning
- 코드트리
- 코딩테스트
- 프로그래머스
- 이분탐색
- 판다스
- 파이썬
- 완전탐색
- paper review
- peft
- 코딩테스트실력진단
- Study
- Today
- Total
목록이분탐색 (2)
생각하는 아져씨
2805번: 나무 자르기https://www.acmicpc.net/problem/2805 문제 정의상근이는 M미터의 나무가 필요해서 나무를 벌목하려고 한다. 절단기의 높이를 설정하면, 높이만큼 나무를 잘라주는데, 나무들의 높이가 주어졌을 때 적어도 M미터의 나무를 가져가려면 절단기의 높이를 최대 몇까지 설정할 수 있을까? 접근 방법나이브한 접근방법나무리스트 [20, 15, 10, 17] 가 주어졌을 때, 절단기의 높이를 1~최대 나무 높이(=20)까지 설정해보면서, (나무-절단기높이)의 합이 M미터 이상인지 확인하면 된다.즉, sum(각 나무높이 - 절단기 높이) ≥ M (적어도 M 미터이므로, M이상과 비교하면 된다.)하지만, N은 최대 2,000,000,000 이므로, 이중 for문을 사용하면 시간 ..
10816번: 숫자 카드 2https://www.acmicpc.net/problem/10816 문제 정의상근이는 숫자 카드 N개를 가지고 있다. 정수가 M개 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하면 된다. 만약 상근이가 6 3 2 10 10 10 -10 -10 7 3 카드를 가지고 있을 때,10 9 -5 2 3 4 5 -10 → 이 숫자들을 몇개 씩 가지고 있는지 출력하면 된다.이 예에서는 10은 3개 가지고 있으므로 3으로 출력하면 된다. 접근 방법N과 M이 최대 500,000이 될 수 있는데, 일일히 2개의 리스트를 비교하기에는 O(N2)O(N^2)O(N2) 으로 시간 초과가 뜰 수 있다.그래서 x가 리스트 안에 몇 개 있는지 찾기 위해서 기준 숫자인 mid..