MZ 개발자

문제 풀이의 핵심은 한블럭 이동을 w 대각선 이동을 s라 할때 (0,0) 에서 (1,1)로 갈수 있는 방법중 최소시간을 우리는 구할 수 있다. 즉 s 와 2*w 중 걸리는 시간이 작은 것을 고르면 된다. 단순하게 생각하면 만약 대각선으로 움직이는 것이 직선으로 이동하는것보다 작을 경우 즉 s> x >> y >> w >> s; if(2 * w

문제의 힌트를 보면 잘 이해가 되지 않는다. 상식적으로 웅덩이를 덮을때 시작점에 딱 맞춰서 널빤지를 붙이면 최적이다. 힌트를 보면 웅덩이는 1에서 시작하는데 널빤지를 0에서 부터 붙이기 시작하여 사실상 힌트 오류라고 할수 있다. 실제 맞는 예시는 다음과 같다. .111222.333444555 .MMMMM..MMMM.MMMM 풀이 방법은 각 웅덩이 위치를 백터 v에 넣어 정렬한 후 각 웅덩이 마다 깔수 있는 널빤지를 구해주면 된다. 핵심은 널빤지가 다른 웅덩이를 일부 덮는다면 거기서부터 계속 붙여나가고, 그렇지 않고 널빤지의 끝이 일반 땅이라면 그다음 웅덩이부터 다시 붙여나가면 된다. #include #include #include using namespace std; int main() { ios_bas..

문제에서 어떤 두 정수 min과 max 사이에 수가 1보다 큰 제곱수로 나누어 떨어지지 않을때 제곱 ㄴㄴ 수 라고 정의를 하였다. 어떤 수가 제곱수로 나누어 떨어지지 않은것을 구하기 위해 우리는 에라토스테네스 방법을 응용할 수 있다. 처음 떠올린 방법은 부르트포스로 생각하였는데 제곱수가 될수 있는 n이 1000000, max-min이 1000000이므로 1000000*1000000 즉 1조가되어 시간초과가 발생한다. 기본적인 에라토스테네스는 소수를 구하기 위해 2,3,5,7의 배수를 모두 지우고 지워지지 않고 남은 수를 우리는 소수임을 알수 있다. 이를 응용하여 i*i (i>1) 가 max 보다 작을때 까지 i*i의 배수를 모두 지워주면 된다. 이때 시작지점은 i*i 가 min 보다는 커야하므로 min/..

이 문제는 0을 뒤집거나 1을 뒤집어서 최소한의 뒤집기로 같은 숫자를 만드는 문제이다. 따라서 0과 1이 바뀌는 구간을 기준으로 0인 구간의 갯수과 1인 구간의 갯수중 최소인 숫자를 뒤집으면 답이된다. 예를들어 0001100의 경우 0의 구간은 앞쪽 000, 뒷쪽 00으로 총 2번 뒤집어야한다. 하지만 1의 구간의 경우 가운데 11으로 1번만 뒤집으면 된다. 따라서 최소한으로 뒤집어야하는 횟수는 1이 된다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; int oneCnt = 0, zeroCnt = 0; for(int i..

S는 서로 다른 N개의 자연수의 합이기 때문에 N은 1부터 증가하면서 누적 합이 S를 초과하기 전의 N을 구하면 되는 문제이다. 하지만 S의 범위는 int를 초과하는 범위이기때문에 long long으로 바꿔주어야한다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long s; cin >> s; long long sum = 0; long long answer = 0; for(long long i = 1; ; i++) { if(sum + i

이 문제의 핵심은 모든 통나무 조각 길이보다 큰 경우를 만족하는 적절한 길이의 통나무를 구하는 문제이다. 예를들어 L =9, K=2, C=1 일 경우 나올수 있는 통나무 조각은 4,1,4이다. 이때 모든 통나무 조각 길이 보다 긴 적절한 길이의 통나무를 구해야한다. 우리가 생각해야하는 조건은 두가지이다. 1. 모든 잘린 통나무 조각은 적절히 자를수 있는 최대 길이(mid)로 모두 자를 수 있어야 한다. 2. 자를수 있는 횟수를 초과 하면 안된다. 이를 바탕으로 풀이를 다음과 같이 생각해볼 수 있다. 1. 만약 잘린 통나무 누적 길이가 mid보다 커지는 순간까지 cut을 하지 않고, 커지는 순간 cnt을 증가시켜준다. 2. 이후 마지막으로 누적한 통나무의 길이가 mid 보다 클경우 위의 조건 1을 만족하지..

MYSQL의 다양한 순위 함수 중 RANK()에 대해 연습해 볼수 있는 괜찮은 문제이다. 학부과정에서 다양한 고급 함수를 배우기 보다는 기본 SQL을 배우다보니 문제를 보는 순간 풀이가 바로 떠오르지 않았다. 프로그래밍이라면 IF - ELSE 를 사용하여 rank를 구할수 있겠지만 SQL문에서 IF - ELSE 사용은 많이 사용해본적이 없어 자신이 없었다. 문득 혹시 내장 함수중에 rank를 구해주는 함수가 있지 않을까 찾아보니 역시나.... 모르는게 너무 많은것 같다. 우선 기본적으로 MYSQL에서 다양한 순위함수(분석함수)를 제공해준다. 더보기 PARTITION BY : 동일 그룹으로 묶어줄 칼럼 명 지정 ORDER BY : Partition 정의에 지정된 컬럼에 대한 정렬 수행 SELECT (arg..

Employee 테이블에 employees와 managers가 섞여 있는 상황에서 employee의 salary가 manager의 salary 보다 더 많은 사람의 name을 반환하도록 SQL을 작성하는 문제이다. Employee 테이블에 직원과 매니저 정보가 모두 들어있기 때문에 cartesian product를 이용하여 managerId = id 인 레코드를 뽑아낸 후 조건에 맞게 where문을 작성해준다. SELECT e1.name AS Employee FROM Employee AS e1, Employee AS e2 WHERE e1.managerId = e2.id AND e1.salary >e2.salary

가장 기본적인 그리디를 연습할 수 있는 문제이다. 조금더 실전과 같은 훈련을 하기 위해 타이머를 설정하고 문제를 풀었다. 비교적 쉬운 난이도여서 약 8분정도 만에 문제를 해결하였다. 풀이방법은 N개의 동전을 가치가 가장 큰 순서대로 정렬을 한다. 그리디는 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 따라서 동전 개수를 최소한으로 하기 위해 선택의 순간마다 가치의 합 K를 결정할때 K보다 작은 동전중 가장 큰 가치를 가진 동전을 선택하면 된다. 예를들어 예시가 다음과 같이 주어졌을경우 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 4200원 보다 작은 동전 중 가치가 가장 큰 1000을 고르면 된다. 이후 1..

첫째 줄에 물이 새는 곳의 개수 N과 테이프 길이L 이 주어진다. 풀이방법은 시작점(start)을 잡고 시작점을 기준으로 물이 새는 곳(v[i]) 까지 거리가 L > n >> l; for(int i = 0; i > num; v.push_back(num); } if(l == 1) { cout