개미의 개열시미 프로그래밍

공유기 설치 풀이노트 스터디때 발표를 하기 위해 정리했던 내용을 그대로 올려본다. 발표때마다 느끼지만 왤케 더듬지.. 문제 이해하기 가장 인접한 두 공유기 사이의 거리를 최대 → "공유기 3개를 설치하는데 공유기 사이 거리를 크게” 정렬 된 집 좌표 : 1_2__4___ 8_ 9 1_ 2_______ 9 1 7 → 가장 인접한 두 공유기의 거리는 7이 아닌 1 1___ 4____ 8 3 4 → 가장 인접한 두 공유기의 거리는 4가 아닌 3 정렬하기 house = new int[N]; for(int i=0; i

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net [풀이 코드] ''' - 제한이 10억일때 이진탐색 - 반복적으로 중량을 선택하고 이동이 가능한 경우를 찾는다. 다른 예제 답이 5가 나와야함 3 3 1 2 9 2 3 5 1 3 2 1 3 ''' from collections import deque n, m = map(int,input().split()) a_list = [[] for _..

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 [첫 번째 실패 코드] from sys import stdin n = int(stdin.readline()) k = int(stdin.readline()) b_list = [(i+1) * (j+1) for i in range(n) for j in range(n)] b_list.sort() print(b_list) - 단계별풀어보기의 '이분 탐색' 파트인데 이렇게 풀면..

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 [풀이 코드] from sys import stdin n, c = map(int, stdin.readline().split()) a_list = [int(stdin.readline()) for _ in range(n)] a_list.sort() start = 1 end = a_list[-1] - a_list[0] # 끝집과 처음집을 뺴준 총 거리..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net [풀이 코드] from sys import stdin n, m = map(int, stdin.readline().split()) a_list = list(map(int, stdin.readline().split())) start, end = 1, max(a_list) while start 0: # cnt += tree - mid # 방법 2 cnt = sum..

백준 단계별 풀어보기 '이진 탐색' 세 번째 문제 랜선 자르기를 풀어보았다. 시간초 과부 터해서 오답, 런타임 에러까지 겪고 푼 문제.. https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [풀이코드] from sys import stdin k, n = map(int, stdin.readline().split()) array = [ int(input()) for _ in range(k)] start = 1 # 0으로 하..

백준 단계별 풀어보기 '이진 탐색' 두 번째 문제를 풀어보았고 전에 풀었던 수 찾기와 매우 비슷한 문제라 금방 풀 수 있었다. https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [풀이코드] from bisect import bisect_left, bisect_right from sys import stdin n = int(input()) n_list = list(map(int, stdin.readline().sp..

백준 단계별 풀기 이분 탐색 파트의 첫 번째 문제입니다. https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net [풀이 코드] from bisect import bisect_left, bisect_right from sys import stdin n = int(input()) n_list = list(map(int, stdin.readline().split())) n_list.sort() m = int(..