알고리즘!/다른 알고리즘4 [C/C++ ] 백준 2467: 용액 (두 포인터) https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 맨 처음에는 bruteforce하게 문제 접근하여 각 경우마다 안되는 경우를 계산하여 시간복잡도가 O(n^2/4)짜리 알고리즘을 짰지만 시간초과가 나왔다. 그 후 이 문제를 "두 포인터"를 이용해 풀었다. 두 포인터란? 두 포인터/ 투 포인터는 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘이다. 즉, 2개의 포인터를 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간 .. 2023. 10. 20. [C/C++] 백준 1644: 소수의 연속합 (에라토스테네스의 체 & 부분 합) https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이! 이 문제를 풀기 위한 과정은 크게 2가지로 나뉜다. 첫번째로는 1부터 n번째까지의 수들 중에서 소수들을 구해야하는 것이고 두번쨰로는 부분 합을 이용하여 연속된 소수의 합으로 주어진 자연수를 나타낼 수 있는 경우의 수를 구하는 과정이다. 첫번째 과정은 소수 판정을 위한 에라토스테네스의 체를 사용하면 되고 두번째는 부분 합을 이용하면 된다. 에라토스테네스의 체 에라토스네스의 체란? 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 만들어낸 소수를 찾는 방법으로 체로 치듯이 수를 걸러낸다고 하여 뒤에 '체'.. 2023. 10. 14. [C/C++] 백준 1806: 부분합 (누적 합 이용) https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이! 사실 문제 이름 자체도 부분합이고 문제 내용도 부분합이라서 "누적합"을 이용하여 문제를 풀어야겠다는 생각을 할 수 있었다. 부분 합(누적 합) 부분 합이란 배열의 시작부터 현재 위치까지의 원소의 합을 구해둔 배열이다. 이렇게 부분 합을 미리 구해 놓는다면 a번째 index부터 b번째 index까지의 합을 구할 때 O(b-a)의 시간이 걸릴 것을 psum[b]-psum[a-1].. 2023. 10. 14. [C/C++] 백준 11286: 절댓값 힙 (구조체와 연산자 오버로딩) https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 절댓값 힙 문제는 최소 힙 문제를 조금 변형시켜면 쉽게 풀 수 있다. 최소 힙 문제에서 priority_queue를 정의할 때 priority_queue queue;를 사용해야 했다면 이 문제에서는 절댓값이 작은 순으로 heap을 정렬시켜야하므로 세번째 자리에 greater 가 아닌 priority_queue queue;와 같은 새로 정의한 구조체를 넣어줘야한다. 참고로 pr.. 2023. 9. 5. 이전 1 다음
