[백준] Gol5 | 투 포인터,이진탐색 | 9024 두 수의 합 Pythonhttps://www.acmicpc.net/problem/9024 구상직전에 푼 3273번과 매우 유사한 문제! 풀이 1 : 이진탐색 (시간초과)TS : 테케 통과, 시간초과.. pypy는 통과!!! 논리는 맞았으나 시간이 문제.풀이 2 : 투 포인터이진탐색 문제는 투 포인터로도 풀 수 있다! [문제 해석]주어진 서로다른 수들 중 두 수의 합이 특정 수k에 가장 가까운 조합의 수숫자들은 -10^8 ~ 10^8(1억) 사이 정수. 숫자의 개수n는 1,000,000개 이하시간제한 : 1초답 : 합이 k에 가장 가까운 두 수 조합의 개수 구상2천만 연산 내에 짜야 함. n^2이면 시간초과3273번처럼 정렬 + 이진탐색 으로 짜면 될까..
이진탐색
[백준] Sil3 | 정렬,이진탐색 | 3273 두 수의 합 Pythonhttps://www.acmicpc.net/problem/3273 구상유형 : 정렬, 이진탐색시간초과땜에 이진탐색logn 사용완전 + 이진 -> nlogn [문제 해석]주어진 수들 중 두 수의 합이 특정 수x가 되는 경우의 개수숫자는 1~1,000,000 자연수, 숫자의 개수는 100,000 개 이하시간제한 : 1초 구상시간제한이 1초 = 2천만 건 안에 처리 -> n^2이 나오면 안됨2중 완전탐색 : n^2 시간초과완전 + 이진탐색 : nlogn, 통과!탐색 방법정렬해두고 탐색젤 작은거 + 더 큰거 로 시작작은걸 고정해두고 큰걸 옮기면서 반복, 합이 x보다 같거나 작아지면 break다음 작은 수 탐색작은 수는 배열 끝까지 탐색숫자..
[백준] Sil2 | 이진탐색 | 18113 그르다 김가놈 Pythonhttps://www.acmicpc.net/problem/18113 구상v1 : 이진탐색 이름이 왜 이런가 했더니..ㅋㅎㅋㅎ 트러블 슈팅TS 1 : 시간초과 -> 이 풀이는 pypy 로 돌려야 풀 수 있다고 함TS 2 : 2% 에서 틀렸습니다 -> mid로 나눗셈 연산을 해야해서 mid가 0이면 안됨. left=1로 시작하고 leftTS 3 : 80%쯤에서 틀렸습니다 -> 이진탐색 if문에서 이번값==목표값 인 경우에도 최적의 정답이 아닐 수 있으므로 바로 break로 탈출하면 안됨. 범위 조절해서 이어서 탐색해줘야 함..(아마도 김밥 남은거 버리고 꼬다리 자르고 뭐 그래서 그런듯...wow 문제에 따라 사용할것) 코드# v1 : ..
[백준] Gol4 | BFS, 이진탐색? | 2412 암벽등반 Pythonhttps://www.acmicpc.net/problem/2412 구상 main idea는 bfs최소경로찾기, 거기에 이진탐색을 쓰면 시간을 더 줄일 수 있음bfs만 써서 풀어봄이게 왜 이진탐색???→ 최소거리 찾는 거 자체는 bfs 해주면 되는데, 간선 데이터가 주어지지 않아서 다음 노드 찾기에 이진탐색을 쓸 수 있음이진탐색 : 홈을 정렬하고, 이진탐색으로 현위치에서 이동 가능한 최소&최대 홈을 구한다. 그 후 정렬된 홈 목록에서 최소&최대 홈 사이의 홈들만 탐색하도록 한다!.→ 이진탐색 안써도 풀리는 문제ㅇㅇ트러블 슈팅시간초과다음 노드를 찾을 때 노드를 모두 확인하는 게 아니라 원하는 숫자 범위 안에 노드가 존재하는지 탐색하..
[백준] Sil2 | 이진탐색 | 2805 나무자르기 Pythonhttps://www.acmicpc.net/problem/2805 구상최적 값 어딘가를 찾기 → 이진탐색~~만만하게 봤다가 오래걸린 문제 ㅎ반례는 찾아봤지만 솔루션 안보고 풀었다! 만세! 트러블 슈팅TS 1 : 클래식해보여도 알고리즘을 외워서 쓰려고 하지 말고 문제에 맞게 말랑하게 생각하거라 . . .TS 2 : 이진탐색 시 양쪽 인덱스가 같은 경우는 문제에 따라 포함여부 달라짐! 문바문 코드# v1 : 이진탐색# 그냥 클래식한 이진탐색으로 구현하면 될 것 같은데？# TS 1 : 클래식해보여도 알고리즘을 외워서 쓰려고 하지 말고 문제에 맞게 말랑하게 생각하거라 . . .# TS 2 : 이진탐색 시 양쪽 인덱스가 같은 경우는 문제에 따라 ..
[백준] Sil4 | 이진탐색 | 1789 수들의 합 Pythonhttps://www.acmicpc.net/problem/1789 구상두가지 방법으로 풀이했다.손구상 풀이 (greedy)내가 손구상한 풀이로도 가능했음. 답까지 모든 경우에 조건을 확인해야해서 더 오래걸리지만..이진탐색문제라고 해서 이진탐색으로도 풀었다이진탐색으로 한번 더 풀어보자 트러블 슈팅이분탐색 시 다음 범위는 현재 중간값을 포함하지 않는 범위로 설정해줄 것!숫자 합 계산에 sum(range()) 를 썼더니 시간초과 발생. 1~n까지의 합 = n(n+1)/2 임을 활용하자! 코드 - greedy# v1 : greedy (60ms)# 그리디 / 이진탐색 둘 다로 풀리는 문제# TS : range 범위 경계값에 걸리는 경우 ..
