난이도: Lv.3유형: 이분 탐색해결 여부: 아예 못품내가 생각했던 아이디어/큰 가닥주사위는 1대1 에서 5대5설마 다해보기인가. 그럼 최대 5개라 할때 일단 주사위 분배 정하는 과정 10C5, 각 계산합할때 나오는 경우의 수 다 쓰면 6^5+6^5, 비교하는 과정 하면 (6^5)^2... 엄청크다.하지만 기댓값으로는 승률 예외 있어서 다하는게 맞는거 같은데.. 뭐지 전혀 모르겠다.오답 이유해답A가 가져갈 주사위와 B가 가져갈 주사위를 일일히 고르는 것은 맞다그리고 그 합의 경우의 수도 일일히 구하는 것이 맞다.하지만 달라지는 건 A와 B 합 간의 비교이다. 정렬 후 bisect()를 활용해 그 개수로만 승패를 판별해 빠르다. 즉 이분탐색이 마지막에 들어간다.규모에 압도당해서 마지막에만 이분탐색 쓰면 되..
Algorithm/Binary Search
난이도: Lv.3유형: 이진 탐색 트리해결 여부: 틀림내가 생각했던 아이디어/큰 가닥하는법은 나와있는데로 트리 만들고 전위 순회, 후위 순회 하면 될거 같다고 생각은 했는데, 혹시 더 좋은 방법있나 싶기도 했고 시간도 많이 지나서 그냥 답 봤다. 오답 이유해답이런건 객체지향으로 푸는게 효과적이다. 지엽적인 문제이기 한데 문제 자체를 한번 알아두어야 한다. preorder과 postorder은 재귀적으로 언제 자신을 추가하고 언제 왼쪽과 오른쪽을 추가하는지로 간단히 구현할 수 있다.#기억할 문법 sys.setrecursionlimit(10**6) 으로 재귀 깊이 제한을 늘릴 수 있다.#정답코드import sys# 재귀 한도 늘리기 (필수)sys.setrecursionlimit(10**6)class Node..
난이도: Lv.3유형: 이분 탐색해결 여부: 포기내가 생각했던 아이디어/큰 가닥큰 가닥은 대충 이분탐색으로 적당한 완료시간을 먼저 구한다음에, 이후부터 스케쥴링 이미 올라간거랑 앞으로 될것들해서 마무리 작업 해주는걸로 구하는것일것 같았다.근데 그게 아닌것 같아서 시간도 다 되었고 해서 그냥 답 봤다. 오답 이유해답근데 그게 맞았다.적당한 시간을 잡은 이후에 스케쥴링 이미 되어 있는건 어카는지가 문제였는데, 그냥 신경을 안쓰면 되었다. 우리는 그냥 들어가는 순간만 포착하면 된다. % 연산으로 이를 해낼 수 있다. #기억할 문법 #내 오답코드#정답코드def solution(n, cores): # 1. n이 코어 개수보다 작거나 같으면 바로 n 반환 if n = n: target..
난이도: Lv.3유형: 이분탐색해결 여부:오답내가 생각했던 아이디어/큰 가닥이분탐색 문제 야근지수 꺼 틀려서 그때 그 아이디어 그대로 시도했다.큰 가닥은 맞았다. 다만..오답 이유low 초기값 설정이 문제였다. low를 무심코 n이라고 뒀는데 그래서는 안되었다. 1이라고 두는게 맞았다. 걍 잘 모르겠으면 low는 가능한 작아도 되고, high는 무식하게 커도 된다는 갓민 기억하자. 이분탐색에서 while에 등호 들어간다는 것도해답low값만 바꾸고 굳이 따지면#기억할 문법 #리스트 컴프리헨션은 아니지만 리스트 순회하면서 뭔가 계산할 때도 바로 조건 붙여서 계산하기 가능하다. #컴프리헨션에 얽매이지 말고 상황에 맞게 활용하기temp=sum(mid//t for t in times)#내 오답코드def solut..
난이도: Lv.3유형: 이분탐색, 힙해결 여부: 틀림내가 생각했던 아이디어/큰 가닥이분탐색으로 적정값 찾는 문제다. 여기까지 큰 가닥은 제대로 잡고 구현도 어느정도 잘되었다. 그런데...오답 이유문제는 샤갈 엣지케이스였다. 해답cutline을 바로 항상 /2 로 저장하는게 아니라, mid랑 분리시켜 가능할때만 저장하고, 이상/이하로 처리해서 +-1 더해주어야지 엣지케이스가 안난다.. 걍 외우자#기억할 문법 # 순회하면서 바로 조건ㅇ붙여서 계산하기 가능하다needed = sum(w - mid for w in works if w > mid) #내 오답코드def is_possible_cut(n,works,cutline): havetocut=0 for w in works: if cutli..
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net C++로 작성한 백준 문제 2110번 공유기 설치에 대한 문제 풀이다. 골드 4 문제로 이분탐색과 매개변수 탐색이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1,..., xN이고, 집 여러 개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 ..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net C++로 작성한 백준 문제 2805번 나무 자르기에 대한 문제 풀이다. 실버 2 문제로 이분탐색, 매개변수 탐색이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net C++로 작성한 백준 문제 1654번 랜선 자르기 에 대한 문제 풀이다. 실버 2 문제로 이분탐색과 매개변수 탐색이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가..
