본문 바로가기

전체 글

 (209)
[백준 11501] 주식 그리디 문제 www.acmicpc.net/problem/11501 [문제 풀이] N개의 주가가 주어졌을 때, 최대 이익을 내는 문제입니다. N의 제한이 1,000,000입니다. 테스트 케이스까지 존재하므로 무조건 $O(N)$의 시간 복잡도로 해결해야 합니다. 우선 최대 이익을 내는 방법을 생각해보겠습니다. 주식을 계속 사들인 다음에 최대 가치일 때 한 번에 팔아버리면 당연히 최대로 이익을 얻을 수 있습니다. 예를 들어 주가가 1, 5, 10일 때, 1을 사고 굳이 5에 팔기보다, 10에 파는 것이 이득입니다. 즉, 현재 구입하는 시점 이후에서 가장 비쌀 때 팔아버리면 되고 현재 구입하는 시점이 가장 비싸다면 사지 않는 것이 이득입니다. 문제는 현재 구입하는 시점 이후에 가장 비싼 때가 언젠지 모른다는 것..
[백준 20500] Ezreal 여눈부터 가네 ㅈㅈ 다이나믹 프로그래밍 문제 www.acmicpc.net/problem/20500 친숙한 문제입니다. [문제 풀이] 1과 5로만 주어진 N자리 자연수 중 15의 배수의 개수를 찾는 문제입니다. 15의 배수라고 하니 별다른 특징을 찾기가 힘듭니다. 조금 형태를 바꿀 필요가 있어 보입니다. 15는 3의 배수이면서 5의 배수입니다. 3과 5는 배수를 구할 때 상당히 익숙한 수입니다. 그러므로 15의 배수인 수를 구하기 위해 3의 배수이면서 5의 배수인 수를 구해보겠습니다. 우선 3의 배수는 모든 자리의 수를 전부 더하고 3으로 나눴을 때 나누어 떨어지는 성질이 있습니다. 그리고 5의 배수는 1의 자릿수가 0이거나 5입니다. 이 문제에서는 1과 5로만 수가 이루어져 있으므로 1의 자릿수가 5입니다. 그러므로 15의..
[붕어빵 꼬리먼저 팀] 4회차 - 학습 마무리 2021/01/21 동계 모각코 4회차 오늘 공부하고자 했던 회전하는 캘리퍼스에 대한 이해와 문제 풀이를 마쳤습니다. [회전하는 캘리퍼스] www.acmicpc.net/problem/10254 회전하는 캘리퍼스를 사용하여 가장 먼 두 점을 구하는 문제입니다. 우선 존재하는 모든 점들에서 가장 먼 두 점을 찾기 위해서는 볼록껍질을 사용합니다. 주어진 점 중에 가장 먼 두점이 볼록껍질 위에 존재함은 직관적으로 떠올릴 수 있습니다. 그러나 볼록껍질을 구한 후에 볼록껍질에 해당되는 모든 점들에 대해서 가장 먼 거리를 찾는 것도 $O(N^2)$입니다. N의 크기가 줄었을 뿐, 시간복잡도 면에서는 여전히 부족합니다. 이런 문제를 해결하기 위해 회전하는 캘리퍼스라는 알고리즘을 사용하는데, $O(N)$에 볼록껍질에서 ..
[붕어빵 꼬리먼저 팀] 4회차 - 학습 계획 2021/01/21 동계 모각코 4회차 오늘 학습할 주제는 회전하는 캘리퍼스입니다. www.acmicpc.net/problem/10254 해당 문제 풀이를 목표로 하겠습니다.
[백준 20149] 선분 교차 3 선분 교차 판정 문제 www.acmicpc.net/problem/20149 www.acmicpc.net/problem/17387 해당 문제의 기본형 문제입니다. 위 문제를 먼저 푸는 것을 권장합니다. [문제 풀이] 두 선분이 주어졌을 때 두 선분의 교차 여부와 교점을 찾는 문제입니다. 교차하지 않거나 교차하는 점이 무수히 많다면 교점을 출력하지 않습니다. 우선, 다행히도 한 선분을 이루는 두 점은 겹치지 않습니다. 두 점이 겹쳤다면 문제가 상당히 귀찮아집니다. 선분 교차 2의 풀이에서 더 귀찮아진 형태입니다. 테스트 케이스도 상당히 견고해서 집중하고 코드를 짜야합니다. 설명하기에 앞서, 선분 교차 2를 완벽히 이해했다는 가정 하에 설명하겠습니다. 또한 네 점을 p1, p2, p3, p4라고 하고 CCW(..
[붕어빵 꼬리먼저 팀] 3회차 - 학습 마무리 2021/01/19 동계 모각코 3회차 오늘 공부하고자 했던 머지 소트 트리에 대한 이해와 문제 풀이를 완료하였습니다. 원래 계획했던 문제는 수열과 쿼리 1 (www.acmicpc.net/problem/13537) 였습니다. 그러나 해당 문제는 오프라인 쿼리를 활용하여 머지 소트 트리 없이도 해결이 가능한 문제였기에, 입력에 이전 쿼리의 정답을 요구하여 온라인 쿼리를 강제한 수열과 쿼리 3 (www.acmicpc.net/problem/13544) 를 풀기로 하였습니다. 해당 문제는 온라인 쿼리를 강제하여 오프라인 쿼리를 사용한 세그먼트 트리 풀이를 막았기 때문에 머지 소트 트리로만 풀어야 합니다. [머지 소트 트리] www.acmicpc.net/problem/13544 머지 소트 트리를 사용하여 특정 구..
[붕어빵 꼬리먼저 팀] 3회차 - 학습 계획 2021/01/19 동계 모각코 3회차 오늘 학습할 주제는 머지 소트 트리입니다. www.acmicpc.net/problem/13537 해당 문제 풀이를 목표로 하겠습니다.
[백준 2217] 로프 그리디 문제 www.acmicpc.net/problem/2217 [문제 풀이] N개의 로프를 사용하여 들 수 있는 최대의 중량을 구하는 문제입니다. N개의 로프를 사용하여 들 수 있는 중량의 모든 경우의 수를 구한다면 $O(N^2)$이 걸리게 됩니다. N의 최대 제한이 100,000이므로 당연히 시간 초과가 발생합니다. 그러므로 단순하게 전부 구하는 방식 말고 다른 방식을 찾아야 합니다. 이 문제를 어떻게 접근하는지 잘 생각해봅시다. 우리가 구해야 하는 것은 로프가 버틸 수 있는 최대 중량입니다. 사용할 수 있다면 튼튼한 로프를 사용하는 것이 좋아 보입니다. 또한 상대적으로 튼튼하지 않은 로프를 버리고 튼튼한 로프만 사용하여 물체를 들어 올리는 것도 좋아 보입니다. 튼튼하지 않은 로프를 버리는 과정에서,..

티스토리툴바