알고리즘112 [백준] 2110 - 공유기 설치 (Python) 문제 출처: 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 문제 풀이 : 앞서 본 이분탐색과 같은 문제이다. 이런 문제류에서 바뀌는 부분은 찾는 특정값을 비교할때 사용되는 결과값을 구하는 부분인데 여기서는 아마 gap을 구하는 부분만 신경 써주면 될 것이다. 보통 for문으로 구하니까 복잡하지 않은 이분탐색 문제에선 while문 안에 있는 for문을 신경써서 보면 문제가 쉽게 이해가 된다. n, c = m.. 2021. 4. 9. [백준] 11286 - 절대값 힙 (Python) 문제 출처 : www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 풀이: 기본 라이브러리에 있는 heap 모듈을 사용했다. abs_h에는 절대값만 넣었다. 이건 최소힙으로 사용된다. h_dict은 dict 형태로 key값에는 주어진 값의 절대값을 넣고 , value에는 값 자체를 넣는다. value에 넣은 다음엔 해당 key값의 value들만 sort한다. 이후 문제에 주어진 대로 연산을 진행한다. 0이 아닌 값이 들어오면 abs_h에.. 2021. 4. 9. [백준] 2512 - 예산 (Python) 문제 출처 : www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 풀이 : 특정값을 찾을때까지 이분 탐색을 계속 시행하면 된다. 이경우엔 우리가 정하고 있는 어떤 값 보다 예산이 많으면 그 값만큼으로 짜른다는 조건이 있는데 이부분만 잘 처리해주면 정답을 쉽게 구할 수 있다. 원리에 대해서 생각해보면 가장 작은 예산인 1원을 left로 두고 주어진 값중에 가장 큰 값인 max값을 right두고 탐색을 시작한다. 기준값을 토대로 예산을 정한뒤에 계산된 예.. 2021. 4. 9. [백준] 최대,최소 힙 (Python) 문제 출처 : www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 문제 풀이 : 파이썬에서는 heap 모듈을 기본 라이브러리로 .. 2021. 4. 9. 이전 1 2 3 4 5 6 7 ··· 28 다음 반응형
