파이썬 코딩테스트 정복기 3탄입니다.
파이썬 코딩에 대해 기본적인 지식이 필요합니다.
각 단원마다 개념을 모두 포함하는 예제 한 문제만 풀이할 예정이니 참고해주세요.
1. 스택 + DFS + 이분 그래프
2. 큐 + BFS + 트리의 지름
3. 우선순위 큐와 그리디
4. 유니온 파인드 + 최소 신장 트리
5-1. 최단 거리 찾기[1] - 다익스트라 알고리즘
5-2. 최단 거리 찾기[2] - K번째 최단 거리
5-3. 최단 거리 찾기[3] - 벨만 포드
5-4. 최단 거리 찾기[4] - 플로이드 워 셜
6. 이진 탐색 + 트라이
7. 투포인터 + 슬라이딩 윈도우
8. 구간 합 + 세그먼트 트리
9. 에라토스 테네스의 체 + 오일러 피 함수
10. 유클리드 호제법 + 확장 유클리드 호제법
11. 조합 + 다이나믹 프로그래밍
이진탐색 알고리즘 개요
데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다. 특징은 아래와 같습니다.
- 데이터 탐색에 사용
- 중앙값 비교하여 대상을 축소
- 시간복잡도 O(logN)
구현 방법
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다
오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복합니다.
- 현재 데이터의 중앙값을 선택
- 중앙값 > 타깃 데이터일 때 중앙값 기준 왼쪽 데이터셋을 선택
- 중앙값 < 타깃 데이터일 때 중앙값 기준 오른쪽 데이터셋을 선택
- 중앙값과 타깃데이터가 같아서 탐색이 종료될때까지 반복
쓰이는 곳
- 정렬 데이터에서 데이터 탐색
백준 2343
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
# 블루레이가 될 수 있는 최소 크기(마지막 원소의 크기)부터 최대 크기까지(한번에 다 넣는 크기)
start = max(A)
end = sum(A)
m = 0
while start < end:
m = (start + end) // 2
cnt_m = 0
sum_lesson = 0
for lesson in A:
sum_lesson += lesson
if sum_lesson > m:
sum_lesson = lesson
cnt_m += 1
cnt_m += 1
# m에 더해지는 값이 다른 이유
# 주어진 블루레이보다 많이 담기면 무조건 그 값도 안되는 값
# 주어진 블루레이보다 적게 담기면
if cnt_m < M:
end = m -1
elif cnt_m == M:
end = m
else:
start = m + 1
print((start + end) // 2)
'컴퓨터 공학 분야 별 지식 > 개념(파이썬)' 카테고리의 다른 글
파이썬 코딩테스트 합격을 위한 팁 정리 (0) | 2024.03.22 |
---|---|
트라이(trie) 파이썬, 백준 14425 파이썬 (1) | 2024.03.22 |
최단거리 찾기 3 - 플로이드-워셜(floyd-warshall) 파이썬, 백준 11404 파이썬 (0) | 2024.03.22 |
최단거리 찾기 2 - 벨만-포드(bellman-ford-moore) 파이썬, 백준 11657 파이썬 (1) | 2024.03.18 |
K번째 최단 거리 찾기 파이썬, 백준 1854 파이썬 (1) | 2024.03.11 |