조준장 개발자 생존기

문제 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 예산 상한액을 정하고 반복문을 통해 예산을 배정한다. - 예산 상한액보다 요청된 예산이 크다면 예산 상한액을 배정하고 그게 아니라면 요청된 예산을 배정한다. - 배정한 예산액이 총 예산보다 크다면 상한 예산액을 줄여준다. - 반대로 총 예산이 배정한 예산액보다 크거나 같다면 상한 예산액을 늘려준다. 코드 import sys n = int(sys.stdin.readline()) budget = list..

문제 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 공유기를 설치할 간격을 정하고 그 간격으로 공유기를 설치했을 때 모든 공유기를 설치할 수 있는지 확인한다. - 모든 공유기를 설치하고도 더 설치할 수 있다면 설치 간격을 늘려준다. - 반대로 모든 공유기를 설치할 수 있거나 공유기를 설치할 수 없다면 간격을 줄여준다. - 가장 인접한 두 공유기 사이의 최대 거리를 출력한다. 코드 import sys n, ..

문제 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 알고리즘 - 반복문을 통해 숫자 카드를 확인한다. - 이분 탐색을 통해 상근이의 카드 중에 현재 카드가 있는지 확인한다. - 상근이가 뽑은 카드가 현재 숫자 카드라면 1을 출력하고 반복을 멈춘다. - 상근이가 뽑은 카드가 현재 숫자 카드보다 크다면 더 작은 카드를 뽑기 위해 카드의 범위를 내린다. - 반대로 현재 숫자 카드가 크다면 더 큰 카드를 뽑기 위해 카드의 범위를 올린다. - 이분 탐색 후에도 상근이의 카드 중에서 현재 ..

문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 반복문을 통해 랜선을 잘랐을 때 남은 랜선의 개수를 구한다. - 자르고 남은 랜선의 개수가 필요한 랜선의 개수보다 크다면 더 이상 랜선을 자를 필요 없기에 반복을 멈춘다. - 필요한 랜선보다 현재 자른 랜선의 개수가 크거나 같다면 랜선을 자를 길이를 늘려준다. - 반대로 필요한 랜선보다 현재 자른 랜선의 개수가 작다면 랜선의 길이를 줄여준다. - 필요한 랜선의 개수를 만들 수 ..

문제 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 반복문을 통해 절단기로 나무를 자른 후 가져갈 수 있는 나무의 높이를 구한다. - 가져갈 수 있는 나무의 높이가 가져가려 하는 나무의 높이보다 크면 더 이상 가져갈 수 있는 나무의 높이를 구하지 않아도 되므로 반복을 멈춰준다. - 가져갈 수 있는 나무의 높이가 가져가야 하는 나무의 높이보다 크거나 같으면 절단기의 높이를 올려준다. - 반대로 가져가야 하는 나무의 높이..

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 기본적인 이분 탐색 문제로 가운데 수와 찾아야 하는 수가 똑같은지 확인한다. - 이분 탐색이 끝나고도 똑같은 수가 없다면 찾아야 하는 수가 없는 것이다. 코드 import sys n = int(sys.stdin.readline()) n_list = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin..

문제 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 아기 상어가 먹을 수 있는 물고기가 없을 때까지 반복한다. - 아기 상어가 현재 이동할 수 있는 모든 곳을 탐색하고 이동한 곳에 아기 상어보다 크기가 작은 물고기가 있다면 힙에 추가한다. - 문제를 보면 위, 왼쪽 물고기부터 먹어야 하는 우선순위가 있다. 따라서 heapq 우선순위 큐를 통해 물고기를 먹는다. - 아기 상어의 크기와 먹은 물고기의 양이 같다면 아기 상어의 크기를 1 키운다. - 위 ..

문제 1323번: 숫자 연결하기 첫째 줄에 N과 K가 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. K는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 - 나머지 연산을 하고 나머지가 0인지 확인한다. - 나머지가 0이면 연산 횟수를 출력한다. - 0이 아니라면 str으로 같은 수를 더하는 연산을 한다. - set() 자료형에 나누어야 하는 수를 추가하고 나누어야 하는 수가 set() 집합에 포함되어 있으면 무한 루트 이므로 -1을 출력한다. 코드 import sys n, k = map(str, sys.stdin.readline().split()) cnt = 0 # 연산 횟수 temp = n # 같은 수를 더하는 연산을 해줄 변수 paper = s..

문제 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 알고리즘 - 딕셔너리 자료형을 통해 문제를 수행한다. - 반복문으로 사이트의 주소와 비밀번호를 입력받아 딕셔너리에 담는다. - 반복문으로 찾고자 하는 비밀번호의 주소를 딕셔너리에 넣어 비밀번호를 출력한다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) site = dict() # 딕셔너리형 # 반복문을 통해 사이트의 주소와 비밀번호를 입력받아 딕셔너리에 담는다. for..

문제 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 알고리즘 - 맨 뒤에 있는 막대기를 제일 높은 막대기로 초기화한다. - 반복문을 통해 막대기의 높이를 확인한다. - 제일 높은 막대기보다 현재 막대기의 높이가 크면 제일 높은 막대기를 현재 막대기로 초기화해준다. - 제일 높은 막대기가 바뀔때마다 카운트한다.(처음에 맨 뒤에 있는 막대기를 제일 높은 막대기를 초기화했기 때문에 카운트를 1로 초기화) 코드 import sys n = int(sys.stdin.readline()) stack = [int(sys.stdi..