문제 분석 완전탐색으로 풀기에는 M의 크기와 N의 크기를 곱했을 때 21억을 넘어감으로 불가능하다. 따라서 시간을 최적화해야 되는데, 이분탐색을 적용했다. 절단기의 높이가 0부터 주어진 나무의 최대값까지 선형적으로 있다고 가정하고, 절단기의 높이를 이분탐색을 통해 찾는다. 중간점검을 진행할 때, 절단된 높이의 합과 M의 길이를 비교하여 다음과 같이 min값과 max 값을 변경한다. 절단된 높이의 합이 M보다 크거나 같은 경우: min 값을 mid + 1로 갱신 절단된 높이의 합이 M보다 작은 경우: max 값을 mid - 1로 갱신 주의할 점은 절단된 높이의 합은 int를 초과할 수 있으므로 long으로 선언해줘야 한다. 문제 풀이 import java.util.Scanner; public class M..
Koala - 9기/코딩테스트 준비 스터디
문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 코드 from collections import Counter input = __import__('sys').stdin.readline input() s = list(map(int, input().split())) s = Counter(s) input() c = list(map(int, input().split())) ans = [] for i in c: i..
문제 https://www.acmicpc.net/problem/2110 Algorithm 임의의 두 공유기 사이의 거리를 늘리게 되면, 이외의 공유기와의 거리가 가까워질 수 있으므로 최대한 평등하게 설치하는 것이 핵심 아이디어다. 이분탐색을 진행하여, 가장 왼쪽부터 시작해 공유기를 설치한 집으로부터 임의의 수 k이상 떨어진 집에 설치하는 것을 반복한다. 더 이상 설치할 수 없는 경우, 설치한 공유기의 개수가 c개 이상이라면 k를 줄인 후 재설치한다. c개 미만이라면, k를 키워 재설치한다. 이분탐색이 끝난 후의 k가 출력 답안이 된다. Code #include #include #include using namespace std; int n,c; vector home; void INPUT() { ios_b..
문제 일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다. 틀린 풀이 # 선분 위의 점 # 복습 횟수:0, 00:30:00, 복습필요:O import sys si = sys.stdin.readline N, M = map(int, si().split()) point_list = list(map(int, ..
https://www.acmicpc.net/problem/15038 15038번: Lounge Lizards Monitor lizards are a kind of reptile known mainly for their cold-bloodedness and addiction to computer screens. Due to their love for digital displays, these scaly creatures spend most of their time at home glued to a small television in the lounge. Confl www.acmicpc.net 문제 분석 난이도 플래티넘5 분류 기하학, LIS(NlogN), 이분탐색, 유클리드 호제법 들어가기 전에 유명한 문..
https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 0. 잡담 아이고 로직은 맞았는데 입력 범위가 매우 커서 7트만에 맞았습니다!!를 받았습니다. 만약 알 수 없는 문제로 10%에서 계속 틀리신다면 코드의 모든 부분에 마음 편하게 unsigned long long 자료형을 써보세요. 혹시 답을 보고 푸셨다면 이곳에서 다시 풀어보시면 좋을 것 같습니다. 동일한 문제에 입력 값이 백준보다 작습니다. https://school.progra..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 코드 from itertools import accumulate from collections import deque input = __import__('sys').stdin.readline n, s = map(int, input().split()) li = list(accumulate(list(map(int, input().split())))) li = deque(li) li.ap..
문제 분석 부분 수열 문제는 보통 DP로 해결한다. 해당 문제의 경우, 감소하는 부분 수열의 최대값을 찾아야 한다. DP는 기본적으로 큰 문제를 작은 문제로 분할하는 것으로, 주어진 입력값이 작을 때 부터 차례로 값을 찾아야 한다. 특정 위치를 기준으로 다음 값을 판단한다. 다음 값이 현재 값보다 크면 감소하는 수열에 해당하지 않고, 현재 값보다 작은 경우 감소하는 수열에 해당한다. 결국 다음값이 현재 값보다 큰 경우 새로운 부분 수열이 시작할 수 있고, 다음 값이 현재 값 보다 작은 경우 기존 부분 수열의 길이가 하나 증가된다. 위와 같은 규칙을 고려하여 알고리즘을 작성하자. 특정 위치를 기준으로 생각했을 때, 감소 수열의 최대 길이를 판단하기 위해서는 자신의 값보다 순서상 앞에 있는 수들이 몇개가 있..
https://www.acmicpc.net/problem/13732 13732번: Falling Apples The input begins with a line containing integers R and C, designating the number of rows and columns of the grid, such that 1 ≤ R ≤ 50 000 and 1 ≤ C ≤ 10. The first line is followed by R additional lines, each designating a row of the grid, from to www.acmicpc.net 흔히 볼 수 있는 '중력' 문제이다. 그런데 그냥 아무생각없이 O(N^2)과 같은 시간복잡도로 구현하기 쉬운 유형이다. 큐를 이용..
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 0. 잡설 시뮬레이션 문제에 자신이 없어서 헤매다가, 좀 풀어보니 감이 좀 잡혔습니다. 시뮬레이션에서는 문제의 모듈화가 중요한 것 같습니다. 디버깅도 쉬워지고, 요새 코테에서 많이 사용하는 프로그래머스에서도 solve()모듈을 주니까 모듈화에 이점이 많은 것 같습니다. 또, 모듈화를 하면 중간중간 프린트를 찍어볼 때 어떤 모듈에서 생각대로 움직여주지 않는지 확인할수도 있겠죠!! 1. 접근 ..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 ..
문제 https://www.acmicpc.net/problem/1644 Algorithm 모르면 너무 어렵고 알면 너무 쉬운 문제이기에 출제 시 변별력이 굉장히 강하면서도, 소수 판정 + 투 포인터 태그 중 굉장히 교육적인 문제라고 생각되어 소개한다. 연속된 소수의 합으로만 이루어져 있어야하므로, 에라토스테네체의 체를 활용해 N까지의 소수를 담은 배열을 만들어야 한다. 에라토스테네체는 연속된 소수 판별의 대표적인 알고리즘이다. void Eratos(int num) { // 에테체 for(int i = 2; i*i n; } void Eratos(int num) { // 에테체 for(int i = 2; i*i
