일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- 스탠실 버퍼 사용
- CSS
- 스탠실 버퍼 튜토리얼
- react native mac
- 리액트 네이티브 맥
- stencil buffer
- html
- c++ using
- GitHub
- react native typescript navigate
- react
- 리액트 네이티브 설치 오류
- react native typescript
- 스탠실 버퍼 시작
- react-native
- 싸이월드
- react native typescript navigation
- node
- node.js
- javascript
- react native ios 기기 연결
- C++
- cyworld
- react native
- c++ 정보은닉
- Expo
- 벡터와 리스트의 차이
- react native 타입스크립트
- react native accessible
- unity stencil buffer
Archives
- Today
- Total
혀니의 이거저거 뿌시기
백준 11663 선분 위의 점(파이썬) 이분 탐색 본문
728x90
11663번: 선분 위의 점 (acmicpc.net)
11663번: 선분 위의 점
첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과
www.acmicpc.net
이분 탐색 문제이다.
처음에는.. 아 for문 돌리면서 풀어야할텐데 이걸 어떻게 이분탐색으로 풀지? 고민이 많았는데
어차피 가장 큰값과 작은 값에 해당하는 인덱스를 알면 거기서 빼기만 하면 되니까 이분탐색이 되겠구나! 하는 접근방법으로 다가갔다.
그랬더니 정답은 나왔는데....
<틀린 코드>
import sys
N, M = map(int,input().split())
dots = list(map(int,sys.stdin.readline().split()))
for i in range(M):
start, end = 0, N - 1
a, b = map(int, input().split())
while start <= end:
mid = (start + end) // 2
if a > dots[mid]:
start = mid + 1
else:
end = mid - 1
res = mid
start, end = 0, N - 1
while start <= end:
mid = (start + end) // 2
if b >= dots[mid]:
start = mid + 1
res2 = mid
else:
end = mid - 1
print(res2 - res + 1)
이렇게 제출했는데 틀렸다고 나온 것이다.. 시간초과도 아니고 왜 틀렸다고 나왔을까...
했더니, 1.dot이 순서대로 나온다는 보장이 없어서 sort를 해줬어야 함
2.res, res2를 잘못 설정해줌
이렇게 크게 두가지 이유가 있었다...
그래서 고친 코드는..
<고친 코드>
import sys
N, M = map(int,sys.stdin.readline().split())
dots = list(map(int,sys.stdin.readline().split()))
dots.sort()
def dot_min(a):
start, end = 0, N - 1
while start <= end:
mid = (start + end) // 2
if a > dots[mid]:
start = mid + 1
else:
end = mid - 1
return end + 1
def dot_max(b):
start, end = 0, N - 1
while start <= end:
mid = (start + end) // 2
if b >= dots[mid]:
start = mid + 1
else:
end = mid - 1
return end
for i in range(M):
a, b = map(int, sys.stdin.readline().split())
print(dot_max(b) - dot_min(a) + 1)
이렇게 된다.
우선 이분탐색에서 가장 중요한 키포인트는
1.각각의 이분탐색 식을 함수로 만들어서 필요할 때만 불러와 코드를깔끔+ 시간초과 피한다.
2.sys.stdin.readline()사용해야 시간초과 뜨지 않음
3.return해주는 값을 제대로 설정해야 한다.
사실 다 중요한 것 같지만... 계속 연습을 하자ㅏ...
728x90
'알고리즘 공부(C++)' 카테고리의 다른 글
백준 15663 N과 M(9) 백트래킹 파이썬 (2) | 2022.09.11 |
---|---|
백준 20291 파일 정리 (파이썬) 문자열 (0) | 2022.09.07 |
백준 19637 IF문 좀 대신 써줘 - 파이썬 (0) | 2022.09.07 |
백준 1343 폴리오미노 (0) | 2022.09.06 |
백준 2805 나무 자르기 - 이분 탐색 (0) | 2022.09.06 |