백준 1300 파이썬 시간 복잡도 N^2인 알고리즘 불가
2024. 5. 21. 06:55ㆍ코딩 도구/백준
반응형
백준 1300 - k번째 수
문제
https://www.acmicpc.net/problem/1300
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
답안 코드 :
N = int(input())
K = int(input())
start = 1
end = K
ans = 0
# 이진 탐색 수행
while start <= end:
middle = int((start + end) / 2)
cnt = 0
# 중앙 값보다 작은 수 계산
for i in range(1, N + 1):
cnt += min(int(middle / i), N) # 작은 수 카운트 핵심 로직
if cnt < K:
start = middle + 1
else:
ans = middle
end = middle - 1
print(ans)
생각 :
# 문제 분석
# k는 min(10^9, N^2)이므로 시간 복잡도 N^2인 알고리즘 불가
# 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄여서 B[k]값을 구함.
# 문제 풀이
# 2차원 리스트는 N행이 N의 배수로 구성
# 2차원 리스트에서 k번쨰 수는 k를 넘지 않음. 1~k번째 안에 답이 있음
# 시작 인덱스 1, 종료 인덱스를 k
# 중앙값보다 작은 수의 개수가 k보다 작으면
# 시작 인덱스를 중앙값 + 1
# 중앙값보다 작은 수의 개수가 k보다 크거나 같으면
# 종료 인덱스를 중앙값 - 1
# 정답을 중앙값으로 업뎃하면서 시작 인덱스가 종료 인덱스보다 커질 때까지 이진 탐색
탐색 알고리즘 정리 블로그
탐색 알고리즘 정리
탐색 탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말한다. 주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이
mkisos.tistory.com
# 어렵다 완벽이해 x
반응형
'코딩 도구 > 백준' 카테고리의 다른 글
| 백준 1715 파이썬 우선순위 큐 (1) | 2024.05.23 |
|---|---|
| 백준 11047 파이썬 전형적인 그리디 알고리즘 (0) | 2024.05.22 |
| 백준 2343 파이썬 블루레이 (1) | 2024.05.20 |
| 백준 1920 파이썬 이진 탐색 O(nlogn) 시간 복잡도 (14) | 2024.05.19 |
| 백준 1167 파이썬 가장 긴 경로를 찾는 방법 관련 아이디어 (28) | 2024.05.18 |