전체 글102 [C/C++] 백준 12015: 가장 긴 증가하는 부분 수열2 (O(logn) 알고리즘) ㅣhttps://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이! 이 문제를 기존의 11503: 가장 긴 증가하는 부분 수열 푼 방식으로 풀 경우에는 해결이 불가능하다. 그 이유는 11503 문제의 알고리즘은 시간복잡도가 O(n^2)로 구현해도 해결이 가능했지만 이 문제는 수열의 크기가 10^6이므로 똑같이 시간복잡도가 O(N^2)가 되어 시간초과가 발생하게 된다. 그렇기 때문에 새로운 아이디어를 생각해야한다. 일단 가장 기본적인 알고리즘은 11503 .. 2023. 10. 14. [C/C++] 백준 20040: 사이클 게임 (Union-Find) https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 해설! 이 문제는 최소 스패닝 트리를 구하기 위해서 필요한 연산인 Union-Find를 이용하면 쉽게 풀리는 문제였다. 이 문제를 Map이나 c++ 내부에 있는 자료구조를 이용하여 풀 경우에는 사실상 해결이 불가능한데 그 이유는 점의 개수가 최대 500,000개이며 진행되는 연산이 최대 1,000,000이기 때문이다. 그렇기 때문에 Union-find를 이용하여 그 연산시간이 O(logn) .. 2023. 10. 12. [C/C++] 백준 2252: 줄 세우기 (위상정렬) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 이 문제를 풀기 위해서는 위상 정렬에 대한 이해가 필요하다! 위상 정렬? 위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미하며 정렬 알고리즘의 일종이다. 위 문제와 같이 1은 3보다 먼저 와야하고 2는 3보다 먼저 들어와야 한다는 방향성이 있을 때 사용 가능하는 알고리즘이다. 따라서 위상 정렬의 결.. 2023. 10. 11. [C/C++] 1562: 계단 수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제를 10844: 쉬운 계단 수처럼 모든 경우의 수를 배열에 저장하여 풀려고 한다면 메모치 초과가 날 것이다. 그렇기 때문에 메모리 아끼면서 Dynamic Programming을 해결하기 위한 방법으로 비트마스킹을 이용하면 된다. 이 문제는 사실 10844 문제를 비트마스킹으로 풀기만 하면 되기 때문에 자세한 알고리즘은 아래 포스팅을 참고하면 된다! https://donggul-godsang.tistory.com/67 [C/C++] 10844: 쉬운 계단 수 https://www.acmicpc.net/problem.. 2023. 10. 11. 이전 1 2 3 4 5 6 7 ··· 26 다음
